题解 P2137 【Gty的妹子树】

· · 题解

Part0.题外话

总算搞出来这一道题了

从上午8:30做到下午2:30

饭都没吃

累死我了

不过想到明天能去买轻小说就敲开心

这篇题解是一边做饭一边写出来的

另外，窝的做法是目前(2019/2/15)所有题解内中最优复杂度

不知道还有没有神仙能够更快

Part1.前置知识

分块、分块、还有分块

好吧其实还有一个并查集

Part2.BB了那么久总算开始了

首先这一题的所谓「树分块」的做法是错误的，可以被菊花图卡掉

所以要换种方法分块

回答一个询问，就是把初始答案与每一个操作带来的影响所整合起来

到这一题上，假设窝们对于初始那棵树（没执行过任何一次修改操作的）进行一次dfs算出dfs序后

树上问题就成了序列问题

那么以u为根的子树所对应的区间就是[dfn[u] , dfn[u] + sz[u] - 1]

(dfn代表dfs序）

所以可以拿个数据结构来维护初始树

记T1为这个数据结构的单次查询复杂度，T2为构造复杂度

那接下来窝们只需要回答每一个修改操作对询问操作的影响了

第一个问题 操作1如何影响询问

操作1是一个点权修改

那它想影响一个询问，必须是修改这个子树里的点权

操作2是一个建一个新的子节点，他只需要在这棵子树里建的就会影响了

综上，我们现在得到的思路是这样的

先用一个数据结构维护初始状态，接着对于每一个询问，扫一次它前面所有的修改操作，如果发现能够影响答案，那就将答案改变

但这样复杂度是不对的，因为这和暴力没什么区别

要不我们每T次操作之后，将初始状态提前一次？

你可能没有理解这句话，就是说每T次操作之后，我们把执行T次操作得到的新树作为新的初始状态

换句话来说，每T次操作，重新dfs+建数据结构一次

这个时候你就发现，每一次询问往后面扫的不是M次了，而是M/T次

你很聪明知道T应该取 \sqrt{M}

综上，我们要实现的操作只剩下两个了

1.写一个数据结构能够维护区间rank（就是区间[l,r]有多少个比c大）

2.判断一个点是否在一个子树中

看到1窝们就想到主席树，2的话因为有修改，我们可以用倍增

瓶颈在于倍增与主席树的构造上 主席树构造时间复杂度是$O(N * \log N)$，一共要暴力构造$\sqrt{M}$次。时间复杂度$O(N * \log N * \sqrt{M})

由于对于每一个询问操作我们都要往前扫\sqrt{M}个修改并且每个修改花\log N的时间倍增，最后再加上一个主席树\log N查询。

每一次询问的复杂度是O(\log N * \sqrt{M} + \log N)

总复杂度 O(M * (\log N * \sqrt{M} + \log N))

极大的复杂度不平衡。

为什么一定要倍增呢？

路径压缩难道忘了吗？

均摊复杂度分析难道忘了吗？

我们将倍增换成加了路径压缩的暴力，再配合一下欧拉序

均摊分析一下复杂度

不就成了O(M * \sqrt{N})了吗

再把主席树换成一个块内维护有序的分块，构造时间为O(N * \log{\sqrt{N}})

总复杂度为O(N * \sqrt{M} * \log{\sqrt{N}})

还有许多小细节，可以看看代码

Part3. Code

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<cstring>
using namespace std;

const int MAXN = 60000 + 5;

vector <int> G[MAXN];

int n , m , num , f[MAXN] , sz[MAXN] , val[MAXN] , dfn[MAXN] , tp[MAXN];
int real_node , all_node;

namespace DFS{
    int dfs_clock , st[MAXN] , ed[MAXN];
    void dfs(int u , int fa) {
        sz[u] = 1 , f[u] = fa , dfn[u] = num++ , st[u] = ++dfs_clock; 
        for(int i = 0 , v ; i < (int)G[u].size() ; ++i) {
            if((v = G[u][i]) == fa) continue;
            dfs(v , u);
            sz[u] += sz[v];
        }
        ed[u] = ++dfs_clock;
    }
    inline bool check(int u , int v) { //节点v是否在以u为根的子树中 
        return st[u] <= st[v] && ed[v] <= ed[u];
    }
    void rebuild() {
        num = dfs_clock = 0;
        dfs(1 , 0);
    }
} 

namespace BLOCK{
    int SIZE , j , cnt , A[MAXN] , b[MAXN] , ord[MAXN / 100][MAXN / 100];
    void rebuild() {
        for(int i = 0 ; i < cnt ; ++i) memset(ord[i] , 0 , sizeof ord[i]);
        memset(ord[cnt] , 0 , sizeof ord[cnt]);
        SIZE = (int)sqrt(all_node + 0.5);
        j = 0 , cnt = 0;
        for(int i = 1 ; i <= all_node ; ++i) A[dfn[i]] = val[i];
        for(int i = 0 ; i < all_node ; ++i) {
            if(j == SIZE) j = 0 , ++cnt; 
            ord[cnt][j] = A[i] , b[i] = cnt;
            ++j;
        }
        for(int i = 0 ; i < cnt ; ++i) sort(ord[i] , ord[i] + SIZE);
        sort(ord[cnt] , ord[cnt] + j);
    }
    int query(int l , int r , int c) {
        int lb = b[l] , rb = b[r] , res = 0;
        if(lb == rb) {
            for(int i = l ; i <= r ; ++i) if(A[i] > c) ++res;
            return res;
        }
        for(int i = l ; i < (lb + 1) * SIZE ; ++i) if(A[i] > c) ++res;
        for(int i = rb * SIZE ; i <= r ; ++i) if(A[i] > c) ++res;
        for(int i = lb + 1 ; i < rb ; ++i) res += ord[i] + SIZE - upper_bound(ord[i] , ord[i] + SIZE , c);
        return res;
    }
}

struct Node{
    int opt , u , x , lst;
    Node(int opt = 0 , int u = 0 , int x = 0 , int lst = 0) : opt(opt) , u(u) , x(x) , lst(lst) {}
};
vector <Node> v;

inline int real(int u) {return u <= real_node;} 
inline int Get(int v) {
    if(real(f[v])) return f[v];
    return tp[v] = Get(f[v]);
}
inline bool check(int u , int v) {
    if(real(u) ^ real(v)) {
        if(real(v) == 1) return false;
        if(!tp[v]) tp[v] = Get(v);
        return DFS::check(u , tp[v]);
    }
    else {
        if(real(u) == 1) return DFS::check(u , v);
        while(!real(f[v])) {
            if(v == u) return true;
            v = f[v];
        }
        return v == u;
    }
}

int main() {
    int last_ans = 0;
    scanf("%d" , &n);
    for(int i = 1 , u , vv ; i < n ; ++i) {
        scanf("%d %d" , &u , &vv);
        G[u].push_back(vv); G[vv].push_back(u);
    }
    for(int i = 1 ; i <= n ; ++i) scanf("%d" , val + i);
    real_node = all_node = n;
    DFS::rebuild();
    BLOCK::rebuild();
    scanf("%d" , &m);int SIZE = (int)sqrt(m + 0.5) + 1 , j = 0;
    while(m--) {
        int opt , u , x;
        scanf("%d %d %d" , &opt , &u , &x);
        if(j == SIZE) {
            memset(tp , 0 , sizeof tp);
            for(int i = 0 ; i < (int)v.size() ; ++i) 
                if(v[i].opt == 2) G[v[i].lst].push_back(++real_node);
            DFS::rebuild(); BLOCK::rebuild();
            v.clear();
            j = 0;
        }
        u ^= last_ans , x ^= last_ans;
        if(opt == 0) {
            int ans = BLOCK::query(dfn[u] , dfn[u] + sz[u] - 1 , x);
            for(int i = 0 ; i < (int)v.size() ; ++i) {
                if(check(u , v[i].u)) {
                    if(v[i].opt == 1) {
                        if(v[i].lst > x && v[i].x <= x) --ans;
                        if(v[i].lst <= x && v[i].x > x) ++ans;
                    }
                    if(v[i].opt == 2)
                        ans += v[i].x > x;
                }
            }
            printf("%d\n" , last_ans = ans); 
        }
        else if(opt == 1) {
            v.push_back(Node(opt , u , x , val[u]));
            val[u] = x;
        }
        else {
            v.push_back(Node(opt , ++all_node , x , u));
            val[all_node] = x; f[all_node] = u;
        }
        ++j;
    }
    return 0;
}