题意
给定一个 (n imes n) 的棋盘，其中有 (n) 个棋子，每行每列恰好有一个棋子。
求有多少个 (k imes k) 的子棋盘中恰好有 (k) 个棋子。
传送门
(n le 3 imes 10^5)。
思路
因为每行每列恰有一个棋子，实际上就是统计 (max - min + 1 = operatorname{len}) 的区间个数。
考虑将右端点向右扫，加入一个数 (a[i]) 时，将三部分分开讨论。
- 最简单的，所有区间长度加一即可。
- 对于最大值，因为是后缀最大值，所以影响是区间相同的。维护一个最大值的单调栈，删掉一个数将让 (st[tp-1]+1) 到 (st[tp]) 的所有最大值从 (a[st[tp]]) 变为 (a[i])，是一个区间加操作
- 对于最小值，维护后缀最小值单调栈，同理是一个区间加操作
所以我们只要写一棵线段树，支持区间加，维护最小值和最小值个数即可。
对于答案，其实是 (max - min - operatorname{len}=-1) 的左端点个数（代码中直接都加了一统计零的个数），判断一下最小值是否符合，把个数加到答案中就做完了
#include <bits/stdc++.h>
const int N=300005;
int t[N<<2],tag[N<<2],size[N<<2],st1[N],st2[N],tp1,tp2,n,x,y,a[N];
long long ans;
void up(int x){
int t1=t[x<<1]+tag[x<<1],t2=t[x<<1|1]+tag[x<<1|1];
if (t1==t2) size[x]=size[x<<1]+size[x<<1|1];
if (t1<t2) size[x]=size[x<<1];
if (t1>t2) size[x]=size[x<<1|1];
t[x]=std::min(t1,t2);
}
void pushdown(int x){
if (tag[x]){
t[x]+=tag[x];
tag[x<<1]+=tag[x];
tag[x<<1|1]+=tag[x];
tag[x]=0;
}
}
void build(int k,int l,int r){
if (l==r){
t[k]=n+1;
size[k]=1;
return;
}
int mid=(l+r)>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
up(k);
}
void modify(int k,int L,int R,int l,int r,int val){
if (r<l) return;
if (L==l && R==r){
tag[k]=tag[k]+val;
return;
}
int mid=(L+R)>>1;
pushdown(k);
if (r<=mid) modify(k<<1,L,mid,l,r,val);
else if (l>mid) modify(k<<1|1,mid+1,R,l,r,val);
else{
modify(k<<1,L,mid,l,mid,val);
modify(k<<1|1,mid+1,R,mid+1,r,val);
}
up(k);
}
int main(){
scanf("%d",&n);
for (int i=1;i<=n;i++){
scanf("%d%d",&x,&y);
a[x]=y;
}
int tp1=tp1=0;
build(1,1,n);
for (int i=1;i<=n;i++){
x=a[i];
while (tp1 && x>a[st1[tp1]]) modify(1,1,n,st1[tp1-1]+1,st1[tp1],x-a[st1[tp1]]),tp1--;
st1[++tp1]=i;
while (tp2 && x<a[st2[tp2]]) modify(1,1,n,st2[tp2-1]+1,st2[tp2],a[st2[tp2]]-x),tp2--;
st2[++tp2]=i;
modify(1,1,n,i,i,-n-1);
modify(1,1,n,1,i-1,-1);
if (t[1]+tag[1]==0) ans=ans+size[1];
}
printf("%lld
",ans);
}