CF526F Pudding Monsters

Description

给定一个 $n \times n$ 的棋盘，其中有 $n$ 个棋子，每行每列恰好有一个棋子。

求有多少个 $k \times k$ 的子棋盘中恰好有 $k$ 个棋子。

$n \le 3 \times 10^5$。

2s 256MB

Solution

二维问题转化为一维问题：每列上的棋子正在 $a_i$ 行，$a$ 是个排列，求有多少区间 $[l,r]$ 是连续的。

一种可行的方法是分治，但是有点愚蠢。

另外一种方法是枚举区间右端点，用单调栈分别维护最大值和最小值。求极差 $-$ 区间长度的最小值，观察到这个值一定大于等于 $-1$，而等于 $-1$ 的地方即对答案产生贡献。

线段树区间加减，维护区间最小值及其个数。

Code

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn 300005
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
inline void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=1e9+7;
inline int power(int x,int y=mod-2) {
	int sum=1;
	while (y) {
		if (y&1) sum=sum*x%mod;
		x=x*x%mod;y>>=1;
	}
	return sum;
}
int n,a[maxn];
namespace seg{
	struct yyy{
		int lazy,Min,sum;
	}f[maxn<<2];
	inline void Pushup(int rt) {
		f[rt].Min=min(f[rt<<1].Min,f[rt<<1|1].Min);
		f[rt].sum=0;
		if (f[rt<<1].Min==f[rt].Min) f[rt].sum+=f[rt<<1].sum;
		if (f[rt<<1|1].Min==f[rt].Min) f[rt].sum+=f[rt<<1|1].sum;
	}
	inline void Pushdown(int rt) {
		if (f[rt].lazy) {
			int k=f[rt].lazy;f[rt].lazy=0;
			f[rt<<1].Min+=k;
			f[rt<<1|1].Min+=k;
			f[rt<<1].lazy+=k;
			f[rt<<1|1].lazy+=k;
		}
	}
	inline void Build(int l,int r,int rt) {
		if (l==r) return f[rt].Min=0,f[rt].sum=1,void();
		int mid=l+r>>1;
		Build(l,mid,rt<<1);
		Build(mid+1,r,rt<<1|1);
		Pushup(rt);
	}
	inline void Update(int l,int r,int rt,int head,int tail,int k) {
//		if (l==1&&r==5) gdb(l,r,rt,head,tail,k,f[rt].sum,f[rt].Min,f[rt].lazy);
		if (head<=l&&r<=tail) return f[rt].Min+=k,f[rt].lazy+=k,void();
		int mid=l+r>>1;
		Pushdown(rt);
		if (head<=mid) Update(l,mid,rt<<1,head,tail,k);
		if (tail>mid)  Update(mid+1,r,rt<<1|1,head,tail,k);
		Pushup(rt);
	}
}
int s1[maxn],tot1,s2[maxn],tot2;ll ans;
signed main(void){
	int i,x,y;
	read(n);
	for (i=1;i<=n;i++) read(x),read(y),a[x]=y;
	seg::Build(1,n,1);
	for (i=1;i<=n;i++) {
		while (tot1&&a[s1[tot1]]>a[i]) {//Min
			seg::Update(1,n,1,s1[tot1-1]+1,s1[tot1],a[s1[tot1]]-a[i]);
			tot1--;
		}
		s1[++tot1]=i;
		while (tot2&&a[s2[tot2]]<a[i]) {//Max
			seg::Update(1,n,1,s2[tot2-1]+1,s2[tot2],-a[s2[tot2]]+a[i]);
			tot2--;
		}
		s2[++tot2]=i;
		seg::Update(1,n,1,1,i,-1);
		ans+=seg::f[1].sum;
	}
	printf("%lld",ans);
	return 0;
}