[文章目录]
Description
一棵树上，每个结点都有一样食材，每个食材都有一个美味度，Shimakaze会进行两种操作：
1、修改某个结点的食材的美味度。
2、对于某条链，询问这条链的美味度集合中，最小的未出现的自然数是多少。即mex值。请你帮帮Haruna吧。
1<=n<=5*10^4,1<=m<=5*10^4,0<=ai<=10^9
树上莫队+分块
将树分为块，每块直径不超过，对于每个询问，按照两端点所在块的编号排序，相同编号的按照时间从小到大排序。
用桶维护每个权值出现的次数，统计块内最小没出现的数，每次询问的时候扫所有的块即可。O(1)修改 O(√n)查询
复杂度
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 50100
int n,m,a[N],blo;
int head[N],to[N<<1],nxt[N<<1],cnt;
inline void add(int x,int y)
{
to[++cnt]=y;
nxt[cnt]=head[x];
head[x]=cnt;
}
int fa[N],dep[N],pos[N],rm[N<<1][20],tim,Log[N<<1];
int nb,bl[N],sta[N],top,siz[N];
void dfs(int x,int pre)
{
fa[x]=pre; dep[x]=dep[pre]+1; rm[pos[x]=++tim][0]=x;
for(int i=head[x];i;i=nxt[i]) if(to[i]!=pre)
{
dfs(to[i],x); rm[++tim][0]=x; siz[x]+=siz[to[i]];
if(siz[x]>=blo)
{
++nb; siz[x]=0;
while(top) bl[sta[top--]]=nb;
}
}
sta[++top]=x; siz[x]++;
}
int lca(int x,int y)
{
x=pos[x],y=pos[y]; if(x>y) swap(x,y);
int lo=Log[y-x+1];
return dep[rm[x][lo]] < dep[rm[y-(1<<lo)+1][lo]] ?
rm[x][lo] : rm[y-(1<<lo)+1][lo];
}
int chp[N],chb[N],cha[N];
struct node
{
int id,x,y,b1,b2,t;
node(){}
node(int _id,int _x,int _y,int _t)
{
id=_id,x=_x,y=_y,t=_t;
b1=bl[x],b2=bl[y];
}
bool operator <(const node &z)const {return b1==z.b1 ? (b2==z.b2 ? t<z.t : b2<z.b2) : b1<z.b1;}
}q[N];
int id,sb[N],lz[N],Siz,ans[N];
bool vis[N];
inline void add(int x){if(x<=n) lz[x/Siz]+=!sb[x],sb[x]++;}
inline void del(int x){if(x<=n) sb[x]--,lz[x/Siz]-=!sb[x];}
inline int getans()
{
int i=0; while(lz[i]==Siz) ++i;
i=i*Siz; while(sb[i]) ++i;
return i;
}
int main()
{
scanf("%d%d",&n,&m);
for(blo=1;blo*blo*blo<=n;++blo);
for(Siz=1;Siz*Siz<=n;++Siz);
blo=(blo-1)*(blo-1);
int i,j,x,y;
for(i=1;i<=n;++i) scanf("%d",a+i);
for(i=2;i<=n;++i)
{
scanf("%d%d",&x,&y);
add(x,y); add(y,x);
}
dfs(1,0);
if(top) {++nb; while(top) bl[sta[top--]]=nb;}
for(i=2;i<=tim;++i) Log[i]=Log[i>>1]+1;
for(i=1;i<=Log[tim];++i)
for(j=1;j+(1<<i)-1<=tim;++j)
rm[j][i]= dep[ rm[j][i-1] ] < dep[ rm[j+(1<<(i-1))][i-1] ] ?
rm[j][i-1] : rm[j+(1<<(i-1))][i-1];
// for(i=1;i<=n;++i)
// for(j=1;j<=n;++j)
// printf("%d%c",lca(i,j),j==n?'\n':' ');
int sw; tim=0;
for(i=1;i<=m;++i)
{
scanf("%d%d%d",&sw,&x,&y);
if(sw==0) ++tim,chp[tim]=x,chb[tim]=a[x],a[x]=cha[tim]=y;
else ++id,q[id]=node(id,x,y,tim);
}
sort(q+1,q+id+1); x=y=1; add(a[1]); vis[1]=1; int z;
for(i=1;i<=id;++i)
{
if(x!=q[i].x)
{
z=lca(x,q[i].x);
while(x!=z)
{
if(vis[fa[x]]) del(a[x]),vis[x]=0;
else add(a[fa[x]]),vis[fa[x]]=1;
x=fa[x];
}
for(x=q[i].x;x!=z;x=fa[x]) sta[++top]=x;
x=z;
while(top)
{
if(vis[sta[top]]) del(a[x]),vis[x]=0;
else add(a[sta[top]]),vis[sta[top]]=1;
x=sta[top--];
}
}
if(y!=q[i].y)
{
z=lca(y,q[i].y);
while(y!=z)
{
if(vis[fa[y]]) del(a[y]),vis[y]=0;
else add(a[fa[y]]),vis[fa[y]]=1;
y=fa[y];
}
for(y=q[i].y;y!=z;y=fa[y]) sta[++top]=y;
y=z;
while(top)
{
if(vis[sta[top]]) del(a[y]),vis[y]=0;
else add(a[sta[top]]),vis[sta[top]]=1;
y=sta[top--];
}
}
while(tim<q[i].t)
{
++tim;
if(vis[chp[tim]]) del(a[chp[tim]]),add(a[chp[tim]]=cha[tim]);
else a[chp[tim]]=cha[tim];
}
while(tim>q[i].t)
{
if(vis[chp[tim]]) del(a[chp[tim]]),add(a[chp[tim]]=chb[tim]);
else a[chp[tim]]=chb[tim];
--tim;
}
ans[q[i].id]=getans();
}
for(i=1;i<=id;++i) printf("%d\n",ans[i]);
return 0;
}