Description
Haruna每天都会给提督做早餐！ 这天她发现早饭的食材被调皮的 Shimakaze放到了一棵
树上，每个结点都有一样食材，Shimakaze要考验一下她。
每个食材都有一个美味度，Shimakaze会进行两种操作：
1、修改某个结点的食材的美味度。
2、对于某条链，询问这条链的美味度集合中，最小的未出现的自然数是多少。即mex值。
请你帮帮Haruna吧。
Solution
树上带修改莫队
统计答案的时候也分块查询，找到第一个没满的块开始一个一个找
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #define MAXN 50005 using namespace std; int n,m,a[MAXN],head[MAXN],cnt=0,tot1=0,tot2=0,stack[MAXN],top=0; int block,block2,tot3=0,belong[MAXN],last[MAXN],deep[MAXN],p[MAXN][22]; int ans=0,res[MAXN],num[MAXN],vis[MAXN],sg[MAXN]; int read() { int x=0,f=1;char c=getchar(); while(c<'0'||c>'9'){ if(c=='-')f=-1;c=getchar(); } while(c>='0'&&c<='9'){ x=(x<<1)+(x<<3)+c-'0';c=getchar(); } return x*f; } struct Node1 { int next,to; }Edges[MAXN*2]; void addedge(int u,int v) { Edges[cnt].next=head[u]; head[u]=cnt; Edges[cnt++].to=v; } struct Node2 { int u,v,tim,id; Node2(int u=0,int v=0,int tim=0,int id=0):u(u),v(v),tim(tim),id(id){} bool operator < (const Node2& x) const { if(belong[u]==belong[x.u]) { if(belong[v]==belong[x.v]) return tim<x.tim; else return belong[v]<belong[x.v]; } else return belong[u]<belong[x.u]; } }query[MAXN]; struct Node3 { int pos,x,pre; Node3(int pos=0,int x=0,int pre=0):pos(pos),x(x),pre(pre){} }modify[MAXN]; void dfs(int u) { int now=top; for(int i=head[u];~i;i=Edges[i].next) { int v=Edges[i].to; if(v==p[u][0])continue; p[v][0]=u,deep[v]=deep[u]+1; dfs(v); if(top-now>=block) { ++tot3; while(top!=now)belong[stack[top--]]=tot3; } } stack[++top]=u; } void init() { for(int i=1;(1<<i)<=n;i++) { for(int j=1;j<=n;j++) p[j][i]=p[p[j][i-1]][i-1]; } } int lca(int a,int b) { if(deep[a]>deep[b])swap(a,b); int f=deep[b]-deep[a]; for(int i=0;(1<<i)<=f;i++) if(f&(1<<i))b=p[b][i]; if(a!=b) { for(int i=(int)log2(n);i>=0;i--) if(p[a][i]!=p[b][i])a=p[a][i],b=p[b][i]; a=p[a][0]; } return a; } void Xor(int pos) { if(a[pos]>n)return; int b=a[pos]/block2+1; if(vis[pos]) { num[a[pos]]--; if(!num[a[pos]])sg[b]--; } else { if(!num[a[pos]])sg[b]++; num[a[pos]]++; } vis[pos]^=1; } void change(int pos,int c) { if(vis[pos]) Xor(pos),a[pos]=c,Xor(pos); else a[pos]=c; } void move(int a,int b) { if(deep[a]>deep[b])swap(a,b); while(deep[a]!=deep[b])Xor(b),b=p[b][0]; while(a!=b){Xor(a),Xor(b);a=p[a][0],b=p[b][0];} } void work() { int u=1,v=1; for(int i=1;i<=tot1;i++) { for(int j=query[i-1].tim+1;j<=query[i].tim;j++) change(modify[j].pos,modify[j].x); for(int j=query[i-1].tim;j>query[i].tim;j--) change(modify[j].pos,modify[j].pre); if(u!=query[i].u)move(u,query[i].u),u=query[i].u; if(v!=query[i].v)move(v,query[i].v),v=query[i].v; int t=lca(u,v); Xor(t); int k=1; while(sg[k]==block2)k++; k=(k-1)*block2; while(num[k])k++; res[query[i].id]=k; Xor(t); } } int main() { memset(head,-1,sizeof(head)); n=read(),m=read(); block=pow(n,2.0/3),block2=sqrt(n); for(int i=1;i<=n;i++)last[i]=a[i]=read(); for(int i=1;i<n;i++) { int u=read(),v=read(); addedge(u,v);addedge(v,u); } dfs(1),init(); for(int i=1;i<=m;i++) { int opt=read(),x=read(),y=read(); if(opt)++tot1,query[tot1]=Node2(x,y,tot2,tot1); else modify[++tot2]=Node3(x,y,last[x]),last[x]=y; } sort(query+1,query+1+tot1); work(); for(int i=1;i<=tot1;i++)printf("%d\n",res[i]); return 0; }