奇袭

题目描述

由于各种原因，桐人现在被困在Under World（以下简称UW）中，而UW马上 要迎来最终的压力测试——魔界入侵。

唯一一个神一般存在的Administrator被消灭了，靠原本的整合骑士的力量 是远远不够的。所以爱丽丝动员了UW全体人民，与整合骑士一起抗击魔族。

在UW的驻地可以隐约看见魔族军队的大本营。整合骑士们打算在魔族入侵前 发动一次奇袭，袭击魔族大本营！

为了降低风险，爱丽丝找到了你，一名优秀斥候，希望你能在奇袭前对魔族 大本营进行侦查，并计算出袭击的难度。

经过侦查，你绘制出了魔族大本营的地图，然后发现，魔族大本营是一个N ×N的网格图，一共有N支军队驻扎在一些网格中（不会有两只军队驻扎在一起）。

在大本营中，每有一个k×k(1≤k≤N)的子网格图包含恰好k支军队，我们袭 击的难度就会增加1点。

现在请你根据绘制出的地图，告诉爱丽丝这次的袭击行动难度有多大。

输入格式

第一行，一个正整数N，表示网格图的大小以及军队数量。

接下来N行，每行两个整数,Xi,Yi，表示第i支军队的坐标。

保证每一行和每一列都恰有一只军队,即每一个Xi和每一个Yi都是不一样 的。

输出格式

一行，一个整数表示袭击的难度。

样例

样例输入

5
1 1
3 2
2 4
5 5
4 3

样例输出

10

数据范围与提示

样例解释

显然，分别以(2,2)和(4,4)为左上,右下顶点的一个子网格图中有3支军队，这为我们的难度贡献了1点。类似的子网格图在原图中能找出10个。

数据范围

对于30%的数据，N ≤ 100
对于60%的数据，N ≤ 5000
对于100%的数据，N ≤ 50000

这是道毒瘤题，毒瘤的不能再毒瘤，你可以想出各种O(n⁵)，O(n⁴)，O(n³)以至于O(n²)的算法，然而你都会T，且卡常卡不过去，而正解是个O(nlogn)的

关于超时的算法我其实还是想说一说，由于考试的时候我zz，所以最好也就打了一个n⁴，实际上这题的n³很好打，就是枚举起始点以及块的大小，这个复杂度最多也就T27吧

然后是n²的，那么你就需要认真读题，我没好好读题，我不是人，注意一下我标红加粗那一行(为什么考试的时候没人给我加粗。。。。。)，他说每行每列就一个，那我们把这个方格图拍扁怎么样，我们把它从二维搞成一维，也就是表示成a[x]=y的形式，那么思考一下，对于一个区间[L,R]，这个LR就是横坐标的范围，也就是子方格图的宽，而a[L]到a[R]之间的max和min就是纵坐标的范围，也就是子方格图的长，那只要max-min=R-L，这个区间就是一个合法的区间，这样的话两层循环枚举L和R就达到了n²，就可以愉快的T67了，据某些Dalao说n²卡一卡可以T91

接下来就是正解了，需要用到刚才拍扁方格的思路，还要用的二分，单调性以及桶

如果我们用二分的想法的话，ans[L,R]=ans[L,mid]+ans[mid+1,R]+跨过mid部分的合法方案，关于前两项，递归下去去算就没问题，重点需要解决的是第三项，我们来想一想这个跨过mid都包含些什么情况

1.min max都在左边

2.min max都在右边

3.min在左边max在右边

4.min在右边max在左边

我们化减一下这四种方案变成  一.最值在同侧  二.最值在异侧

首先我们需要记录一下从mid到L中间这些区间内的最值以及mid+1到R中间这些区间的最值

一.最值在同侧(以均在左侧为例)

如果最值都在左侧，那么就需要满足max[l]-min[l]=r-l，这个和n²的思路是一样的，我们移一下项，就得到了r=max[l]-min[l]+l，那我们就可以枚举这个l，来确定每一个对应的r，来看是不是符合条件

如果都在右侧，同样的思路枚举右端点就可以了

二.最值在异侧(以最小值在左最大值在右为例)

我在说正解之前提到了单调性，那什么具有单调性呢？这个区间max min具有单调性，因为左区间的最值都是有mid开始推的，那从mid到L，min严格不上升，max严格不下降，这个很显然嘛，那同理，从mid+1到Rmin严格不上升，max严格不下降，我们假设左区间是[L,mid]，那什么样的右区间是合法的呢？我们设两个指针r1，r2，把他们的初始位置放在mid+1处，我们在移动指针之前先想一想右区间应该满足什么才可以称作合法，诶呀，不就是min[r]>min[l] max[r]>max[l]嘛，关于这个max我们可以找到第一个比max[l]大的，由于这个单调性，第一个max及其之后都大于max[l]，我们还可以找到最后一个比min[l]大的，同样由于这个单调性最后一个之后的min都小于min[l]，变成了不合法区间，这样的话我们用r1，r2这两个指针找到这个第一个和最后一个，这中间就是合法方案，他还需要满足一个什么条件来着？max[r]-min[l]=r-l，还是移项，那就可以变形为max[r]-r=min[l]-l，这样的话等式两边就变成了两个独立的部分，我们把这个独立的部分扔进桶里，让他进行加加减减的操作我们就可以得到正确的区间数，当然了，我们最开始定下了大左区间[L,mid]，我们现在需要缩小它，那r1和r2两个指针也就接着移动就可以了

