Description

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

树上，每个结点都有一样食材，Shimakaze要考验一下她。

每个食材都有一个美味度，Shimakaze会进行两种操作：

1、修改某个结点的食材的美味度。

2、对于某条链，询问这条链的美味度集合中，最小的未出现的自然数是多少。即mex值。

请你帮帮Haruna吧。

Solution

树上带修改莫队

统计答案的时候也分块查询，找到第一个没满的块开始一个一个找

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define MAXN 50005using 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
           
            =block) { ++tot3; while(top!=now)belong[stack[top--]]=tot3; } } stack[++top]=u;}void init(){ for(int i=1;(1<
            
             <=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<
             
              <=f;i++) if(f&(1<
              
               =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