CF526F Pudding Monsters

传送门

模型转换：对于一个 \(n\times n\) 的棋盘，若每行每列仅有一个棋子，令 \(a_x=y\)，则 \(a\) 为一个排列。

转换成排列过后问题即变为：给定一个排列，求有多少个区间满足 \(\max-\min=r-l\)。

然后我突然发现原来模拟赛好像考过这玩意。好像是用单调栈加线段树维护。

然后我发现我完全不懂（看来是当时对着题解抄的）

事实上枚举右端点维护 \(\max-\min-\operatorname{len}\) 即可。

其中最大最小值用单调栈维护变化量。

然后把这玩意弄懂了就很简单了。

贴代码

/*---Author:HenryHuang---*/

/*---Never Settle---*/

#include<bits/stdc++.h>

using namespace std;

const int maxn=3e5+5;

int val[maxn];

int num[maxn<<2],tot[maxn<<2],tag[maxn<<2];

void up(int t){

	num[t]=min(num[t<<1],num[t<<1|1]);tot[t]=0;

	if(num[t]==num[t<<1]) tot[t]+=tot[t<<1];

	if(num[t]==num[t<<1|1]) tot[t]+=tot[t<<1|1];

	return ;

}

void down(int t){

	if(tag[t]){

		num[t<<1]+=tag[t],num[t<<1|1]+=tag[t];

		tag[t<<1]+=tag[t],tag[t<<1|1]+=tag[t];

		tag[t]=0;

	}

}

void build(int l,int r,int t){

	if(l==r){

		num[t]=tot[t]=1;

		return ;

	}

	int mid=(l+r)>>1;

	build(l,mid,t<<1);

	build(mid+1,r,t<<1|1);

	up(t);return ;

}

void update(int ll,int rr,int l,int r,int nu,int t){

	if(ll<=l&&r<=rr){

		tag[t]+=nu;

		num[t]+=nu;

		return ;

	}

	int mid=(l+r)>>1;down(t);

	if(ll<=mid) update(ll,rr,l,mid,nu,t<<1);

	if(rr>mid) update(ll,rr,mid+1,r,nu,t<<1|1);

	up(t);return ;

}

int query(int ll,int rr,int l,int r,int t){

	if(ll<=l&&r<=rr){

		if(num[t]==0) return tot[t];

		return 0;

	}

	int mid=(l+r)>>1;down(t);int tmp=0;

	if(ll<=mid) tmp+=query(ll,rr,l,mid,t<<1);

	if(rr>mid) tmp+=query(ll,rr,mid+1,r,t<<1|1);

	return tmp;

}

stack<pair<int,int> > mn,mx;

int main(){

	ios::sync_with_stdio(0);

	cin.tie(0),cout.tie(0);

	int n;cin>>n;

	for(int i=1;i<=n;++i){

		int a,b;cin>>a>>b;

		val[a]=b;

	}

	mx.emplace(0,2e9),mn.emplace(0,0);

	build(1,n,1);

	long long ans=0;

	for(int i=1;i<=n;++i){

		int p,q;

		while((!mx.empty())&&mx.top().second<=val[i]){

			tie(p,q)=mx.top();mx.pop();

			update(mx.top().first+1,p,1,n,val[i]-q,1);

		}

		mx.emplace(i,val[i]);

		while((!mn.empty())&&mn.top().second>=val[i]){

			tie(p,q)=mn.top();mn.pop();

			update(mn.top().first+1,p,1,n,q-val[i],1);

		}

		mn.emplace(i,val[i]);

		update(1,i,1,n,-1,1);

		ans=(ans+query(1,i,1,n,1));

	}

	cout<<ans<<'\n';

	return 0;

}

巴特西

「CF526F」 Pudding Monsters

CF526F Pudding Monsters

最新文章

热门文章