bzoj 4129: Haruna’s Breakfast （带修改树上莫队+分块）

Description

 Haruna每天都会给提督做早餐！ 这天她发现早饭的食材被调皮的 Shimakaze放到了一棵

Input

第一行包括两个整数n，m，代表树上的结点数(标号为1~n)和操作数。

Output

对于每次询问，输出该链的mex值。

Sample Input

Sample Output

HINT

1<=n<=5*10^4

Source

题解：带修改树上莫队+分块

带修改的树上莫队基本上框架都相似，可以参照WC糖果公园。

对于这个题要维护mex，我们可以将权值离线(注意不只是出现过的权值，还有每个出现过的权值+1和0),然后对权值进行分块，维护一个块中的值是否都出现了。在查询的时候可以用O(sqrt(n))的时间进行查询，找到第一个未全部出现的块，暴力块中第一未出现的结点。

#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include<map>#define N 100003using namespace std;int n,m,top,st[N],vis[N],last[N],ans[N];int point[N],v[N],nxt[N],tot,deep[N],mi[20],fa[N][20],belong[N],block;int val[N],col[N],hp[N],bk[N],bl,cl,cnt,sz,num[N],num1,num2,dfsn[N];struct data{	int x,y,num;	int c,id,PRe,ti;}a[N],p[N],q[N];map<int,int> mp;void add(int x,int y){	tot++; nxt[tot]=point[x]; point[x]=tot; v[tot]=y;	tot++; nxt[tot]=point[y]; point[y]=tot; v[tot]=x;}int cmp(data a,data b){	if (belong[a.x]==belong[b.x]&&belong[a.y]==belong[b.y]) return a.ti<b.ti;	if (belong[a.x]==belong[b.x]) return dfsn[a.y]<dfsn[b.y];	return belong[a.x]<belong[b.x];}int dfs(int x,int f){	deep[x]=deep[f]+1; int size=0; dfsn[x]=++sz;	for (int i=1;i<=15;i++) {		if (deep[x]-mi[i]<0) break;		fa[x][i]=fa[fa[x][i-1]][i-1];	}	for (int i=point[x];i;i=nxt[i]) {		if (v[i]==f) continue;		fa[v[i]][0]=x;		size+=dfs(v[i],x);		if (size>=block) {			++cnt;			for (int j=1;j<=size;j++) belong[st[top--]]=cnt;			size=0;		}	}	st[++top]=x;	return size+1;}int lca(int x,int y){	if (deep[x]<deep[y]) swap(x,y);	int k=deep[x]-deep[y];	for (int i=0;i<=15;i++)	 if ((k>>i)&1) x=fa[x][i];	if (x==y) return x;	for (int i=15;i>=0;i--)	 if (fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];	return fa[x][0];}void reserve(int x){	if (!vis[x]) {		vis[x]=1;		num[col[x]]++;		if (num[col[x]]==1) a[bk[col[x]]].num++;	}	else {		vis[x]=0;		num[col[x]]--;		if (num[col[x]]==0) a[bk[col[x]]].num--;	}}void solve(int x,int y){	while (x!=y) {		if(deep[x]>deep[y]) reserve(x),x=fa[x][0];		else reserve(y),y=fa[y][0];	}}void change(int x,int c){	if (vis[x]) {		reserve(x);		col[x]=c;		reserve(x);		return;	}	col[x]=c;}int calc(){	for (int i=1;;i++) 	 if (a[i].num<a[i].y-a[i].x+1) {	 	for (int j=a[i].x;j<=a[i].y;j++)	 	 if (!num[j]) return hp[j];	 }}int main(){	freopen("a.in","r",stdin);	freopen("my.out","w",stdout);	scanf("%d%d",&n,&m);	for (int i=1;i<=n;i++) scanf("%d",&val[i]),last[i]=val[i],col[i]=val[i];	for (int i=1;i<n;i++) {		int x,y; scanf("%d%d",&x,&y);		add(x,y);	}	mi[0]=1;	for (int i=1;i<=17;i++) mi[i]=mi[i-1]*2;	block=pow(n,(double)2/3); int cl=n;	dfs(1,0);	for (int i=1;i<=m;i++) {		int opt,x,y; scanf("%d%d%d",&opt,&x,&y);		if (opt==0) {			p[++num1].x=x; p[num1].y=y; p[num1].pre=last[x];			last[x]=y; col[++cl]=y;		}		else {			q[++num2].x=x; q[num2].y=y; q[num2].id=num2; q[num2].ti=num1;			if (dfsn[x]>dfsn[y]) swap(q[num2].x,q[num2].y);		}	}	sort(col+1,col+cl+1);	cl=unique(col+1,col+cl+1)-col-1; 	if (col[1]!=0) col[++cl]=0; int t1=cl;	for (int i=1;i<=t1;i++) col[++cl]=col[i]+1;	sort(col+1,col+cl+1); 	cl=unique(col+1,col+cl+1)-col-1;	for (int i=1;i<=cl;i++) mp[col[i]]=i,hp[i]=col[i];	for (int i=1;i<=n;i++) col[i]=mp[val[i]];	bl=sqrt(cl);	for (int i=1;i<=cl;i++) {	   bk[i]=(i-1)/bl+1;	   if (a[bk[i]].x==0) a[bk[i]].x=i;	   a[bk[i]].y=i;    }	sort(q+1,q+num2+1,cmp);	for (int i=1;i<=q[1].ti;i++) change(p[i].x,mp[p[i].y]);	solve(q[1].x,q[1].y);	int t=lca(q[1].x,q[1].y);	reserve(t); 	ans[q[1].id]=calc();	reserve(t);	for (int i=2;i<=num2;i++) {		for (int j=q[i-1].ti+1;j<=q[i].ti;j++) change(p[j].x,mp[p[j].y]);		for (int j=q[i-1].ti;j>q[i].ti;j--) change(p[j].x,mp[p[j].pre]);		solve(q[i-1].x,q[i].x); solve(q[i-1].y,q[i].y);		int t=lca(q[i].x,q[i].y);		reserve(t); ans[q[i].id]=calc();		reserve(t);	}	for (int i=1;i<=num2;i++) printf("%d/n",ans[i]);}