C. 奇袭
题目类型：传统 评测方式：文本比较
内存限制：256 MiB 时间限制：1000 ms 标准输入输出
题目描述
由于各种原因，桐人现在被困在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
27分
刚开始想暴力，用bitset记录行，列，都包含哪些军队，再维护干成前缀和，枚举方块长度l，行开头i，列开头j,
bitset<51000>h=(hang[i+l-1]^hang[i-1])&(lie[j+l-1]^lie[j-1]), h内的1的数量即方块内军队数 ，自己手%了几个n=100的点，发现bitset开太大，会跑的很慢很慢，
果断开成5100，TLE 27分，考试后开成51000，聪明如我，TLE 9 复杂度$O(n^3 (log^k)^3)$ k为bitset大小（复杂度lockey不太会算，请见谅）
55or64分
题中说每行每列只有一个军队，所以可以把它们按横坐标x递增排成一个序列，这个很好想。然后就是找一段区间，满足区间的y值排序后是一个连续的数列，那么就是一个含有k个军队的长宽为k的方块，ans++;
那么怎么判定满足条件呢，有博客说用两个单调队列，维护区间最大最小值，即max-min==r-l，则区间满足条件，他们是枚举区间长度，类似于滑动窗口来做的,期望TLE 64分
Lockey在此提出自己的方法：记录序列前缀和sum,枚举开头i，然后枚举j从开头到n扫一遍，扫的过程中一个优先队列维护区间最小，如果当前$(min-1)*(j-i+1)+(j-i+2)*(j-i+1)/2 ==sum[j]-sum[i-1]$ ，则满足条件，ans++, 复杂度$ O(n^2log^n)$ ,期望得分TLE 55分
91分
其他人的代码我不知道，但我的55分代码，加上一些剪枝，即可达到91分
剪枝前
剪枝后
然后惊奇的发现维护最小值完全用不着优先队列
去掉之后
快了1000ms，但接下来无论我怎么卡常都卡不过去了，听说曾经有学长91分TLE卡常卡了一天没卡过去，还好我只卡了一下午+一晚上
#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
#define rint register int
const int L(<<|);
char buffer[L],*S,*T;
#define getchar() ((S==T&&(T=(S=buffer)+fread(buffer,1,L,stdin),S==T))?EOF:*S++)
inline int read(){
rint ret;
register char r;
while(r=getchar(),r<''||r>'');ret=(r^);
while(r=getchar(),r>=''&&r<='')ret=(ret<<)+(ret<<)+(r^);
return ret;
}
int n,lo[],a[],minn(0x7fffffff);
long long sum[],ans;
bool judge(int j,int i){
return sum[j]-sum[i-]==(long long)(minn-)*(j-i+)+(long long)(j-i+)*(j-i+)/;
}
int main(){
n=read();
int x,y;
for(rint i=;i<=n;i++){
x=read(),y=read();
lo[y]=x;
a[x]=y;
}
for(rint i=;i<=n;i++){
sum[i]=sum[i-]+a[i];
}
for(rint i=;i<=n;i++){
for(rint j=i;j<=n;j++){
if(lo[a[j]-]<i&&lo[a[j]+]<i){
if(j==i) ans++;
break;
}
minn=min(a[j],minn);
if(judge(j,i)) ans++;
}
minn=0x7fffffff;
}
printf("%lld\n",ans);
}
91分1000多ms代码
100分
boss来了～
joker学长证明$n^2$算法是绝对卡不过去的
正解 ：分治+桶排
把序列不断二分，处理左右区间，然后加上跨mid即跨左右区间的子区间的符合条件的方案
mxl[i] 表示i~mid 的最大值，mil[i]表示 i～mid的最小值
mxr[i] 表示mid+1~i的最大值，mir[i]表示mid+1～i的最小值
找这段满足条件的区间的情况，这个区间肯定有最大值最小值
1. 最大值最小值都在mid左边，即在左区间
2. 都在右区间
3. 最小值在左，最大值在右
4. 大在左，小在右
对于前两种情况，其实很简单，先说都在左区间： 枚举l~mid为跨mid的区间的左端点，mxl[i],mil[i]表示i～mid即当前左区间的最大最小，那么显然在大情况整个区间最大最小值都在左区间下，mxl[i]即为左右区间（整个区间）最大值，mil[i]为最小值。
回想区间成立的条件 max-min==r-l， mxl[i]-mil[i]+1即为区间长度，i为左端点，如果区间满足条件,那右端点j=i+mxl[i]-mil[i] ,且j的情况不违背大条件（即mxr[j]<mxl[i]&&mir[j]>mil[i]）,而且j<=区间右边界r。
则反过来，如果j<=区间右边界r且mxr[j]<mxl[i]&&mir[j]>mil[i]（保证mxl[i]最大mil[i]最小）,那么区间满足条件，ans++,都在右区间同理，枚举右端点即可
对于后两种情况就有些麻烦了
继续回想条件 max-min==r-l ，移项 min-l=max-r
仍然以其中一种情况为例，3.小在左大在右
那么可以统计右边max-r的值，放进桶里面（也就是一个数组，大概实现就是统计某个值出现了几次），统计这个差值出现了几次
然后枚举左边min-l ，查询这个差值在桶里出现了几次，看右边有几个与他相等的，有几个ans就加几
4.同理 满足条件 max-min==r-l, 只不过因为max在左，min在右，移项成 max+l=min+r,同上操作
以上讲的是我的理解，至于一些具体操作，建议看看这几篇博客
上代码
#include<iostream>
#include<cstdio>
using namespace std;
int n,a[],t[],maxl[],minl[],maxr[],minr[];
long long ans;
void dfs(int l,int r){
if(l==r) {ans++;return;}
int mid=(l+r)>>;
dfs(l,mid),dfs(mid+,r);
maxl[mid]=minl[mid]=a[mid];
maxr[mid+]=minr[mid+]=a[mid+];
for(int i=mid-;i>=l;i--) maxl[i]=max(maxl[i+],a[i]),minl[i]=min(minl[i+],a[i]);
for(int i=mid+;i<=r;i++) maxr[i]=max(maxr[i-],a[i]),minr[i]=min(minr[i-],a[i]);
//小大同左
for(int i=l;i<=mid;i++){
int j=i+maxl[i]-minl[i];
if(j>mid&&j<=r&&maxr[j]<maxl[i]&&minr[j]>minl[i]) ans++;
}
//小大同右
for(int i=mid+;i<=r;i++){
int j=i-maxr[i]+minr[i];
if(j<=mid&&j>=l&&maxl[j]<maxr[i]&&minl[j]>minr[i]) ans++;
}
//小左大右
//maxr[j]-minl[i]=j-i
//移项 maxr[j]-j=minl[i]-i 小右大左同
int z=mid+,z1=mid+;
for(int i=mid;i>=l;i--){
while(z<=r&&maxr[z]<maxl[i]) t[maxr[z]-z+n]--,z++;
while(z1<=r&&minr[z1]>minl[i]) t[maxr[z1]-z1+n]++,z1++;
if(t[minl[i]-i+n]>) ans+=t[minl[i]-i+n];
}
for(int i=mid+;i<=r;i++) t[maxr[i]-i+n]=;
//小右大左
z=z1=mid+;
for(int i=mid;i>=l;i--){
while(z<=r&&minr[z]>minl[i]) t[minr[z]+z+n]--,z++;
while(z1<=r&&maxr[z1]<maxl[i]) t[minr[z1]+z1+n]++,z1++;
if(t[maxl[i]+i+n]>) ans+=t[maxl[i]+i+n];
}
for(int i=mid+;i<=r;i++) t[minr[i]+i+n]=;
//cout<<"l="<<l<<" r="<<r<<" ans="<<ans<<endl;
}
int main(){
scanf("%d",&n);
int x,y;
for(int i=;i<=n;i++) scanf("%d%d",&x,&y),a[x]=y;
dfs(,n);
printf("%lld",ans);
}
