P3201 [HNOI2009] 梦幻布丁题解

题意

给定一个长度为 n 的序列，其中所有连续且相同的数字为一个“段”，完成以下操作：

1 x y：把序列中所有 x 变为 y。
2：询问整个序列中有多少“段”。

思路

对于这类不可逆的合并操作，容易想到用线段树合并解决。

很明显我们可以对每一种数字开一棵线段树(动态开点)，每一个线段树的节点储存三个信息：sum(“段”数)，lz(当前数字在当前区间内最靠左的一个数的下标)，rz(当前数字在当前区间内最靠右的一个数的下标)。此时，当两个子节点上放(pushup)到父节点时，就可以通过判断左儿子的 lz 与右儿子的 rz 是否只相差1(是否可合并为一个“段”)，来对 sum 进行适当修改，具体实现如下：

CPP

void pushup(int u){
	tr[u].sum=tr[lc[u]].sum+tr[rc[u]].sum;
	if(tr[lc[u]].rz+1==tr[rc[u]].lz)tr[u].sum--;
	tr[u].lz=tr[lc[u]].lz?tr[lc[u]].lz:tr[rc[u]].lz;//由于是动态开点,需要特判,下同
	tr[u].rz=tr[rc[u]].rz?tr[rc[u]].rz:tr[lc[u]].rz;
}
将 x 变为 y 时，只需将 x的线段树 合并到 y的线段树 上就行了。

而在每次进行修改时，要将 ans 带着一起改，因为这里每种数字都开了一个线段树，无法一次性统计答案。而 ans 的修改其实只需在修改前减去当前修改颜色的修改前的“段”数，在修改后再加上当前修改颜色的修改后的“段”数就行了(合并操作时两个都要减)。

完整代码

以下代码省略了前文的pu部分：

CPP

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+5;
struct segment{
	#define mid ((l+r)>>1)
	struct tree{int sum,lz,rz;}tr[N<<5];
	int n,cnt,root[N<<3],lc[N<<5],rc[N<<5];
	void pushup(int u){...}
	void update(int &u,int l,int r,int pos){
		if(!u)u=++cnt;
		if(l==r){tr[u]={1,l,l};return ;}
		if(pos<=mid)update(lc[u],l,mid,pos);
		else update(rc[u],mid+1,r,pos);
		pushup(u);
	}void update(int x,int pos){
		return update(root[x],1,n,pos);}
	int merge(int x,int y,int l,int r){
		if(!x||!y)return x|y;
		if(l==r)tr[x]={1,l,l};
		lc[x]=merge(lc[x],lc[y],l,mid);
		rc[x]=merge(rc[x],rc[y],mid+1,r);
		pushup(x);return x;
	}void merge(int x,int y){
		root[x]=merge(root[x],root[y],1,n),root[y]=0;}
	int get(int x){return tr[root[x]].sum;}
}tree;
int n,m,ans;
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m,tree.n=n;
	for(int i=1,x;i<=n;i++){
		cin>>x;
		ans-=tree.get(x);
		tree.update(x,i);
		ans+=tree.get(x);
	}
	for(int op,x,y;m--;){
		cin>>op;
		if(op==1){
			cin>>x>>y;
			if(x==y)continue;
			ans-=tree.get(x)+tree.get(y);
			tree.merge(y,x);
			ans+=tree.get(y);
		}else cout<<ans<<"\n";
	}
	return 0;
}

AC记录

P3201 [HNOI2009] 梦幻布丁题解

文章操作

题意

思路

完整代码

相关推荐

评论

P3201 [HNOI2009] 梦幻布丁题解