BZOJ4129 Haruna’s Breakfast

带修改树上莫队加分块-_-

带修改莫队：把修改和查询分别存起来，查询按x所在块为第一关键字，y所在块为第二关键字，时间为第三关键字排序，修改按时间排序，然后再扫查询的时候每次走完x和y再走时间，该更改的更改，该回滚的回滚，块的大小取n^(2/3)，复杂度为n^(5/3）

树上分块：维护一个栈，维护子树内没有块的点，深搜，回溯的时候压栈，当栈里元素大于块下界的时候分一块

树上莫队：刚开始使得L和R都在根，没有点在莫队里（-_-这个表述真蛋疼），假设要转移到x,y，设x和L的lca为l1，y和R的lca为l2，把x到l1，L到l1，y到l2，R到l2上的点的状态都取反（l1和l2不取反），然后把L,R设为x,y，把lca(L,R)的状态取反，记录解，再把lca(L,R)的状态取反

然后这道题再对答案分一下块，每次查询的时候从小到大，查这块满不满，不满就进块里查第一个没有的就好了

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<iomanip>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<bitset>
#include<map>
using namespace std;
#define MAXN 200010
#define MAXM 50010
#define ll long long
#define eps 1e-8
#define INF 1000000000
#define MOD 1000000007
struct vec{
	int to;
	int fro;
};
struct que{
	int x;
	int y;
	int t;
	int v;
};
struct ch{
	int x;
	int t;
	int v;
	int vv;
};
vec mp[MAXN];
int tai[MAXN],cnt;
int fa[MAXN][20],dep[MAXN];
int bel[MAXN],tot;
int a[MAXN],ta[MAXN];
int ans[MAXN];
que q[MAXN];
ch c[MAXN];
int st[MAXN],ed[MAXN],p[MAXN];
int ct[MAXN],tt[MAXN];
int L,R,wzh;
int n,m,Q,C;
int MX,SZ;
int tls[MAXN],tln,mx;
int s[MAXN],tp;
bool vis[MAXN];
map<int,int>h;
int g[MAXN];
bool operator <(que x,que y){
	return bel[x.x]!=bel[y.x]?bel[x.x]<bel[y.x]:bel[x.y]!=bel[y.y]?bel[x.y]<bel[y.y]:x.t<y.t;
}
bool operator <(ch x,ch y){
	return x.t<y.t;
}
inline void be(int x,int y){
	mp[++cnt].to=y;
	mp[cnt].fro=tai[x];
	tai[x]=cnt;
}
inline void bde(int x,int y){
	be(x,y);
	be(y,x);
}
void dfs(int x){
	int i,t,y,j;
	dep[x]=dep[fa[x][1]]+1;
	int now=tp;
	for(i=tai[x];i;i=mp[i].fro){
		y=mp[i].to;
		if(!dep[y]){
			for(j=1,t=x;t;j++){
				fa[y][j]=t;
				t=fa[t][j];
			}
			dfs(y);
			if(tp-now>MX){
				tot++;
				while(tp>now){
					bel[s[tp--]]=tot;
				}
			}
		}
	}
	s[++tp]=x;
	if(x==1){
		tot++;
		while(tp){
			bel[s[tp--]]=tot;
		}
	}
}
int lca(int x,int y){
	int i;
	if(dep[x]<dep[y]){
		swap(x,y);
	}
	for(i=19;i;i--){
		if(dep[fa[x][i]]>=dep[y]){
			x=fa[x][i];
		}
	}
	for(i=19;i;i--){
		if(fa[x][i]!=fa[y][i]){
			x=fa[x][i];
			y=fa[y][i];
		}
	}
	return x==y?x:fa[x][1];
}
void del(int x){
	if(!--ct[x]){
		tt[p[x]]--;
	}
}
void add(int x){
	if(!ct[x]++){
		tt[p[x]]++;
	}
}
void rev(int x){
	if(vis[x]){
		del(a[x]);
		vis[x]=0;
	}else{
		add(a[x]);
		vis[x]=1;
	}
}
void change(int x,int y){
	if(vis[x]){
		del(a[x]);
		a[x]=y;
		add(a[x]);
	}else{
		a[x]=y;
	}
}
int cal(){
	int i;
	for(i=1;;i++){
		if(tt[i]!=ed[i]-st[i]+1){
			break;
		}
	}
	for(i=st[i];;i++){
		if(!ct[i]){
			return i;
		}
	}
}
int main(){
	int i,x,y,o;
	scanf("%d%d",&n,&m);
	MX=pow(1.0*n*n,1.0/3);
	tls[++tln]=0;
	for(i=1;i<=n;i++){
		scanf("%d",&a[i]);
		ta[i]=a[i];
		tls[++tln]=a[i];
		tls[++tln]=a[i]+1;
	}
	for(i=1;i<n;i++){
		scanf("%d%d",&x,&y);
		bde(x,y);
	}
	dfs(1);
	for(i=1;i<=m;i++){
		scanf("%d%d%d",&o,&x,&y);
		if(o==0){
			C++;
			c[C].x=x;
			c[C].t=i;
			c[C].v=y;
			c[C].vv=a[x];
			tls[++tln]=y;
			tls[++tln]=y+1;
			a[x]=y;
		}else{
			Q++;
			q[Q].x=x;
			q[Q].y=y;
			q[Q].t=i;
			q[Q].v=Q;
		}
	}
	for(i=1;i<=n;i++){
		a[i]=ta[i];
	}
	tls[0]=-1;
	sort(tls+1,tls+tln+1);
	for(i=1;i<=tln;i++){
		if(tls[i]!=tls[i-1]){
			h[tls[i]]=++mx;
			g[mx]=tls[i];
		}
	}
	SZ=sqrt(mx);
	for(i=1;i<=mx;i++){
		p[i]=(i-1)/SZ+1;
		if(!st[p[i]]){
			st[p[i]]=i;
		}
		ed[p[i]]=i;
	}
	for(i=1;i<=C;i++){
		c[i].v=h[c[i].v];
		c[i].vv=h[c[i].vv];
	}
	for(i=1;i<=n;i++){
		a[i]=h[a[i]];
	}
	sort(q+1,q+Q+1);
	sort(c+1,c+C+1);
	L=1,R=1;
	wzh=0;
	for(i=1;i<=Q;i++){
		int l1=lca(q[i].x,L);
		int l2=lca(q[i].y,R);
		for(x=L;x!=l1;x=fa[x][1]){
			rev(x);
		}
		for(x=q[i].x;x!=l1;x=fa[x][1]){
			rev(x);
		}
		for(x=R;x!=l2;x=fa[x][1]){
			rev(x);
		}
		for(x=q[i].y;x!=l2;x=fa[x][1]){
			rev(x);
		}
		L=q[i].x;
		R=q[i].y;
		int l=lca(L,R);
		rev(l);
		while(wzh<C&&c[wzh+1].t<=q[i].t){
			wzh++;
			change(c[wzh].x,c[wzh].v);
		}
		while(wzh&&c[wzh].t>=q[i].t){
			change(c[wzh].x,c[wzh].vv);
			wzh--;
		}
		ans[q[i].v]=cal();
		rev(l);
	}
	for(i=1;i<=Q;i++){
		printf("%d\n",g[ans[i]]);
	}
	return 0;
}

/*
5 1
4 4 4 3 3 
2 1
3 2
4 2
5 2
1 3 3


*/