题意
? 一个长度为 \(n\) 的排列 \(a\)，求这个排列中有多少个区间 \([l,r]\)，满足这个区间的 \(max-min=r-l\)。
? 数据范围：\(n \le 3 \times 10 ^ 5\)。
题解
? 考虑分治做法。
? 考虑分治区间 \([le,rig]\)?，我们现在只考虑经过 \(mid\)? 的那部分区间，其余的递归解决。递归边界 \(le==rig\)，答案直接 \(+1\)。
? 先预处理 \(mx(max)\) 和 \(mn(min)\) 数组，维护最大最小值的前缀。具体定义如下：
- \(mx[mid]=mn[mid]=a[mid],mx[mid+1]=mn[mid+1]=a[mid+1]\)
- \(mx[i]=max(mx[i+1],a[i]),mn[i]=min(mn[i+1],a[i]),(le \le i < mid)\)
- \(mx[i]=max(mx[i-1],a[i]),mn[i]=min(mn[i+1],a[i]),(mid+1\le i\le rig)\)
? 可以发现，\(mx\) 和 \(mn\) 数组就是以 \(mid\) 为分界，向左和向右延伸的前缀和。
? 假定我们枚举了左端点 \(i\) 和右端点 \(j\)。
? 因为 \(max-min=j-i\)，我们根据 \(max\) 和 \(min\) 在 \(mid\) 左边还是右边来分类讨论。
情况1：\(mx[i]>mx[j]\and mn[i]<mn[j],mx[i]-mn[i]=j-i\)
? 我们发现最大值和最小值都在左边，我们可以直接枚举左端点 \(i\)，\(i\) 确定之后 \(j=mx[i]-mn[i]+i\)，\(j\) 也就确定了，再判断那个 \(j\) 是否合法（超界？\(mx\) 或 \(mn\) 不满足？）就行了。
情况2：\(mx[i]<mx[j]\and mn[i]>mn[j],mx[j]-mn[j]=j-i\)
? 与情况 \(1\) 类似，枚举右端点 \(j\)，判断对应的i是否合法即可。
情况3：\(mx[i]<mx[j]\and mn[i]<mn[j],mx[j]-mn[i]=j-i\)
? 式子移项可得：\(mx[j]-j=mn[i]-i\)
? 这种情况相对麻烦一些。考虑枚举左端点 \(i\)，对于每个 \(i\) 找出所有满足上述不等式的 \(j\)，只要满足不等式，用桶可以方便维护。
? 所以值可以方便维护，问题转化为了如何维护满足不等式关系。
? 考虑这几个值的单调性。因为 \(mx\) 数组都是单增的，\(mn\) 数组都是单减的，所以随着 \(i\) 变小满足 \(mn[i]<mn[j]\) 的 \(j\) 区间的右边界 一定会从 \(mid+1\) 到 \(rig\) 逐渐右移，就是说某个区间 \([mid+1,r]\) 满足 \(mn\) 的关系式，并且随着 \(i\) 变小 \(r\) 会右移。
? 再考虑 \(mx[i]<mx[j]\)? 这一条件，随着 \(i\) 变小，\(mx[i]\) 会逐渐变大，又因为 \(mx[j]\) 也是单增的，比较靠左的 \(j\) 会逐渐不满足条件，被剔除贡献。发现贡献满足先入后出的性质。
? 所以我们枚举左端点 \(i\) ，对于右端点维护一个队列，根据两个不等式加入和弹出。
情况4：\(mx[i]>mx[j]\and mn[i]>mn[j],mx[i]-mn[j]=j-i\)
? 式子转化为：\(mx[i]+i=mn[j]+j\)
? 大概和情况 \(3\) 类似，只是式子有所变化，队列头尾所用的不等式有所交换。
代码及细节
? 注意情况 \(3\) 和情况 \(4\) 结束之后要清空桶，注意情况 \(1\) 和 \(2\) 判断合法不要漏掉条件。
#include <bits/stdc++.h>
using namespace std ;
#define ll long long
#define rep(i,l,r) for(ll i=(l);i<=(r);++i)
#define per(i,r,l) for(ll i=(r);i>=(l);--i)
#define wif while
#define mem(a,b) memset(a,b,sizeof a)
const ll inf = INT_MAX , df = 3e5 + 7 , N = 1e6 + 7 ;
ll i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z,a[df],ans,mx[df],mn[df],buc[N*3];
void solve(ll le,ll rig) {
if( le > rig ) return ;
ll mid = (le+rig) >> 1 ;
if( le == rig ) return ans ++ , void() ;
solve( le , mid ) , solve( mid + 1 , rig ) ;
mx[mid] = mn[mid] = a[mid] , mx[mid+1] = mn[mid+1] = a[mid+1] ;
rep(i,mid+2,rig) mx[i] = max( mx[i-1] , a[i] ) , mn[i] = min( mn[i-1] , a[i] ) ;
per(i,mid-1,le) mx[i] = max( mx[i+1] , a[i] ) , mn[i] = min( mn[i+1] , a[i] ) ;
per(i,mid,le) {
ll j = mx[i] - mn[i] + i ;
if( mx[i] > mx[j] && mn[i] < mn[j] && j > mid && j <= rig ) ans ++ ; }
rep(j,mid+1,rig) {
ll i = j - mx[j] + mn[j] ;
if( mx[j] > mx[i] && mn[j] < mn[i] && i <= mid && i >= le ) ans ++ ; }
ll j = mid + 1 , k = mid ;
per(i,mid,le) {
wif(mn[i]<mn[k+1]&&k+1<=rig) k ++ , buc[mx[k]-k+N] ++ ;
wif(mx[i]>mx[j]&&j<=k) buc[mx[j]-j+N] -- , j ++ ;
ans += buc[mn[i]-i+N] ; }
wif(j<=k) buc[mx[j]-j+N] -- , j ++ ;
j = mid + 1 , k = mid ;
per(i,mid,le) {
wif(mx[i]>mx[k+1]&&k+1<=rig) k ++ , buc[mn[k]+k+N] ++ ;
wif(mn[i]<mn[j]&&j<=k) buc[mn[j]+j+N] -- , j ++ ;
ans += buc[mx[i]+i+N] ; }
wif(j<=k) buc[mn[j]+j+N] -- , j ++ ;
return ; }
inline ll read() {
ll x = 0 , y = 1 ; char ch = getchar() ;
wif( ch > ‘9‘ || ch < ‘0‘ ) y = ( ch == ‘-‘ ) ? - 1 : 1 , ch = getchar() ;
wif( ch >= ‘0‘ && ch <= ‘9‘ ) x = ( x << 3 ) + ( x << 1 ) + ch - ‘0‘ , ch = getchar() ;
return x * y ; }
int main() {
n = read() ;
rep(i,1,n) x = read() , y = read() , a[x] = y ;
solve(1,n) ;
printf("%lld\n",ans); return 0 ; }