如果最大值在左，最小值在右，也是一样的思路，在左边找到合法区间，移动右区间就可以了

当然这题还可以翻转，就是那个reverse，代码会变短，复杂度的话多个logn

注意：桶记得清空，min[l]-l可能小于0，所以再加个n

 1 #include<iostream>
 2 #include<cstdio>
 3 #define maxn 50010
 4 #define ll long long
 5 using namespace std;
 6 int n,maxx,minn;
 7 ll ans;
 8 int a[maxn],mi[maxn],ma[maxn],tong[maxn*3];
 9 inline int read()
10 {
11     int e=0,f=1;  char ch=getchar();
12     while(ch<'0'||ch>'9')
13     {
14         if(ch=='-')  f=-1;
15         ch=getchar();
16     }
17     while(ch>='0'&&ch<='9')  {e=(e<<3)+(e<<1)+(ch-48);  ch=getchar();}
18     return e*f;
19 }
20 ll fz(int l,int r)
21 {
22     if(l==r)  return 1;
23     ll da=0,sum=0;  int mid=(l+r)>>1;
24     da=fz(l,mid)+fz(mid+1,r);
25     ma[mid]=mi[mid]=a[mid];
26     for(int i=mid-1;i>=l;--i)  {ma[i]=max(ma[i+1],a[i]);  mi[i]=min(mi[i+1],a[i]);}
27     ma[mid+1]=mi[mid+1]=a[mid+1];
28     for(int i=mid+2;i<=r;++i)  {ma[i]=max(ma[i-1],a[i]);  mi[i]=min(mi[i-1],a[i]);}
29     for(int i=mid;i>=l;--i)//都在左侧
30     {
31         int R=ma[i]-mi[i]+i;
32         if(R<=mid||R>r)  continue;
33         if(ma[R]<ma[i]&&mi[R]>mi[i])  sum++;
34     }
35     for(int i=mid+1;i<=r;++i)//都在右侧
36     {
37         int L=i-ma[i]+mi[i];
38         if(L>=mid+1||L<l)  continue;
39         if(ma[L]<ma[i]&&mi[L]>mi[i])  sum++;
40     }
41     int r1=mid+1,r2=mid+1;//最小值在左，最大值在右
42     while(r1<=r&&mi[r1]>mi[l])  {tong[n+ma[r1]-r1]++;  r1++;}
43     while(r2<=r&&ma[r2]<ma[l])  {tong[n+ma[r2]-r2]--;  r2++;}
44     for(int L=l;L<=mid;++L)
45     {
46         while(r1>mid+1&&mi[r1-1]<mi[L])  {r1--;  tong[n+ma[r1]-r1]--;}
47         while(r2>mid+1&&ma[r2-1]>ma[L])  {r2--;  tong[n+ma[r2]-r2]++;}        
48         if(tong[n+mi[L]-L]>0)  sum+=tong[n+mi[L]-L];
49     }
50     for(int i=mid+1;i<=r;++i)  tong[n+ma[i]-i]=0;
51     r1=mid;  r2=mid;//最大值在坐，最小值在右
52     while(r1>=l&&mi[r1]>mi[r])  {tong[n+ma[r1]+r1]++;  r1--;}
53     while(r2>=l&&ma[r2]<ma[r])  {tong[n+ma[r2]+r2]--;  r2--;}
54     for(int R=r;R>=mid+1;--R)
55     {
56         while(r1<mid&&mi[r1+1]<mi[R])  {r1++;  tong[n+ma[r1]+r1]--;}
57         while(r2<mid&&ma[r2+1]>ma[R])  {r2++;  tong[n+ma[r2]+r2]++;}
58         if(tong[n+mi[R]+R]>0)  sum+=tong[n+mi[R]+R];
59     }
60     for(int i=l;i<=mid;++i)  tong[n+ma[i]+i]=0;
61     da+=sum;
62     //cout<<"from"<<l<<"to"<<r<<"sum="<<sum<<endl;
63     return da;
64 }
65 int main()
66 {
67     n=read();
68     for(int i=1;i<=n;++i)  {int o=read(),p=read();  a[o]=p;}
69     ans=fz(1,n);
70     printf("%lld\n",ans);
71     return 0;
72 }

View Code