大致的简化题意在我的考试反思里有，裸n2及以上的暴力也不打算再讲了。
1 #include<cstdio> 2 #include<ctime> 3 using namespace std; 4 #define rus register unsigned short 5 inline unsigned short max(const rus a,const rus b){return a>b?a:b;} 6 inline unsigned short min(const rus a,const rus b){return a<b?a:b;} 7 inline unsigned short read(){ 8 rus a=0;register char ch=getchar(); 9 while(ch<48||ch>57)ch=getchar(); 10 while(ch>=48&&ch<=57)a=(a<<3)+(a<<1)+ch-48,ch=getchar(); 11 return a; 12 } 13 int ans; 14 unsigned short pos[50005],n; 15 int main(){ 16 n=read(); 17 for(rus i=1,x,y;i<=n;++i) x=read(),y=read(), pos[x]=y; 18 for(rus i=1,maxx=0,minn=50006;i<=n;++i,maxx=0,minn=50006){ 19 if(clock()>990000){printf("%d ",ans+n-i+1);return 0;} 20 for(rus j=i;j<=n;++j){ 21 maxx=max(maxx,pos[j]); minn=min(minn,pos[j]); 22 if(maxx-minn==j-i)ans++; 23 } 24 } 25 26 printf("%d ",ans);//printf("%ld ",clock()); 27 }
跳跃的91分n2还是要讲一下的：
看上边的代码里的枚举，我们在循环中不断更新maxx和minn。
然而我们需要的是maxx-minn==j-i，如果maxx和minn的差值很大，那么j接下来的很多次枚举都不会更新答案。
我们考虑跳过这段区间直到j=maxx-minn+i（简单移项别说不会），这才有可能更新答案嘛。
这时j跳了一大段，中间的maxx和minn怎么更新呢？
我们考虑预处理出区间最大最小值，RMQ（ST,线段树，树状数组选你喜欢的就好）
这样我们就可以跳起来了！枚举量减小了很多。
但是，答案的累加还是ans++的，而本题最大的答案是50000×50000的正方形里的主对角线。
这时的答案是50000×50001/2>1e9，单纯ans++这个思路就会TLE
所以让我们放弃它，从头想。
码农与一个厉害的程序员的区别在哪里？一个只会码，另一个会思考。
我们对式子动一下手脚吧，假装我们不是码农的样子。
看数据范围，n log是可以接受的。考虑那些含有二分思想的玩意。
有的题解说线段树，其实是类似一个动态权值线段树的玩意，思想大同小异。
一个区间，从中间mid分成两个区间，如果最小值在左边最大值在右边。。。
用maxr表示max(a[mid+1],a[mid+2],...,a[r]), minl=min(a[mid],a[mid-1],...,a[l])
那么式子是maxr-minl=r-l。稍微移项，maxr-r=minl-l，现在左右两边无关了。
对于每一个r，把maxr-r的桶++，对应左边的minl-l把桶里面的值ans+=桶值。
可能有人不理解桶是什么东西吧？天天爱跑步做了吗？
没做也没关系。
大致思路就是，如果我们需要单点查询/修改某一个值出现了多少次，怎么办？
很简单那，开一个数组，数组的对应位数++，查询也直接查数组的那一位就好了呀。
这种存权值（少数时候会存权值区间）的数组就被叫做桶。
然而这乍一下维护桶是错的，为什么呢？
因为在左边的l从mid向区间左端L枚举的过程中，并非所有的r都还能满足我们预设的“最小值在左边，最大值在右边”的条件
但是我们仍然能发现，对于每一个左端点l，它所对应的合法的右区间r总是连续的，递增的。
l继续向左移--，对应的右区间的两个端点称之为rl和rr（是闭区间[rl,rr]），它们一定不会向左移。
证明：上一步rl～rr是最大的合法决策区间，那么l左移后，maxl可能大了，minl可能小了，也可能都不变。
如果maxl变大了，那么maxr还需要满足大于maxl的话，可能需要把rl右移,它所贡献的桶值不再有效。
while(rl<=R&&maxx[l]>maxx[rl])t[maxx[rl]-rl]--,rl++;
同理，如果minl变小了，那么能够满足minr>minl的右区间可能会扩大，扩建新桶。
while(rr+1<=R&&minn[l]<minn[rr+1])rr++,t[maxx[rr]-rr];
这样就可以累加l对应的答案了。但是我们可悲的发现答案还是不对，为什么呢？
因为我们并没有限制rl和rr的大小关系，而实际上可能会出现rl>rr的情况，导致桶中有负值。
有很多解决办法：控制rl与rr的大小关系，或累加答案时判断大小关系，或累加答案是判断桶的正负。
当所有左区间枚举完毕后，记得清空你的maxx和minn以及t（桶）数组。
不要memset啊同志们，nlog次O(n)的memset想什么呢！
可以改一下memset的参数让它清区间，或手动for清，都可以。
这样我们已经考虑了最小值在左最大值在右的情况，接下来说最值都在左侧的情况。
再翻回来找出我们的算式：max-min=r-l，移项l+max-min=r
那么就很简单了，对于每个l，设rrr=l+maxl-minl，如果rrr满足设定的条件就好了
if(rrr>=mid+1&&rrr<=R&&maxx[rrr]<maxx[l]&&minn[rrr]>minn[l]) ans++;
现在我们已经处理了极值都在左边的情况和左小右大的情况。
还剩都在右边和左大右小。这两种情况嘛。。。我们尝试把数组翻过来，这两种情况就变成了上面的那两种情况。
reverse。但注意要更改一下mid值。如原区间[1,5],reverse前是[1,3]和[4,5]
翻一下之后应该是[5,4]和[3,1]，也就是左边应该有两个元素，mid=2而不在是原来的3。
没了，递归二分，到l==r直接ans++，return。没了。
顺便提一嘴，桶里那个minl-l之类的可能负过去，你可以学习下tdcp和mikufun的数组负下标操作。
否则记得给它加上50000。
1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 using namespace std; 6 int ans,n,a[50005],maxx[50005],minn[50005],t[200005]; 7 void ask(const int l,const int r){ 8 if(l==r){ans++;/*printf("!!!---%d %d---!!! ",l,ans);*/return;} 9 register int mid=l+r>>1; 10 ask(l,mid);ask(mid+1,r);//printf("-----%d %d----- ",l,r); 11 for(int p=0;p<=1;++p){//for(int i=1;i<=n;++i)printf("%d ",a[i]);puts(""); 12 for(int i=mid;i>=l;--i) minn[i]=min(minn[i+1],a[i]),maxx[i]=max(maxx[i+1],a[i]); 13 minn[mid+1]=maxx[mid+1]=a[mid+1]; 14 for(int i=mid+2;i<=r;++i) minn[i]=min(minn[i-1],a[i]),maxx[i]=max(maxx[i-1],a[i]); 15 for(int i=mid,rl=mid+1,rr=mid;i>=l;--i){//printf("---%d--- ",i); 16 while(rl<=r&&maxx[rl]<maxx[i]) t[maxx[rl]-rl+100000]--,rl++; 17 while(rr+1<=r&&minn[rr+1]>minn[i]) rr++,t[maxx[rr]-rr+100000]++; 18 if(rl<=rr&&t[minn[i]-i+100000]) ans+=t[minn[i]-i+100000];//;printf("%d %d ",rl,rr);for(int ii=100000-3;ii<=100000+3;++ii)printf("%d ",t[ii]);puts(""); 19 if(i==l) while(rl<=rr)t[maxx[rl]-rl+100000]--,rl++; 20 if(i==l) while(rr<rl-1) rr++,t[maxx[rr]-rr+100000]++; 21 //for(int ii=100000-3;ii<=100000+3;++ii)printf("%d ",t[ii]);puts(""); 22 }//printf("ans=%d ",ans); 23 for(int i=mid,rrr=i+maxx[i]-minn[i];i>=l;--i,rrr=i+maxx[i]-minn[i]) 24 if(rrr<=r&&rrr>=mid+1&&maxx[rrr]<maxx[i]&&minn[rrr]>minn[i]) ans++; 25 for(int i=r;i>=l;--i)minn[i]=0x3fffffff,maxx[i]=0; 26 reverse(a+l,a+r+1);mid=r-mid+l-1;//printf("ans=%d ",ans); 27 } 28 } 29 int main(){memset(minn,0x3f,sizeof(minn)); 30 scanf("%d",&n);for(int i=1,x,y;i<=n;++i)scanf("%d%d",&x,&y),a[x]=y; 31 ask(1,n); 32 printf("%d ",ans); 33 }