考试时的题，当时玄学的打了个树状数组，后来发现还不如打前缀和。。。。
N^2暴力：
我没打不过主要依靠每一行列只有一个军队，使问题转化为在1～n的区间中找区间max-min=len就行了
Nlogn正解：
这题正解感人，考试完全没想到......
首先要把这题和分治联系在一起，其中求每段的符合条件的个数大体分两种情况
首先maxl[i]表示从i到mid的最大值 maxr[i]表示从mid+1到i的最大值 minl[] minr[]同理
1.当最大最小值在不同区间时（mid的左右两段时）以左为例
这种情况略微简单，依据式子发maxl[i]-minl[i]=j-i
移项可知j=maxl[i]-minl[i]+i;
所以判断此时的j是否符合条件，maxl[i]>maxr[j],minl[i]<minr[j],j>mid+1,j<r(注意这里是r而不是n)
在右侧同理
2.当最大值最小值不在同一区间时
这种情况要用到一种“桶”的思想，相信有和我一样不懂桶的蒟蒻，简单来说桶是以数的权值为下标而tong[]的权值表示出现次数。
然后这题以左小右大为例
i从mid循环到l因为左边的是小值所以可以发现maxr在右侧单増而minr递减
定义两个指针zuo you易发现左在向右移动时直到maxr[zuo]>maxl[i]在这之前都是不符合的所以tong[maxr[zuo]-zuo]--;而you移动至minl<minr时之前都是可能符合的所以令其++而这样只会使其中的某一段有值，其余已归零。
所以已知maxr[j]-minl[i]=j-i等价maxr[j]-j=min1[i]-i;
可以在桶+-中tong[....+n]防止变为负数
然后一定要清空，发现可能修改的值只是两个指针运动的地方
所以从mid+1到r将tong[maxr[i]-i+n]=0即可。
代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<string> 5 #include<algorithm> 6 #include<vector> 7 #include<cmath> 8 using namespace std; 9 #define SBCYF 150000 10 #define ll long long 11 using namespace std; 12 ll maxr[SBCYF];ll maxl[SBCYF];ll minr[SBCYF];ll minl[SBCYF]; 13 ll tong[SBCYF]; 14 ll a[SBCYF]; 15 ll n; 16 ll find(ll l,ll r) 17 { 18 ll ans=0; 19 ll mid=(l+r)>>1; 20 if(l==r)return 1; 21 else ans=find(l,mid)+find(mid+1,r); 22 //printf("l====%lld r=====%lld mid=%lld ",l,r,mid); 23 minl[mid]=a[mid];maxl[mid]=a[mid]; 24 for(ll i=mid-1;i>=l;--i) 25 { 26 maxl[i]=max(a[i],maxl[i+1]); 27 minl[i]=min(a[i],minl[i+1]); 28 } 29 minr[mid+1]=a[mid+1];maxr[mid+1]=a[mid+1]; 30 for(ll i=mid+2;i<=r;++i) 31 { 32 maxr[i]=max(a[i],maxr[i-1]); 33 minr[i]=min(a[i],minr[i-1]); 34 } 35 //printf("case1 "); 36 for(ll i=mid;i>=l;--i) 37 { 38 ll j=i+maxl[i]-minl[i]; //printf("i=%lld j=%lld %lld %lld ",i,j,maxl[i],minl[i]); 39 if(j<mid+1||j>r)continue; 40 if(maxr[j]>maxl[i]||minr[j]<minl[i])continue; 41 ans++; 42 // printf("i=%lld j=%lld ans=%lld ",i,j,ans); 43 } 44 // printf("case2 "); 45 for(ll j=mid+1;j<=r;++j) 46 { 47 ll i=j-(maxr[j]-minr[j]); 48 if(i>mid||i<l)continue; 49 if(maxl[i]>maxr[j]||minl[i]<minr[j])continue; 50 ans++; 51 // printf("i=%lld j=%lld ans=%lld ",i,j,ans); 52 } 53 //小值在左 大值在右 54 // printf("case3 "); 55 for(ll i=mid,zuo=mid+1,you=mid+1;i>=l;--i) 56 { 57 //printf("z%lld y%lld ",zuo,you); 58 while(minr[you]>minl[i]&&you<=r) 59 { 60 tong[maxr[you]-you+n]++; 61 // printf("t[%lld]=%lld ",maxr[you]-you+n,tong[maxr[you]-you+n]); 62 you++; 63 // printf("you=%lld ",you); 64 } 65 while(maxr[zuo]<maxl[i]&&zuo<=r) 66 { 67 tong[maxr[zuo]-zuo+n]--; 68 // printf("t[%lld]=%lld ",maxr[zuo]-zuo+n,tong[maxr[zuo]-zuo+n]); 69 zuo++; 70 // printf("zuo=%lld ",you); 71 } 72 if(tong[minl[i]-i+n]>=0) 73 { 74 ans+=tong[minl[i]-i+n]; 75 } 76 //printf("i=%lld zuo=%lld you=%lld ans=%lld ",i,zuo,you,ans); 77 } 78 for(ll i=mid+1;i<=r;++i) 79 { 80 tong[maxr[i]-i+n]=0; 81 } 82 //大值在左 小值在右 83 //clear(l,r); 84 // memset(tong,0,sizeof(tong)); 85 //printf("case4 "); 86 for(ll i=mid+1,zuo=mid,you=mid;i<=r;++i) 87 { 88 //printf("minl[%lld]=%lld maxr[%lld]=%lld ",zuo,minl[zuo],i,maxr[i]); 89 while(maxl[you]<maxr[i]&&you>=l) 90 { 91 tong[maxl[you]+you+n]--; 92 you--; 93 } 94 while(minl[zuo]>minr[i]&&zuo>=l) 95 { 96 tong[maxl[zuo]+zuo+n]++; 97 // printf("ton111====%lld ",tong[maxl[zuo]-zuo+n]); 98 // printf("tonhg[%lld]========%lld ",maxl[zuo]-zuo+n,tong[maxl[zuo]-zuo+n]); 99 zuo--; 100 } 101 if(tong[i+minr[i]+n]>=0) 102 { 103 ans+=tong[i+minr[i]+n];//printf("ans=%lld %lld ",ans,tong[4]); 104 }//printf("min[%lld]=%lld %lld ",i,minr[i],tong[6]); 105 // printf("i=%lld zuo=%lld you=%lld ans=%lld ",i,zuo,you,ans); 106 } 107 //clear(l,r); 108 for(ll i=l;i<=mid;++i) 109 { 110 tong[maxl[i]+i+n]=0; 111 } 112 //memset(tong,0,sizeof(tong)); 113 return ans; 114 } 115 int main() 116 { 117 // freopen("text.in","r",stdin); 118 // freopen("wa.out","w",stdout); 119 scanf("%lld",&n); 120 for(ll i=1;i<=n;++i) 121 { 122 ll x,y; 123 scanf("%lld%lld",&x,&y); 124 a[x]=y; 125 } 126 ll ans=find(1,n); 127 printf("%lld ",ans); 128 }