bzoj4129 Haruna’s Breakfast 树上莫队+分块

Description

---

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

第一行包括两个整数n，m，代表树上的结点数(标号为1~n)和操作数。
第二行包括n个整数a1…an，代表每个结点的食材初始的美味度。
接下来n-1行，每行包括两个整数u，v，代表树上的一条边。
接下来m 行，每行包括三个整数
0 u x 代表将结点u的食材的美味度修改为 x。
1 u v 代表询问以u，v 为端点的链的mex值。

1<=n<=5*10^4
1<=m<=5*10^4
0<=ai<=10^9

Solution

---

终于学习到了树上分块的正确姿势，一开始还以为是各种可持久化数据结构

先求出树的括号序，对括号序分块然后排序，就是比较一般的待修改莫队了
求mex可以用权值线段树二分，然鹅由于莫队的特殊性可以考虑分块，这样修改和查询的复杂度不均衡就比较优秀了

码量略大

Code

---

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
#define rep(i,st,ed) for (int i=st;i<=ed;++i)
#define drp(i,st,ed) for (int i=st;i>=ed;--i)

const int N=100005;
const int E=200005;

struct Q {int l,r,x,lca,id,ans;} q[N];
struct C {int x,v;} c[N];
struct edge {int y,next;} e[E];

int ls[N],edCnt;
int fa[N][21],a[N],size;
int in[N],out[N],dep[N];
int dfn[N],qCnt,cCnt;
int bel[N],bct[N],rec[N];
int st[N],ed[N],n,m;

bool vis[N];

int read() {
    int x=0,v=1; char ch=getchar();
    for (;ch<'0'||ch>'9';v=(ch=='-')?(-1):(v),ch=getchar());
    for (;ch<='9'&&ch>='0';x=x*10+ch-'0',ch=getchar());
    return x*v;
}

void add_edge(int x,int y) {
    e[++edCnt]=(edge) {y,ls[x]}; ls[x]=edCnt;
    e[++edCnt]=(edge) {x,ls[y]}; ls[y]=edCnt;
}

void dfs(int now) {
    dfn[++dfn[0]]=now;
    in[now]=dfn[0]; bel[dfn[0]]=(dfn[0]-1)/size+1;
    rep(i,1,20) fa[now][i]=fa[fa[now][i-1]][i-1];
    for (int i=ls[now];i;i=e[i].next) {
        if (e[i].y==fa[now][0]) continue;
        dep[e[i].y]=dep[now]+1;
        fa[e[i].y][0]=now;
        dfs(e[i].y);
    }
    dfn[++dfn[0]]=now; bel[dfn[0]]=(dfn[0]-1)/size+1;
    out[now]=dfn[0];
}

int get_lca(int x,int y) {
    if (dep[x]<dep[y]) std:: swap(x,y);
    drp(i,20,0) if (dep[fa[x][i]]>=dep[y]) x=fa[x][i];
    if (x==y) return x;
    drp(i,20,0) if (fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
    return fa[x][0];
}

bool cmp1(Q a,Q b) {
    if (bel[a.l]<bel[b.l]) return true;
    if (bel[a.l]==bel[b.l]&&a.r<b.r) return true;
    if (bel[a.l]==bel[b.l]&&a.r==b.r&&a.x<b.x) return true;
    return false;
}

bool cmp2(Q a,Q b) {
    return a.id<b.id;
}

void modify(int x) {
    vis[x]^=1;
    if (a[x]>n) return ;
    if (vis[x]) {
        rec[bel[a[x]]]+=(++bct[a[x]]==1);
    } else {
        rec[bel[a[x]]]-=(--bct[a[x]]==0);
    }
}

void change(int x) {
    if (vis[c[x].x]) {
        modify(c[x].x);
        std:: swap(c[x].v,a[c[x].x]);
        modify(c[x].x);
    } else {
        std:: swap(c[x].v,a[c[x].x]);
    }
}

int query(int x) {
    rep(i,1,bel[dfn[0]]) if (rec[i]!=(ed[i]-st[i]+1)) {
        rep(j,st[i],ed[i]) if (!bct[j]) {
            return j-1;
        }
    }
}

int main(void) {
    freopen("data.in","r",stdin);
    freopen("myp.out","w",stdout);
    n=read(),m=read();
    rep(i,1,n) a[i]=read()+1;
    size=pow(1.0*n*n,1.0/3);
    rep(i,2,n) add_edge(read(),read());
    dep[1]=1; dfs(1);
    rep(i,1,n+1) {
        if (!st[bel[i]]) st[bel[i]]=i;
        ed[bel[i]]=i;
    }
    rep(i,1,m) {
        int opt=read(),x=read(),y=read();
        if (!opt) {
            c[++cCnt]=(C) {x,y+1};
            continue;
        }
        int lca=get_lca(x,y);
        if (lca==x||lca==y) q[++qCnt]=(Q) {std:: min(in[x],in[y]),std:: max(in[x],in[y]),cCnt,lca,qCnt,0};
        else {
            if (out[x]<in[y]) q[++qCnt]=(Q) {out[x],in[y],cCnt,lca,qCnt,0};
            else q[++qCnt]=(Q) {out[y],in[x],cCnt,lca,qCnt,0};
        }
    }
    std:: sort(q+1,q+qCnt+1,cmp1);
    for (int i=1,l=1,r=0,x=0;i<=qCnt;i++) {
        for (;r<q[i].r;) modify(dfn[++r]);
        for (;r>q[i].r;) modify(dfn[r--]);
        for (;l>q[i].l;) modify(dfn[--l]);
        for (;l<q[i].l;) modify(dfn[l++]);
        for (;x<q[i].x;) change(++x);
        for (;x>q[i].x;) change(x--);
        if (!vis[q[i].lca]) {
            modify(q[i].lca);
            q[i].ans=query(i);
            modify(q[i].lca);
        } else q[i].ans=query(i);
    }
    std:: sort(q+1,q+qCnt+1,cmp2);
    rep(i,1,qCnt) printf("%d\n", q[i].ans);
    return 0;
}