[BZOJ 4129]Haruna’s Breakfast：树上带修改莫队+分块

点击这里查看原题

依然好题，不过这题时限比糖果公园短很多，坑点是查询mex值的时候不能O(n)去查，会超时，因此需要sqrt(n)分块，记录每个块内是否每个值都有至少一个。

/*
User:Small
Language:C++
Problem No.:4129
*/
#include<bits/stdc++.h>
#define ll long long
#define inf 999999999
using namespace std;
const int M=50005;
int n,m,q,t,fir[M],tot,num[M],a[M],blk[M],l[250],r[250],lg[M],ans[M],pos[M],dfn[M],dep[M],anc[M][20],dfs_clock,stk[M],tp,res,cnt1,cnt2;
bool vis[M],g[250];
struct edge{
    int v,nex;
}e[M<<1];
struct change{
    int pos,x,y;
}cg[M];
struct query{
    int u,v,pre,id;
    bool operator<(const query &b)const{
        return pos[u]!=pos[b.u]?pos[u]<pos[b.u]:(pos[v]!=pos[b.v]?pos[v]<pos[b.v]:(pre!=b.pre?pre<b.pre:dfn[v]<dfn[b.v]));
    }
}qy[M];
void add(int u,int v){
    e[++tot]=(edge){v,fir[u]};
    fir[u]=tot;
}
int dfs(int u){
    int siz=0;
    dfn[u]=++dfs_clock;
    for(int i=1;i<=lg[dep[u]];i++)
        anc[u][i]=anc[anc[u][i-1]][i-1];
    for(int i=fir[u];i;i=e[i].nex){
        int v=e[i].v;
        if(v==anc[u][0]) continue;
        dep[v]=dep[u]+1;
        anc[v][0]=u;
        siz+=dfs(v);
        if(siz>=t){
            tot++;
            for(int j=1;j<=siz;j++) pos[stk[tp--]]=tot;
            siz=0;
        }
    }
    stk[++tp]=u;
    return siz;
}
int LCA(int u,int v){
    if(dep[u]<dep[v]) swap(u,v);
    int d=dep[u]-dep[v];
    for(int i=lg[d];i>=0;i--)
        if((d>>i)&1) u=anc[u][i];
    if(u==v) return u;
    for(int i=lg[n];i>=0;i--)
        if(anc[u][i]!=anc[v][i]) u=anc[u][i],v=anc[v][i];
    return anc[u][0];
}
void update(int pos){
    vis[pos]^=1;
    if(a[pos]>n) return;
    if(!vis[pos]){
        num[a[pos]]--;
        if(!num[a[pos]]) g[blk[a[pos]]]=0;
        if(!num[a[pos]]&&res>a[pos]) res=a[pos];
    }
    else{
        num[a[pos]]++;
        if(num[a[pos]]==1){
            int bk=blk[a[pos]];
            g[bk]=1;
            for(int i=l[bk];i<=r[bk];i++){
                if(!num[i]){
                    g[bk]=0;
                    break;
                }
            }
        }
        if(num[a[pos]]==1&&res==a[pos]){
            int bk=blk[a[pos]];
            while(g[bk]&&bk<=blk[n]) bk++;
            if(bk>blk[n]) res=n;
            else{
                for(int i=l[bk];i<=r[bk];i++){
                    if(!num[i]){
                        res=i;
                        break;
                    }
                }
            }
        }
    }
}
void chage(int pos,int x){
    if(vis[pos]){
        update(pos);
        a[pos]=x;
        update(pos);
    }
    else a[pos]=x;
}
void work(int u,int v){
    int lca=LCA(u,v);
    while(u!=lca){
        update(u);
        u=anc[u][0];
    }
    while(v!=lca){
        update(v);
        v=anc[v][0];
    }
}
void solve(){
    int now=cnt1;
    for(int i=1;i<=cnt2;i++){
        for(int j=now;j>qy[i].pre;j--) chage(cg[j].pos,cg[j].x);
        for(int j=now+1;j<=qy[i].pre;j++) chage(cg[j].pos,cg[j].y);
        work(qy[i-1].u,qy[i].u);
        work(qy[i-1].v,qy[i].v);
        int lca=LCA(qy[i].u,qy[i].v);
        update(lca);
        ans[qy[i].id]=res;
        update(lca);
        now=qy[i].pre;
    }
}
int main(){
    freopen("data.in","r",stdin);//
    scanf("%d%d",&n,&m);
    t=pow(n,2.0/3);
    int k=sqrt(n);
    for(int i=0;i<=n;i++){
        blk[i]=(i-1)/k+1;
        if(!l[blk[i]]&&blk[i]!=1) l[blk[i]]=i;
        r[blk[i]]=i;
    }
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<n;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v);
        add(v,u);
    }
    for(int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;
    tot=0;
    int rm=dfs(1);
    for(int i=1;i<=rm;i++) pos[stk[tp--]]=tot;
    for(int i=1;i<=m;i++){
        int typ,x,y;
        scanf("%d%d%d",&typ,&x,&y);
        if(typ) qy[++cnt2]=(query){x,y,cnt1,cnt2};
        else{
            cg[++cnt1]=(change){x,a[x],y};
            a[x]=y;
        }
    }
    sort(qy+1,qy+cnt2+1);
    qy[0]=(query){1,1,0,0};
    solve();
    for(int i=1;i<=cnt2;i++)
        printf("%d\n",ans[i]);
    return 0;
}