[ZJOI2012]小蓝的好友

https://www.luogu.org/problemnew/show/P2611

题解

\(n\times m\)肯定过不去。。

我们把给定的点看做障碍点，考虑先补集转化为求全空矩阵。

然后我们枚举每一行，令这一行每个点的权值为从这点向上的极大不包含障碍点的连续段。

然后对这个序列建立笛卡尔树，那么答案为：

\[f[x]=(h[x]-h[fa[x]])*\frac{szie[x]*(size[x]+1)}{2}
\]

我们的笛卡尔树上的的每个节点都要维护一个这样的信息。

现在我们还需要扫描每一行，动态维护这颗笛卡尔树。

如果这行没有障碍点，我们整体加个1就好了，这个可以直接打标记。

对于障碍点，相当于这个位置的值变成了0，那么我们把这个点旋转上来就好了，通过手玩我们可以发现\(rotate\)操作不会破坏除了这个点以外的其他点的笛卡尔树结构，于是我们可以一直\(rotate\)把这个点转上去，顺便更新一下答案就好了，因为是随机的数据，所以每次期望操作次数是\(log\)的。

注意如果按照上面的\(\Delta h\)那样算贡献的话如果一个点的父亲改变了的话这个点需要重新\(pushup\)一次。

代码

#include<bits/stdc++.h>

#define N 100009

#define ls tr[x][0]

#define rs tr[x][1]

using namespace std;

typedef long long ll;

vector<int>vec[N];

vector<int>::iterator it;

int tr[N][2],fa[N],size[N],h[N],la[N],n,m,num,rot;

ll dp[N],ans;

inline ll rd(){

	ll x=0;char c=getchar();bool f=0;

	while(!isdigit(c)){if(c=='-')f=1;c=getchar();}

	while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}

	return f?-x:x;

}

inline ll calc(ll x){return x*(x+1)/2;}

inline bool ge(int x){return tr[fa[x]][1]==x;}

inline void pushup(int x){

	size[x]=size[ls]+size[rs]+1;

	dp[x]=dp[ls]+dp[rs]+1ll*(h[x]-h[fa[x]])*calc(size[x]);

}

inline void rotate(int x){

	int y=fa[x],o=ge(x);

	tr[y][o]=tr[x][o^1];fa[tr[y][o]]=y;

	if(fa[y])tr[fa[y]][ge(y)]=x;fa[x]=fa[y];

	fa[y]=x;tr[x][o^1]=y;

	if(tr[y][o])pushup(tr[y][o]);pushup(y);pushup(x);

}

inline void add(int x,int y){

	h[x]+=y;la[x]+=y;

	pushup(x);

}

inline void pushdown(int x){

	if(la[x]){

		if(ls)add(ls,la[x]);

		if(rs)add(rs,la[x]);

		la[x]=0;

	}

}

void _pushdown(int x){

	if(fa[x])_pushdown(fa[x]);

	pushdown(x);

}

int build(int l,int r){

	if(l>r)return 0;

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

	ls=build(l,x-1);rs=build(x+1,r);

	if(ls)fa[ls]=x;if(rs)fa[rs]=x;

	size[x]=size[ls]+size[rs]+1;

	return x;

}

void dfs(int x){

	pushdown(x);

	if(ls)dfs(ls);

	cout<<x<<" "<<ls<<" "<<rs<<" "<<h[ls]<<" "<<h[rs]<<" "<<h[x]<<" "<<dp[x]<<endl;

	if(rs)dfs(rs);

}

int main(){

	n=rd();m=rd();num=rd();

	rot=build(1,m);

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

		int x,y;

		x=rd(),y=rd();

		vec[x].push_back(y);

	}

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

		add(rot,1);

		for(it=vec[i].begin();it!=vec[i].end();++it){

			int x=*it;

			_pushdown(x);

			while(fa[x])rotate(x);

			h[x]=0;

			if(ls)pushup(ls);if(rs)pushup(rs);

			pushup(x);

			rot=x;

		}

		ans+=dp[rot];

	}

	printf("%lld",calc(n)*calc(m)-ans);

	return 0;

}

巴特西

[ZJOI2012]小蓝的好友

题解

代码

最新文章

热门文章