「BZOJ1095」「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

G
C 
G
C 
G
C 
G

Sample Output

HINT

對于 100% 的資料， N≤105,M≤5×105 。

題解

動态點分治。

首先處理出所有點到所有分治根節點的距離 dis[ dfn[i][j] ][ j ] ，按照 dfs 序插入到每個分治根節點對應的動态開點線段樹中。（這是為了友善查詢該節點屬于分治根節點的哪一個子樹）

然後對于每一個分治根節點 root ，經過該節點的路徑長度最大值為：

⎧⎩⎨⎪⎪0, open[i]=1,max1≤i<l[mx],r[mx]<i≤size[root]]{dis[i][rt]}=0max1≤i≤size[root]{dis[i][rt]}+max1≤i<l[mx],r[mx]<i≤size[root]]{dis[i][rt]}, otherwise

其中 mx 為最大值所處下标， l[x] 表示 x 所處子樹在 dfs 序上的左端點， r[x] 表示 x 所處子樹在 dfs 序上的右端點。

上式的意思是如果 rt 開着并且隻有一個子樹有關的燈，那麼就沒有路徑經過 rt 。其他情況就是以 rt 為分治根的子樹距離的最大值 + 不在該最大值節點所在子樹的節點距離的最大值。

然後修改 x 的時候就可以周遊所有的包含節點 x 的分治子樹的根節點，修改 x 線上段樹上的存在性（如果關燈則加入 x，開燈則删除 x ，即為講 x 所在的下标的值置為 −inf ），然後更新該分治根節點的答案。

查詢的時候可以再開一顆線段樹，存儲每個分治根節點的答案，單點修改，查詢 1∼n 的最大值（好像也可以用手寫堆）

複雜度 O((n+m)log22n) 。

My Code

代碼很長（共 8KB），寫的時候要注意細節和邊界情況。當然我的代碼有一些地方可以簡化。

不要犯一些制杖性錯誤。

/**************************************************************
    Problem: 1095
    User: infinityedge
    Language: C++
    Result: Accepted
    Time:32113 ms
    Memory:214388 kb
****************************************************************/

#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
#include <complex>

#define inf 0x3f3f3f3f
#define eps 1e-10

using namespace std;
typedef long long ll;
typedef pair<int, int> P;

struct edge {
    int to, w, nxt;
} e[];

int h[], cnt;

void addedge(int x, int y) {
    cnt++; e[cnt].to = y; e[cnt].nxt = h[x]; h[x] = cnt;
    cnt++; e[cnt].to = x; e[cnt].nxt = h[y]; h[y] = cnt;
}

int n, m;

int vis[], siz[], dep[], tp[], ans[], Ans[], dis[][], dfn[][], root[];
int b[], Dfn[], end[], Ct, cnt_open;
vector<int> vec[];
int N, rt, ct, ansroot;

struct node{
    int l, r, lc, rc;
    P dat;
}d[ *  *  * ];

int seg_sz;

void pushup(int k){
    d[k].dat = make_pair(-inf, );
    if(d[k].lc) d[k].dat = d[d[k].lc].dat;
    if(d[k].rc) {
        if(d[d[k].rc].dat.first > d[k].dat.first) d[k].dat = d[d[k].rc].dat;
    }
}

void ins(int &k, int l, int r, int pos, int x){
    if(k == ) k = ++seg_sz;
    d[k].l = l, d[k].r = r;
    if(l == r) {
        d[k].dat = make_pair(x, pos);
        return;
    }
    int mid = (l + r) >> ;
    if(pos <= mid) ins(d[k].lc, l, mid, pos, x);
    else ins(d[k].rc, mid + , r, pos, x);
    pushup(k);
}

void modify(int k, int pos, int x){
    if(k == ) return;
    if(d[k].l == d[k].r){
        d[k].dat = make_pair(x, pos);
        return;
    }
    int mid = (d[k].l + d[k].r) >> ;
    if(pos <= mid) modify(d[k].lc, pos, x);
    else modify(d[k].rc, pos, x);
    pushup(k);
}

P query(int k, int l, int r){
    if(k == ) return make_pair(-inf, );
    if(l <= d[k].l && d[k].r <= r){
        return d[k].dat;
    }
    int mid = (d[k].l + d[k].r) >> ;
    P sum = make_pair(-inf, );
    if(l <= mid) {
        P tmp = query(d[k].lc, l, r);
        if(tmp.first > sum.first) sum = tmp;
    }
    if(r > mid) {
        P tmp = query(d[k].rc, l, r);
        if(tmp.first > sum.first) sum = tmp;
    }
    return sum; 
}



