BZOJ 1095 ZJOI 2007 Hide 捉迷藏 動态點分治

動态點分治？

就是記憶體卡的很緊？用了154MB。。。

第一次寫參考了PoPoQQQ大爺的代碼。

而做到改查就需要依賴資料結構，本題詢問最遠距離，即對于某個根節點的兩子樹的最遠距離，如果我們能同時維護子樹内離根最遠的黑點的距離和根的兩個子樹且最遠距離在子樹間最大，即最大和次大值，問題就很好辦了。可以為每個點造2個堆 h1 和 h2 ，分别維護子樹内各點到根的距離和子樹中 h1 的最大值。

那麼最終答案就是每個點的 h2 的最大值和次大值的和的最大值。

對于動态修改，如果是關燈，對于本點的 h2 多加一個0，然後由于本點的該邊隻會影響其祖先，是以維護其到根的路徑上的點的 h1 ，即添加該點到本點的距離。開燈相反。

在維護堆的時候需要同時維護依賴其維護值的其他堆以保證答案的實時性。

然後這麼維護的話樹的形态不好會導緻單次修改的複雜度退化為 O(nlogn) ，由于我們不在意确切的路徑怎麼走，隻關心某個點和其他黑點間的距離，是以預處理出各點間距，點間的連邊便對我們要維護的值無影響了。

原因是我們始終維護的是【子樹内的點】，而不是【邊】，也就是說，我們劃定了一些點，其資料被其他的點所維護，。然後子樹内的點是什麼，不影響最終答案，不妨特别地構造一棵樹，使樹高為 O(logn) ，這樣複雜度就限定為 O(log2n) ，而點分治完全符合我們的需求，在利用的重心間建立連接配接的樹的形态下預處理出所有堆的值，保證複雜度。

最終複雜度 O(nlog2n)

#include <queue>
#include <cstdio>
#include <algorithm>
#define FOR(i,j,k) for(i=j;i<=k;++i)
const int N = , M = N * ;
using namespace std;

struct Heap {
    priority_queue<int> h, d;
    void add(int x) { h.push(x); }
    void del(int x) { d.push(x); }
    void chg(int x, int f) { if (f) add(x); else del(x); }
    void fix() { while (d.size() && h.top() == d.top()) h.pop(), d.pop(); }
    void pop() { fix(); h.pop(); }
    int fir() { fix(); return h.top(); }
    int sec() { int a, b; a = fir(); pop(); b = fir(); add(a); return b; }
    int sz() { return h.size() - d.size(); }
} s1[N], s2[N], ans;

int vis[M], p[M], v[M], h[N], fa[N], cnt = , node, rt;
int lb[M], dep[N], g[N], sz[N], pos[N], r[M][], id, light[N];
void add(int a, int b) {
    p[++cnt] = h[a]; v[cnt] = b; h[a] = cnt;
}
void root(int x, int fa) {
    sz[x] = ; g[x] = ;
    for (int i = h[x]; i; i = p[i])
        if (v[i] != fa && !vis[i]) {
            root(v[i], x);
            sz[x] += sz[v[i]];
            g[x] = max(g[x], sz[v[i]]);
        }
    g[x] = max(g[x], node - sz[x]);
    if (g[x] < g[rt]) rt = x;
}
int get_root(int x, int fa, int sz) {
    rt = ; node = sz; g[] = ;
    root(x, fa); return rt;
}
void dfs_seq(int x, int fa, int dep, Heap &s) {
    s.add(dep);
    for (int i = h[x]; i; i = p[i])
        if (!vis[i] && v[i] != fa)
            dfs_seq(v[i], x, dep + , s);
}
void add(Heap &s) { if(s.sz() >= ) ans.add(s.fir() + s.sec()); }
void del(Heap &s) { if(s.sz() >= ) ans.del(s.fir() + s.sec()); }
void work(int x) {
    s2[x].add();
    for (int i = h[x]; i; i = p[i])
        if (!vis[i]) {
            vis[i] = vis[i ^ ] = true;
            Heap s;
            dfs_seq(v[i], , , s);
            int cg = get_root(v[i], x, sz[v[i]]);
            fa[cg] = x; s1[cg] = s;
            s2[x].add(s1[cg].fir());
            work(cg);
        }
    add(s2[x]);
}
void dfs_seq(int x,int fa) {
    r[++id][] = dep[x] = dep[fa] + ; pos[x] = id;
    for (int i = h[x]; i; i = p[i])
        if (v[i] != fa) {
            dfs_seq(v[i], x);
            r[++id][] = dep[x];
        }
}
void init_rmq(int s) {
    int i, j;
    FOR(i,,s) lb[i] = lb[i >> ] + ;
    FOR(j,,lb[s]) FOR(i,,(s+-(<<j)))
        r[i][j] = min(r[i][j - ], r[i + ( << j - )][j - ]);
}
int rmq(int a, int b) {
    a = pos[a]; b = pos[b];
    if (a > b) swap(a, b);
    int t = lb[b - a + ];
    return min(r[a][t], r[b - ( << t) + ][t]);
}
int dis(int a, int b) {
    return dep[a] + dep[b] -  * rmq(a, b);
}
void turn(int x, int flag) {
    del(s2[x]); s2[x].chg(, flag); add(s2[x]);
    for (int i = x; fa[i]; i = fa[i]) {
        del(s2[fa[i]]);
        if (s1[i].sz()) s2[fa[i]].del(s1[i].fir());
        s1[i].chg(dis(fa[i],x), flag);
        if (s1[i].sz()) s2[fa[i]].add(s1[i].fir());
        add(s2[fa[i]]);
    }
}
int main() {
    int i, j, x, y, n, m, dark; char p[];
    scanf("%d", &n); dark = n;
    FOR(i,,n) scanf("%d%d", &x, &y), add(x, y), add(y, x);
    work(get_root(, , n));
    dfs_seq(,);
    init_rmq(id);
    scanf("%d", &m);
    FOR(i,,m) {
        scanf("%s", p);
        if (p[] == 'G')
            if (dark <= ) printf("%d\n", dark - );
            else printf("%d\n", ans.fir());
        else {
            scanf("%d",&x);
            turn(x, light[x]);
            light[x] ? ++dark : --dark;
            light[x] = !light[x];
        }
    }
    return ;
}
           

1095: [ZJOI2007]Hide 捉迷藏

Description

捉迷藏 Jiajia和Wind是一對恩愛的夫妻，并且他們有很多孩子。某天，Jiajia、Wind和孩子們決定在家裡玩捉迷藏遊戲。他們的家很大且構造很奇特，由N個屋子和N-1條雙向走廊組成，這N-1條走廊的分布使得任意兩個屋子都互相可達。遊戲是這樣進行的，孩子們負責躲藏，Jiajia負責找，而Wind負責操縱這N個屋子的燈。在起初的時候，所有的燈都沒有被打開。每一次，孩子們隻會躲藏在沒有開燈的房間中，但是為了增加刺激性，孩子們會要求打開某個房間的電燈或者關閉某個房間的電燈。為了評估某一次遊戲的複雜性，Jiajia希望知道可能的最遠的兩個孩子的距離（即最遠的兩個關燈房間的距離）。 我們将以如下形式定義每一種操作： C(hange) i 改變第i個房間的照明狀态，若原來打開，則關閉；若原來關閉，則打開。 G(ame) 開始一次遊戲，查詢最遠的兩個關燈房間的距離。

Input

第一行包含一個整數N，表示房間的個數，房間将被編号為1,2,3…N的整數。接下來N-1行每行兩個整數a, b，表示房間a與房間b之間有一條走廊相連。接下來一行包含一個整數Q，表示操作次數。接着Q行，每行一個操作，如上文所示。

Output

對于每一個操作Game，輸出一個非負整數到hide.out，表示最遠的兩個關燈房間的距離。若隻有一個房間是關着燈的，輸出0；若所有房間的燈都開着，輸出-1。

Sample Input

8
1 2
2 3
3 4
3 5
3 6
6 7
6 8
7
G
C 1
G
C 2
G
C 1
G
           

Sample Output

4
3
3
4
           

HINT

對于100%的資料， N ≤100000, M ≤500000。