[bzoj 4129]Haruna’s Breakfast

Haruna每天都会给提督做早餐！
这天她发现早饭的食材被调皮的 Shimakaze放到了一棵树上，每个结点都有一样食材，Shimakaze要考验一下她。 每个食材都有一个美味度，Shimakaze会进行两种操作：
1、修改某个结点的食材的美味度。 2、对于某条链，询问这条链的美味度集合中，最小的未出现的自然数是多少。即mex值。

这道题是一道树上带修莫队+权值分块的题目。建议做这题前先去做bzoj 3585。那其实我们发现这题也就多了一个树上莫队和带修，再注意一下细节，这道题就解决了。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
using namespace std;
struct node
{
    int x,y,next;
}a[110000];int len,last[110000];
void ins(int x,int y)
{
    len++;
    a[len].x=x;a[len].y=y;
    a[len].next=last[x];last[x]=len;
}
int n,m,cnt,b[51000],c[51000],t1[51000],t2[51000];
int belong[51000],bl[51000],br[51000],f[20][51000],bb[51000];
int ss,dep[51000],dfn[51000];
bool vv[51000];
struct que1
{
    int l,r,id,t,s;
}q[110000];
struct que2
{
    int p,nw,od;
}cg[51000];
void fk()
{
    int he=(int)sqrt(n);
    for(int i=1;i<=n;i++)
    {
        int bg=(i-1)/he+1;
        bb[i]=bg;
        if(bl[bg]==0)bl[bg]=i,br[bg-1]=i-1;
    }
    br[bb[n]]=n;
}
bool cmp1(que1 a,que1 b)
{
    if(belong[a.l]==belong[b.l])
    {
        if(dfn[a.r]==dfn[b.r])
        {
            if(a.t>b.t)return false;
            if(a.t<b.t)return true;
            return 0;
        }
        if(dfn[a.r]>dfn[b.r])return false;
        if(dfn[a.r]<dfn[b.r])return true;
    }
    if(belong[a.l]>belong[b.l])return false;
    if(belong[a.l]<belong[b.l])return true;
}
bool cmp2(que1 a,que1 b)
{
    if(a.id>b.id)return false;
    if(a.id<b.id)return true;
    return 0;
}
void dfs(int x)
{
    dfn[x]=++ss;
    for(int k=last[x];k;k=a[k].next)
    {
        int y=a[k].y;
        if(f[0][x]!=y)
        {
            f[0][y]=x;
            dep[y]=dep[x]+1;
            dfs(y);
        }
    }
}
int lca(int x,int y)
{
    if(dep[x]<dep[y])swap(x,y);
    for(int i=15;i>=0;i--)
    {
        if((dep[x]-dep[y])>=(1<<i))x=f[i][x];
    }
    if(x==y)return x;
    for(int i=15;i>=0;i--)
    {
        if(dep[x]>=(1<<i) && f[i][x]!=f[i][y])
        {
            x=f[i][x];y=f[i][y];
        }
    }
    return f[0][x];
}
void add(int x)
{
    if(x>n)return ;
    t1[x]++;
    if(t1[x]==1)t2[bb[x]]++;
}
void del(int x)
{
    if(x>n)return ;
    t1[x]--;
    if(t1[x]==0)t2[bb[x]]--;
}
void wy(int x)
{
    if(vv[x]==true){vv[x]=false,del(b[x]);}
    else {vv[x]=true,add(b[x]);}
}
void walk(int x,int d)
{
    if(vv[x]==true)
    {
        del(b[x]);add(d);
    }
    b[x]=d;
}
void change(int x,int y,int LCA)
{
    while(x!=LCA)wy(x),x=f[0][x];
    while(y!=LCA)wy(y),y=f[0][y];
}
int solve()
{
    int he;
    if(t1[0]==0)return 0;
    for(int i=1;i<=bb[n];i++)
    {
        if(t2[i]<=br[i]-bl[i]){he=i;break;}
    }
    for(int i=bl[he];i<=br[he];i++)
    {
        if(t1[i]==0)return i;
    }
    return n;
}
int main()
{
    len=0;memset(last,0,sizeof(last));
    memset(t1,0,sizeof(t1));
    memset(t2,0,sizeof(t2));
    memset(vv,false,sizeof(vv));
    int s1=0,s2=0;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&b[i]),c[i]=b[i];
    for(int i=1;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        ins(x,y);ins(y,x);
    }    
    fk();cnt=(int)pow(n,0.66666);
    dfs(1);
    for(int i=1;i<=n;i++)belong[i]=(dfn[i]-1)/cnt+1;
    for(int i=1;i<=15;i++)
    {
        for(int j=1;j<=n;j++)f[i][j]=f[i-1][f[i-1][j]];
    }
    for(int i=1;i<=m;i++)
    {
        int z,x,y;
        scanf("%d%d%d",&z,&x,&y);
        if(z==1)
        {
            if(belong[x]>belong[y])swap(x,y);
            s1++;
            q[s1].t=s2;q[s1].id=s1;
            q[s1].l=x,q[s1].r=y;
        }
        else
        {
            s2++;
            cg[s2].p=x;
            cg[s2].od=c[x];cg[s2].nw=y;
            c[x]=y;
        }
    }
    sort(q+1,q+s1+1,cmp1);
    int l=1,r=1,lr=0;
    for(int i=1;i<=s1;i++)
    {
        for(int j=lr+1;j<=q[i].t;j++)walk(cg[j].p,cg[j].nw);
        for(int j=lr;j>=q[i].t+1;j--)walk(cg[j].p,cg[j].od);
        change(l,q[i].l,lca(l,q[i].l));
        change(r,q[i].r,lca(r,q[i].r));
        int LCA=lca(q[i].l,q[i].r);
        wy(LCA);
        q[i].s=solve();
        wy(LCA);
        l=q[i].l,r=q[i].r,lr=q[i].t;
    }
    sort(q+1,q+s1+1,cmp2);
    for(int i=1;i<=s1;i++)printf("%d\n",q[i].s);
    return 0;
}