void dfs_root(int x, int f){
    siz[x] = ; int mx = ;
    for(int i = h[x]; i; i = e[i].nxt){
        if(e[i].to == f || vis[e[i].to]) continue;
        dfs_root(e[i].to, x);
        mx = max(mx, siz[e[i].to]);
        siz[x] += siz[e[i].to];
    }
    if(max(mx, N - siz[x] - ) <= N / ) rt = x;
}

void dfs_size(int x, int f){
    siz[x] = ;
    for(int i = h[x]; i; i = e[i].nxt){
        if(e[i].to == f || vis[e[i].to]) continue;
        dfs_size(e[i].to, x);
        siz[x] += siz[e[i].to];
    }
}

void dfs_tag(int x, int f, int de){
    dep[x] = de;
    for(int i = h[x]; i; i = e[i].nxt){
        if(e[i].to == f || vis[e[i].to]) continue;
        tp[e[i].to] = rt;
        dfs_tag(e[i].to, x, de);
    }
}

void dfs_ans(int x, int f){
    dis[x][dep[x]] = dis[f][dep[x]] + ;
    dfn[x][dep[x]] = ++ct;
    ins(root[rt], , N, dfn[x][dep[x]], dis[x][dep[x]]);
    for(int i = h[x]; i; i = e[i].nxt){
        if(e[i].to == f || vis[e[i].to]) continue;
        dfs_ans(e[i].to, x);
    }
}

void solve(int x, int cur){
    dfs_root(x, );
    Dfn[rt] = end[rt] = ++Ct;
    dfs_size(rt, );
    dfs_tag(rt, , cur);
    ins(root[rt], , N, , );
    ct = ;
    for(int i = h[rt]; i; i = e[i].nxt){
        if(vis[e[i].to]) continue;
        vec[rt].push_back(ct);
        dfs_ans(e[i].to, rt);
    }
    vec[rt].push_back(ct + );
    P r1 = query(root[rt], , N);
    int r = lower_bound(vec[rt].begin(), vec[rt].end(), r1.second) - vec[rt].begin();
    int l = r - ;
    l = vec[rt][l], r = vec[rt][r];
    P r2 = make_pair(-inf, ), r3 = make_pair(-inf, );
    if(l >= ) r2 = query(root[rt], , l);
    if(r < N) r3 = query(root[rt], r + , N);
    if(r3.first > r2.first) r2 = r3;
    Ans[rt] = ans[rt] = r1.first + r2.first;
    vis[rt] = ;
    int trt = rt;
    for(int i = h[trt]; i; i = e[i].nxt){
        if(vis[e[i].to]) continue;
        if(siz[e[i].to] == ) continue;
        N = siz[e[i].to];
        solve(e[i].to, cur + );
        Ans[trt] = max(Ans[trt], Ans[e[i].to]);
        end[trt] = Ct;
    }
    ins(ansroot, , n, Dfn[trt], Ans[trt]);
}

