A simple Blog for wyx I've been down the bottle hoping.
BZOJ 1095 捉迷藏 动态点分治 好题
发表于: | 分类: Oi | 评论:0 | 阅读:188

这题真是好题……Orz浙江省选九年之前的题都这么新颖……
首先这个东西是点分治,应该没什么问题
然后我们一共维护三个堆
第一个堆大概是这样的,我们把分治中心按层连在一起,然后为了方便查询信息,我们把所有对于上一分治中心但是在这个分治中心的部分都存在这个分治中心里,但是值还是对于上一个分治中心的
第二个堆维护一下下层分治中心的第一个堆得堆顶
第三个堆维护一下全局的答案

显然对于一个分治中心来说,他第二个堆存的最大值和次大值的加和就是答案了
这样我们的预处理就做完了

然后思考如何进行修改
我们可以沿着分治中心的那棵树向上走
然后每次把所有有关原来信息但是现在改变信息的量全都删掉
然后把这个东西插进去,然后按照刚才删除的倒序再插回来
然后接着往上翻,由于这颗树最多只有$log$层,每次修改的时候复杂度是$log$,乘上堆得复杂度摊下来是个$log^2$
堆需要支持删除操作

支持删除操作的堆可以搞两个堆,然后每次删除元素就直接扔到第二个堆里面,查询和弹堆得话看一下两个堆得堆顶是否相同,如果相同就删除两个,否则就直接返回堆顶就行了

理论上事情到这就结束了
但是实际上并没有
我们刚才的操作只操作出了一种操作,就是过这个点的操作
但是还有一种情况没有处理,如果上一个分治中心就这么GG了其实我们少了一种情况就是他作为一个端点,然后这个答案还在堆里面
大概是这个数据

5
1 2
2 3
3 4
4 5
10
C 5
G
C 4
G
C 3
G
C 2
G
C 1
G

然后你就GG了

应对这个的方式也非常简单,每次他从白色变成黑色的时候就插入一个0进去,如果是逆操作就删除一个0出来
这个做法多优雅

然后还有几个点可以注意下

有人说这个东西复杂度如果每次倍增求复杂度不优雅,所以转rmq求Lca然后再求距离//其实蒟蒻我早就忘了欧拉序求Lca咋写了,所以我就直接倍增了2333333

#include <queue>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
const int N = 1e5+5;
const int M = N << 1;
using namespace std;

bool vis[N];

struct data{
    priority_queue <int> q,Del;

    void insert(int x){
        q.push(x);
    }

    void del(int x){
        Del.push(x);
    }

    void pop(){
        while(!Del.empty() && !q.empty() && Del.top() == q.top()) q.pop(), Del.pop();
        q.pop();
    }

    int top(){
        while(!Del.empty() && !q.empty() && Del.top() == q.top()) q.pop(),Del.pop();
        return q.top();
    }

    int sec(){
        int tt = top(); pop();
        int tt2 = top(); insert(tt);
        return tt2;
    }

    int sz(){
        return q.size() - Del.size();
    }
}s1[M],s2[M],ans;

void insert(data &z){
    if(z.sz() >= 2){
        int tmp = z.top() + z.sec();
        ans.insert(tmp);
    }
}

void del(data &z){
    if(z.sz() >= 2){
        int tmp = z.top() + z.sec();
        ans.del(tmp);
    }
}

int head[N];

struct graph{
    int next,to;
    graph () {}
    graph (int _next,int _to)
    :next(_next),to(_to){}
}edge[M];

inline void add(int x,int y){
    static int cnt = 0;
    edge[++cnt] = graph(head[x],y); head[x] = cnt;
    edge[++cnt] = graph(head[y],x); head[y] = cnt;
}

