BZOJ1095 动态点分治(点分树)

忘是亡心i 2023-10-10 07:52 61阅读 0赞

题意：

操作1.修改一个点的颜色（黑白互换）

操作2.询问所有黑色点之间最远距离

点分树：当我们可以形如点分治一样的统计答案，即每次确定一个重心，然后计算他们子树之间的贡献和得出答案的时候

我们可以将每个区域的重心作为其所有子树的重心的父亲，构成一颗新的树，显然这棵树的深度不会超过logn

每次对于单点（边）更新的时候，只要对其所有的父亲更新，就只需要更新log个点，这样的数据结构就是点分树

对于本题来说，最终的答案是在每个点作为链上一个点的时候，找每个点出发的最长链和次长链的和的最大值

所以用一个堆A维护每个点在点分树中子树下所有的点到这个点父亲的距离

再用一个堆B维护每个点所有儿子点的堆A的最大值，即每条链的最长的长度

最后用一个堆C维护每个点的最长值 + 次长值的大小

tips:

1.树上两两之间的点的距离可以rmq + ST表预处理之后O(1)查询，注意转化成序列不是dfs序，具体看代码

2.做一个供删除的优先队列，可以用两个优先队列A,B，一个正常用，删除操作就是把元素加入B，当AB顶部相同的时候一起弹出