void solvemodify(int x){
    if(b[x] == ){
        b[x] = ; cnt_open --;
        int mxdep = dep[x], rtp = tp[x];
        if(Dfn[x]) {
            mxdep--;
//          printf("%d ", Ans[x]);
            modify(root[x], , -inf);
            N = d[root[x]].r;
            P r1 = query(root[x], , N);
            int r = lower_bound(vec[x].begin(), vec[x].end(), r1.second) - vec[x].begin();
            int l = r - ;
            l = vec[x][l], r = vec[x][r];
            P r2 = make_pair(-inf, ), r3 = make_pair(-inf, );
            if(l >= ) r2 = query(root[x], , l);
            if(r < N) r3 = query(root[x], r + , N);
            if(r3.first > r2.first) r2 = r3;
            if(b[x] ==  && r2.first == ) r1.first = ; 
            Ans[x] = ans[x] = r1.first + r2.first;
            modify(ansroot, Dfn[x], Ans[x]);
//          printf("%d\n", Ans[x]);
        }
        for(int i = mxdep; i >= ; i --){
//          printf("%d ", Ans[rtp]);
            modify(root[rtp], dfn[x][i], );
            N = d[root[rtp]].r;
            P r1 = query(root[rtp], , N);
            int r = lower_bound(vec[rtp].begin(), vec[rtp].end(), r1.second) - vec[rtp].begin();
            int l = r - ;
            l = vec[rtp][l], r = vec[rtp][r];
            P r2 = make_pair(-inf, ), r3 = make_pair(-inf, );
            if(l >= ) r2 = query(root[rtp], , l);
            if(r < N) r3 = query(root[rtp], r + , N);
            if(r3.first > r2.first) r2 = r3;
            if(b[rtp] ==  && r2.first == ) r1.first = ; 
            ans[rtp] = r1.first + r2.first;
//          printf("%d %d %d %d ", r1.first, r1.second, r2.first, r2.second);
            modify(ansroot, Dfn[rtp], ans[rtp]);
            Ans[rtp] = query(ansroot, Dfn[rtp], end[rtp]).first;
//          printf("%d\n", Ans[rtp]);
            rtp = tp[rtp];
        }
    }else{
        b[x] = ; cnt_open ++;
        int mxdep = dep[x], rtp = tp[x];
        if(Dfn[x]) {
            mxdep--;
//          printf("%d ", Ans[x]);
            modify(root[x], , );
            N = d[root[x]].r;
            P r1 = query(root[x], , N);
            int r = lower_bound(vec[x].begin(), vec[x].end(), r1.second) - vec[x].begin();
            int l = r - ;
            l = vec[x][l], r = vec[x][r];
            P r2 = make_pair(-inf, ), r3 = make_pair(-inf, );
            if(l >= ) r2 = query(root[x], , l);
            if(r < N) r3 = query(root[x], r + , N);
            if(r3.first > r2.first) r2 = r3;
            if(b[x] ==  && r2.first == ) r1.first = ; 
            Ans[x] = ans[x] = r1.first + r2.first;
            modify(ansroot, Dfn[x], Ans[x]);
//          printf("%d\n", Ans[x]);
        }
        for(int i = mxdep; i >= ; i --){
//          printf("%d ", Ans[rtp]);
            modify(root[rtp], dfn[x][i], dis[x][i]);
            N = d[root[rtp]].r;
            P r1 = query(root[rtp], , N);
            int r = lower_bound(vec[rtp].begin(), vec[rtp].end(), r1.second) - vec[rtp].begin();
            int l = r - ;
            l = vec[rtp][l], r = vec[rtp][r];
            P r2 = make_pair(-inf, ), r3 = make_pair(-inf, );
            if(l >= ) r2 = query(root[rtp], , l);
            if(r < N) r3 = query(root[rtp], r + , N);
            if(r3.first > r2.first) r2 = r3;
            if(b[rtp] ==  && r2.first == ) r1.first = ; 
            ans[rtp] = r1.first + r2.first;
//          printf("%d %d %d %d ", r1.first, r1.second, r2.first, r2.second);
            modify(ansroot, Dfn[rtp], ans[rtp]);
            Ans[rtp] = query(ansroot, Dfn[rtp], end[rtp]).first;
//          printf("%d\n", Ans[rtp]);
            rtp = tp[rtp];
        }
    }
}
int main() {
    //  freopen("test.in", "r", stdin);
    //  freopen("test.out", "w", stdout);
    scanf("%d", &n);
    for (int i = ; i < n; i ++) {
        int x, y;
        scanf("%d%d", &x, &y);
        addedge(x, y);
    }
    N = n; cnt_open = n;
    solve(, );
    scanf("%d", &m);
    char ch[];
    for(int i = ; i <= m; i ++){
        scanf("%s", ch);
        if(ch[] == 'G'){
            if(cnt_open == ){
                printf("0\n");
                continue;
            }
            if(cnt_open == ){
                printf("-1\n");
                continue;
            }
            printf("%d\n", query(ansroot, , n).first); 
        }else{
            int x;
            scanf("%d", &x);
            solvemodify(x);
        }
    }
    return ;
}

「BZOJ1095」「ZJOI2007」Hide 捉迷藏

Description

Input

Output

Sample Input

Sample Output

HINT

題解

My Code

繼續閱讀

BZOJ1047 [HAOI2007]理想的正方形（洛谷P2216）單調隊列

BZOJ1452: [JSOI2009]Count（洛谷P4054）樹狀數組

BZOJ2819 Nim樹鍊剖分

【BZOJ】3196 Tyvj 1730 二逼平衡樹線段樹+平衡樹

[BZOJ4568][SCOI2016]幸運數字

[BZOJ 1046][HAOI 2007]上升序列(nlogn的LIS算法)

codeforces 321 C Ciel the Commander 點分治

bzoj3546: [ONTAK2010]Life of the Party

bzoj1717 [Usaco2006 Dec]Milk Patterns 産奶的模式字尾數組論文題

【Codeforces】600E Lomsat gelral (dsu on tree)

[bzoj 1355--Baltic2009]Radio Transmission

【BZOJ 1355】[Baltic2009]Radio Transmission kmp

BZOJ P1355: [Baltic2009]Radio Transmission

bzoj4556 [Tjoi2016&Heoi2016]字元串可持久化線段樹+字尾數組+二分

BZOJ4556: [Tjoi2016&Heoi2016]字元串

HYSBZ 2038 小Z的襪子(hose)