inline int read(){
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

int size[N],f[N],root,sum;
int fa[N][18],depth[N];

void DFS(int x){
    for(int i=head[x];i;i=edge[i].next)
        if(edge[i].to != fa[x][0]){
            fa[edge[i].to][0] = x;
            depth[edge[i].to] = depth[x] +1;
            DFS(edge[i].to);
        }
}

inline int lca(int x,int y){
    if(depth[x] < depth[y] ) swap(x,y);
    int tt = depth[x] - depth[y];
    for(int i=17;~i;--i) if((1<<i)&tt) x = fa[x][i];
    for(int i=17;~i;--i) if(fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
    return x == y ? x : fa[x][0];
}

inline int calc(int x,int y){
    return depth[x] + depth[y] - (depth[lca(x,y)]<<1);
}

void DFS1(int x,int fa){
    size[x] = 1, f[x] = 0;
    for(int i=head[x];i;i=edge[i].next)
        if(edge[i].to != fa && !vis[edge[i].to]){
            DFS1(edge[i].to,x); size[x] += size[edge[i].to];
            f[x] = max(f[x],size[edge[i].to]);
        }
    f[x] = max(f[x],sum - size[x]);
    if(f[x] < f[root]) root = x;
}

int dis[N];

void DFS2(int x,int fa,int belong){
    s1[belong].insert(dis[x]);
    for(int i=head[x];i;i=edge[i].next)
        if(edge[i].to != fa && !vis[edge[i].to]){
            dis[edge[i].to] = dis[x] + 1;
            DFS2(edge[i].to,x,belong);
        }
}

int last[N];

void solve(int x){
    vis[x] = 1; dis[x] = 0;
    s2[x].insert(0);
    for(int i=head[x];i;i=edge[i].next)
        if(!vis[edge[i].to]){
            dis[edge[i].to] = dis[x] + 1;
            root = 0, sum = size[edge[i].to];
            DFS1(edge[i].to,x); DFS2(edge[i].to,x,root);
            last[root] = x; s2[x].insert(s1[root].top());
            solve(root);
        }
    insert(s2[x]);
}

void on(int x){
    del(s2[x]);
    s2[x].insert(0);
    insert(s2[x]);
    for(int i=x;last[i];i=last[i]){
        del(s2[last[i]]);
        if(s1[i].sz()) s2[last[i]].del(s1[i].top());
        s1[i].insert(calc(last[i],x));
        if(s1[i].sz()) s2[last[i]].insert(s1[i].top());
        insert(s2[last[i]]);
    }
}

void off(int x){
    del(s2[x]);
    s2[x].del(0);
    insert(s2[x]);
    for(int i=x;last[i];i=last[i]){
        del(s2[last[i]]);
        if(s1[i].sz()) s2[last[i]].del(s1[i].top());
        s1[i].del(calc(last[i],x));
        if(s1[i].sz()) s2[last[i]].insert(s1[i].top());
        insert(s2[last[i]]);
    }
}

bool v[N];

int main(){// freopen("1095.in","r",stdin); freopen("1095.out","w",stdout);
    int n = read(); 
    for(int i=1;i<n;++i) add(read(),read());
    for(int i=1;i<=n;++i) v[i] = 1;
    DFS(1); root = 0; f[0] = 0x7fffffff; ::sum = n ;
    DFS1(1,0); int tmp = root; DFS1(root,0); 
    for(int j=1;j<=17;++j) for(int i=1;i<=n;++i) fa[i][j] = fa[fa[i][j-1]][j-1];
    solve(tmp);
//  for(int i=1;i<=n;++i) cout << last[i] << " ";
    int Q = read(); char str[10];
    int sum = n;
    while(Q--){
        scanf("%s",str);
        if(str[0] == 'C'){
            int x = read(); 
            if(v[x]) sum --, off(x), v[x] = false;
            else on(x), v[x] = true, sum ++;
        }
        else{
            if(sum <= 1) printf("%d\n",sum-1);
            else printf("%d\n",ans.top());
        }
    }
}


一个下午没白花……
感觉自己码力上升了不少

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP