davidwang's Blog

首先改成待修该的树上莫队，然后就发现题目变成了一个要求维护一个集合，加入一个数字，修改一个数字(这两个操作要求O(1)完成)然后询问这个集合的mex值 $$ O(n^{2/3}) $$ 以内完成

然后我想了半天发现修改可以用树状数组，询问可以二分，然后这么又非常逗比的想到了分块大法好这样询问就是$$ O(n^{0.5}) $$ 了

//coder : davidwang
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <ctime>
#include <iostream>
using namespace std;
#define LL long long
#define LD long double
#define X first
#define Y second
inline int read()
{
    int ret=0,f=1; char ch;
    for (ch=getchar();ch>'9' || ch<'0';ch=getchar())
        if (ch=='-') f=-f;
    for (;'0'<=ch && ch<='9';ch=getchar())
        ret=ret*10+ch-'0';
    return ret*f;
}
const int N = 50010;
int start[N],to[N<<1],next[N<<1],cnt;
int stack[N],bel[N],dfn[N],p[N][20],d[N],fa[N],now,tot,top,col[N];
int a[N],vis[N],n,m,t1,t2;
int block[N],num[N],g[N],l[N],r[N],B,C,D;
int ans[N];
struct query{
	int x,y,t,pos;
	int operator < (const query &A) const {
		if (bel[x]!=bel[A.x]) return bel[x]<bel[A.x];
		if (bel[y]!=bel[A.y]) return bel[y]<bel[A.y];
		return t<A.t;
	}
}Q[N];
struct modify{
	int x,y,pre;
}A[N];
inline void connect(int x,int y){
	to[++cnt]=y; next[cnt]=start[x]; start[x]=cnt;
}
void dfs(int x){
	dfn[x]=++now;
	int bot=top;
	for (int p=start[x];p;p=next[p]){
		int &y=to[p];
		if (y==fa[x]) continue;
		fa[y]=x;  
		d[y]=d[x]+1;
		dfs(y);
		if (top-bot>B){
			tot++;
			while (top>bot) bel[stack[top--]]=tot;
			bel[stack[top--]]=tot;
		}
	}
	stack[++top]=x;
}
int init()
{
#ifndef ONLINE_JUDGE
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
#endif
	n=read(),m=read();
	for (int i=1;i<=n;i++) col[i]=a[i]=read();
	for (int i=1;i<n;i++){
		int x=read(),y=read();
		connect(x,y);
		connect(y,x);
	}
	B = pow(n,2.0/3),C=sqrt(n),D=(n+1)/C+((n+1)%C!=0);
	for (int i=0;i<D;i++){
		l[i]=i*C; r[i]=min(n,(i+1)*C-1);
	}
	d[1]=1;
	dfs(1); tot++;
	while (top) bel[stack[top--]]=tot;
	for (int i=1;i<=m;i++){
		int op=read(),x=read(),y=read();
		if (op==0){
			A[++t2].x=x;
			A[t2].y=y; A[t2].pre=col[x];
			col[x]=y;
		}else{
			t1++;
			if (dfn[x]>dfn[y]) swap(x,y);
			Q[t1].x=x; Q[t1].y=y;
			Q[t1].pos=t1; Q[t1].t=t2;
		}
	}
	sort(Q+1,Q+t1+1);
	for (int i=1;i<=n;i++) p[i][0]=fa[i];
	for (int j=1;j<20;j++)
		for (int i=1;i<=n;i++) p[i][j]=p[p[i][j-1]][j-1];
	return 0;
} 
inline int lca(int x,int y){
	if (d[x]<d[y]) swap(x,y);
	int j;
	while (d[x]>d[y]){
		for (j=1;d[p[x][j]]>=d[y];j++);
		x=p[x][j-1];
	}
	while (x!=y){
		for (j=1;p[x][j]!=p[y][j];j++);
		x=p[x][j-1],y=p[y][j-1];
	}
	return x;
}
inline void reverse(int x){
	if (vis[x]){
		vis[x]=0;
		if (a[x]>n) return;
		num[a[x]]--;
		if (num[a[x]]==0){
			g[a[x]/C]--;
		}
	}else{
		vis[x]=1;
		if (a[x]>n) return;
		num[a[x]]++;
		if (num[a[x]]==1){
			g[a[x]/C]++;
		}
	}
}
inline int getans(){

	for (int i=0;i<D;i++){
		if (g[i]==r[i]-l[i]+1) continue;
		for (int j=l[i];j<=r[i];j++){
			if (num[j]==0) return j;
		}
	}

//	for (int i=0;;i++) if (num[i]==0) return i;
	return n;
}
inline void change(int x,int y){
	if (vis[x]){
		reverse(x);
		a[x]=y;
		reverse(x);
	}else a[x]=y;
}
inline void solve(int x,int y){
	while (x!=y){
		if (d[x]>d[y]) reverse(x),x=fa[x];
		else reverse(y),y=fa[y];
	}
}
void work()
{
	for (int i=1;i<=Q[1].t;i++) change(A[i].x,A[i].y);
	solve(Q[1].x,Q[1].y); 
	int u=lca(Q[1].x,Q[1].y); 
	reverse(u); ans[Q[1].pos]=getans(); reverse(u);
	for (int i=2;i<=t1;i++){
		if (Q[i].t>Q[i-1].t) for (int j=Q[i-1].t+1;j<=Q[i].t;j++) change(A[j].x,A[j].y);
		if (Q[i].t<Q[i-1].t) for (int j=Q[i-1].t;j>Q[i].t;j--) change(A[j].x,A[j].pre);
		u=lca(Q[i].x,Q[i].y);
		solve(Q[i].x,Q[i-1].x);
		solve(Q[i].y,Q[i-1].y);
		reverse(u);
		ans[Q[i].pos]=getans();
		reverse(u);
	}
	for (int i=1;i<=t1;i++)
		printf("%d\n",ans[i]);
	return;
}
int main()
{
	init();
	work();
	return 0;
}