#include <map>
    #include <set>
    #include <ctime>
    #include <cmath>
    #include <queue>
    #include <stack>
    #include <vector>
    #include <string>
    #include <bitset>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <sstream>
    #include <iostream>
    #include <algorithm>
    #include <functional>
    using namespace std;
    #define For(i, x, y) for(int i=x;i<=y;i++)  
    #define _For(i, x, y) for(int i=x;i>=y;i--)
    #define Mem(f, x) memset(f,x,sizeof(f))  
    #define Sca(x) scanf("%d", &x)
    #define Sca2(x,y) scanf("%d%d",&x,&y)
    #define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
    #define Scl(x) scanf("%lld",&x)  
    #define Pri(x) printf("%d\n", x)
    #define Prl(x) printf("%lld\n",x)  
    #define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
    #define LL long long
    #define ULL unsigned long long  
    #define mp make_pair
    #define PII pair<int,int>
    #define PIL pair<int,long long>
    #define PLL pair<long long,long long>
    #define pb push_back
    #define fi first
    #define se second 
    typedef vector<int> VI;
    int read(){
        int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){
        if (c == '-') f = -1;c = getchar();}
    while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}
    const double PI = acos(-1.0);
    const double eps = 1e-9;
    const int maxn = 2e5 + 10;
    const int INF = 0x3f3f3f3f;
    const int mod = 1e9 + 7; 
    int N,M,K;
    struct heap{
        priority_queue<int>A,B;
        void push(int x){A.push(x);}
        void del(int x){B.push(x);}
        void init(){
            while(!B.empty() && A.top() == B.top()){
                A.pop(); B.pop();
            }
        }
        int top(){
            init();
            if(A.empty()) return 0;
            return A.top();
        }
        int size(){
            return A.size() - B.size();
        }
        int Maxdis(){
            if(size() < 2) return 0;
            int x = top(); A.pop();
            int y = top(); A.push(x);
            return x + y;
        }
    };
    struct Edge{
        int to,next;
    }edge[maxn << 1];
    int head[maxn],tot;
    void init(){
        for(int i = 0 ; i <= N ; i ++) head[i] = -1;
        tot = 0;
    }
    void add(int u,int v){
        edge[tot].to = v;
        edge[tot].next = head[u];
        head[u] = tot++;
    }
    int dep[maxn];
    int id[maxn],pos[maxn],cnt;
    void dfsinit(int u,int la){
        id[++cnt] = dep[u];
        pos[u] = cnt;
        for(int i = head[u]; ~i ; i = edge[i].next){
            int v = edge[i].to;
            if(v == la) continue;
            dep[v] = dep[u] + 1;
            dfsinit(v,u);
            id[++cnt] = dep[u]; 
        }
    }
    const int SP = 20;
    int MIN[maxn][SP],mm[maxn];
    void initRMQ(int n,int b[]){
        for(int i = 1; i <= n ; i ++){
            for(int j = 0 ; j < SP; j ++){
                MIN[i][j] = INF;
            }
        }
        mm[0] = -1;
        for(int i = 1; i <= n; i ++){
            mm[i] = ((i & (i - 1)) == 0)?mm[i - 1] + 1:mm[i - 1];
            MIN[i][0] = b[i];
        }
        for(int j = 1; j <= mm[n]; j ++){
            for(int i = 1; i + (1 << j) - 1 <= n; i ++){
                MIN[i][j] = min(MIN[i][j - 1],MIN[i + (1 << (j - 1))][j - 1]);
            }
        }
    }
    int rmq(int x,int y){
        if(x > y) swap(x,y);
        int k = mm[y - x + 1];
        return min(MIN[x][k],MIN[y - (1 << k) + 1][k]);
    }
    int getdis(int x,int y){
        return dep[x] + dep[y] - 2 * rmq(pos[x],pos[y]);
    }
    struct dtnode{
        int fa;
        heap Q,P;
        int Maxdis(){
            return Q.top();
        }
        int Maxline(){
            return P.Maxdis();
        }
    }dt[maxn];
    heap fans;
    int root,max_part,SUM;
    int size[maxn],vis[maxn];
    int dis[maxn];
    void dfs_root(int u,int la){
        size[u] = 1; int heavy = 0;
        for(int i = head[u]; ~i ; i = edge[i].next){
            int v = edge[i].to;
            if(v == la || vis[v]) continue;
            dfs_root(v,u);
            heavy = max(heavy,size[v]);
            size[u] += size[v];
        }
        if(max_part > max(heavy,SUM - heavy)){
            max_part = max(heavy,SUM - heavy);
            root = u;
        }
    }
    void dfs(int u,int la){
        dis[u] = getdis(u,dt[root].fa);
        dt[root].Q.push(dis[u]);
        for(int i = head[u]; ~i ; i = edge[i].next){
            int v = edge[i].to;
            if(v == la || vis[v]) continue;
            dfs(v,u);
        }
    }
    int divide(int t,int la){
        max_part = INF;
        root = t; 
        dfs_root(t,-1); 
        int now = root;
        dt[root].fa = la; dt[root].P.push(0);
        if(~la) dfs(root,-1);
        vis[root] = 1;
        for(int i = head[now]; ~i ; i = edge[i].next){
            int v = edge[i].to;
            if(vis[v]) continue;
            SUM = size[v];
            v = divide(v,now);
            dt[now].P.push(dt[v].Maxdis());
        }
        if(dt[now].P.size() >= 2)fans.push(dt[now].Maxline());
        return now;
    }
    int use[maxn];
    int main(){
        Sca(N); init();
        for(int i = 1; i < N ; i ++){
            int u = read(),v = read();
            add(u,v); add(v,u);
        }
        dfsinit(1,-1); initRMQ(cnt,id);
        SUM = N; divide(1,-1);
        int num = N;
        Sca(M);
        while(M--){
            char op[3]; scanf("%s",op);
            if(op[0] == 'G'){
                if(num == 1) puts("0");
                else if(!num) puts("-1");
                else{
                    Pri(fans.top());
                }    
            }else{
                int v = read(); int tmp = v;
                if(use[v]) num++;
                else num--;
                if(dt[v].P.size() >= 2) fans.del(dt[v].Maxline());
                if(use[v]) dt[v].P.push(0);
                else dt[v].P.del(0);
                if(dt[v].P.size() >= 2) fans.push(dt[v].Maxline());
                while(~dt[tmp].fa){
                    int u = dt[tmp].fa;
                    if(dt[u].P.size() >= 2) fans.del(dt[u].Maxline());
                    if(dt[tmp].Q.size()) dt[u].P.del(dt[tmp].Maxdis());
                    int d = getdis(v,u);
                    if(use[v]) dt[tmp].Q.push(d);
                    else dt[tmp].Q.del(d);
                    if(dt[tmp].Q.size()) dt[u].P.push(dt[tmp].Maxdis());
                    if(dt[u].P.size() >= 2) fans.push(dt[u].Maxline());
                    tmp = u;
                }
                use[v] ^= 1;
            }
        }
        return 0;
    }

转载于:https://www.cnblogs.com/Hugh-Locke/p/11530003.html