题解 P2166 【Gty的超级妹子树】

muller · 2019-01-15 11:23:22 · 题解

分块吧！这题的分块不是给树分块，而是程序分块，就没了！

好像3操作数据里并没有，而且数据范围没道100000吧，所以直接水！

就是询问套套主席树，其他瞎搞，暴力+卡常就可以跑过了，非常开心吧！

然后要注意不能离散化，同时要当心有0

所以直接在0 - 2 ^ 30 搞一下即可！（chairman tree大法好）

这题好像和超级妹子树一样吧qwq

代码：

// luogu-judger-enable-o2
#include <bits/stdc++.h>
using namespace std;
const int N = 200005, M = (N << 1), P = (1 << 30);
int n, ecnt, val[N], to[M], nxt[M], fir[N];
template <class T> void cmax(T &x, T y) {x = x > y ? x : y;}
template <class T> void cmin(T &x, T y) {x = x < y ? x : y;}
template <class T> void rd(T &x) {
    char c = getchar(); int f = 1; x = 0;
    for (; !isdigit(c); c = getchar()) if (c == '-') f = -1;
    for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
    x *= f;
}
void ae(int u, int v) {to[++ecnt] = v; nxt[ecnt] = fir[u]; fir[u] = ecnt;}
namespace subtask1 {
    int ls[N * 60], rs[N * 60], size[N * 60], Rt[N], siz[N], dfn[N], idx = 0, tot = 0, ans = 0;
    struct Segment_Tree {
        #define mid (l + r >> 1)
        #define lc ls[rt]
        #define rc rs[rt] 
        void modify(int rt, int pre, int l, int r, int x) {
            size[rt] = size[pre] + 1;
            if (l == r) return; lc = ls[pre], rc = rs[pre];
            if (x <= mid) modify(lc = ++tot, ls[pre], l, mid, x);
            else modify(rc = ++tot, rs[pre], mid + 1, r, x);            
        }
        int query(int rt, int pre, int l, int r, int x) {
            if (l == r) return size[rt] - size[pre];
            if (x < mid) return size[rc] - size[rs[pre]] + query(lc, ls[pre], l, mid, x);
            return query(rc, rs[pre], mid + 1, r, x);
        }
    } T;
    void dfs(int u, int f) {
        int i; dfn[u] = ++idx, siz[u] = 1; T.modify(Rt[idx] = ++tot, Rt[idx - 1], 1, P, val[u]);
        for (i = fir[u]; i; i = nxt[i]) {
            int v = to[i];
            if (v != f) dfs(v, u), siz[u] += siz[v];
        }
    }
    void solve() {
        int Q; rd(Q); dfs(1, 0);
        while (Q--) {
            int opt, x, y; rd(opt); rd(x); rd(y); x ^= ans, y ^= ans;
            printf("%d\n", ans = T.query(Rt[dfn[x] + siz[x] - 1], Rt[dfn[x] - 1], 0, P, y));
        }
    }
};
namespace subtask2 {
    int fa[N], k, ans = 0;
    void dfs(int u, int f) {
        int i; fa[u] = f;
        for (i = fir[u]; i; i = nxt[i]) {
            int v = to[i];
            if (v != f) dfs(v, u); 
        }
    }
    void work(int u) {
        int i; ans += val[u] > k;
        for (i = fir[u]; i; i = nxt[i]) {
            int v = to[i];
            if (v != fa[u]) work(v);
        }
    }
    void solve() {
        int Q; rd(Q); dfs(1, 0);
        while (Q--) {
            int opt, x, y; rd(opt); rd(x); rd(y); x ^= ans, y ^= ans;
            if (!opt) ans = 0, k = y, work(x), printf("%d\n", ans);
            if (opt == 1) val[x] = y;
            if (opt == 2) val[++n] = y, fa[n] = x, ae(x, n);
        }
    }
}
int main() {
    int i; rd(n);
    for (i = 1; i < n; ++i) {
        int u, v; rd(u); rd(v);
        ae(u, v); ae(v, u);
    }
    for (i = 1; i <= n; ++i) rd(val[i]);
    if (n == 30000) subtask1 :: solve();
    else subtask2 :: solve();
    return 0;
}