并不是普通的分块...

Problem

维护一棵初始有 n 个节点的有根树 (根节点为 1)，树上节点编号为 1 -n，每个点有一个权值 wi。

支持以下操作：

0 u x 询问以 u 为根的子树中，严格大于 x 的值的个数。(u^=lastans,x^=lastans)

1 u x 把 u 节点的权值改成 x。(u^=lastans,x^=lastans)

2 u x 添加一个编号为 "当前树中节点数 +1" 的节点，其父节点为 u，其权值为 x。(u^=lastans,x^=lastans)

最开始时 lastans=0。

Solution

暴力计算 $sqrt(m)$ 个更改对答案的贡献，这里要用到倍增。

若更改超过 $sqrt(m)$ 个，则重构区间树。

总复杂度 $O(n\sqrt{m} \log n)$。

参考：https://www.luogu.org/blog/Mr-Spade/solution-p2137

Code

// Code by ajcxsu
// Problem: girls tree


#include<bits/stdc++.h>
using namespace std;

template<typename T> inline void gn(T &x) {
    char ch=getchar();
    x=0;
    while(ch<'0' || ch>'9') ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
}

const int N=1e5+10, M=2e5+10;
int h[N], to[M], nexp[M], p=1;
inline void ins(int a, int b) { nexp[p]=h[a], h[a]=p, to[p]=b, p++; }

int dfn[N], siz[N], w[N], rw[N], nw[N], idx;
#define ls x<<1
#define rs x<<1|1
vector<int> seg[N*4];
void dfs1(int x) {
    dfn[x]=++idx, rw[idx]=w[x], siz[x]=1;
    for(int u=h[x];u;u=nexp[u])
        if(!dfn[to[u]]) dfs1(to[u]), siz[x]+=siz[to[u]];
}
void build(int x, int l, int r) {
    seg[x].clear();
    if(l==r) { seg[x].push_back(rw[l]); return; }
    int mid=(l+r)>>1;
    build(ls, l, mid), build(rs, mid+1, r);
    seg[x].resize(r-l+1); // important
    merge(seg[ls].begin(), seg[ls].end(), seg[rs].begin(), seg[rs].end(), seg[x].begin());
}
int query(int x, int l, int r, int xl, int xr, int v) {
    if(xl<=l && r<=xr) { return upper_bound(seg[x].begin(), seg[x].end(), v)-seg[x].begin(); }
    int mid=(l+r)>>1, ret=0;
    if(xl<=mid) ret+=query(ls, l, mid, xl, xr, v);
    if(xr>mid) ret+=query(rs, mid+1, r, xl, xr, v);
    return ret;
}

int chg[200];
int cp, rn, n, m;
void rebuild() {
    memset(dfn, 0, sizeof(dfn));
    for(int i=1;i<=cp;i++)
        w[chg[i]]=nw[chg[i]], nw[chg[i]]=0;
    idx=0;
    n=rn;
    dfs1(1);
    build(1, 1, n);
    cp=0;
}

const int OP=20;
int dep[N], gup[N][OP];
void dfs2(int x, int k) {
    dep[x]=k;
    for(int u=h[x];u;u=nexp[u])
        if(!dep[to[u]]) gup[to[u]][0]=x, dfs2(to[u], k+1);
}
void ad(int x, int fa) {
    dep[x]=dep[fa]+1, gup[x][0]=fa;
    for(int j=1;j<OP;j++)
        gup[x][j]=gup[gup[x][j-1]][j-1];
}
bool lca(int s, int t) {
    if(dep[s]<dep[t]) return false;
    for(int j=OP-1;j>=0;j--)
        if(dep[gup[s][j]]>=dep[t]) s=gup[s][j];
    return s==t;
}

int main() {
    int u, v;
    gn(n);
    for(int i=0;i<n-1;i++) gn(u), gn(v), ins(u, v), ins(v, u);
    for(int i=1;i<=n;i++) gn(w[i]);
    dfs1(1), dfs2(1, 1);
    build(1, 1, n);
    gn(m);
    for(int j=1;j<OP;j++)
        for(int i=1;i<=n;i++)
            gup[i][j]=gup[gup[i][j-1]][j-1];
    int unit=sqrt(m);
    int o, ans=0;
    rn=n;
    while(m--) {
        gn(o), gn(u), gn(v);
        u^=ans, v^=ans;
        if(o==0) {
            if(u<=n) ans=siz[u]-query(1, 1, n, dfn[u], dfn[u]+siz[u]-1, v);
            else ans=0;
            for(int i=1;i<=cp;i++)
                if(lca(chg[i], u)) {
                    if(w[chg[i]]>v && nw[chg[i]]<=v) ans--;
                    else if(w[chg[i]]<=v && nw[chg[i]]>v) ans++;
                }
            printf("%d\n", ans);
        }
        else if(o==1) {
            if(nw[u]) nw[u]=v;
            else chg[++cp]=u, nw[u]=v;
        }
        else if(o==2) {
            rn++;
            ad(rn, u), chg[++cp]=rn, nw[rn]=v;
            ins(u, rn), ins(rn, u);
        }
        if(cp>unit) rebuild();
    }
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-luogu-2137.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