Brief description:

给定一棵树，每个结点有 0/1 两种状态，要求动态维护以下操作。（初始全 1 .. .

• C x: 将 x 点的状态取反。
• Q x: 询问以 x 结点为根子树中，1 的个数。

Analysis:

… 略）。。（ DFS 序列 + (线段树 or 树状数组)。。

http://acm.hust.edu.cn/vjudge/problem/viewSource.action?id=1169124

const int N = 100009, M = 2 * N;

int L[N], R[N], cnt;
// Vertex .. .
int hd[N], nxt[M], a[M], b[M];
// Adjacent List .. .
int C[4*N];
// Interval Tree
int n;

#define root 1, 1, n
#define lx (x<<1)
#define rx (lx|1)
#define m ((l+r)>>1)
#define lc lx, l, m, a, b
#define rc rx, m+1, r, a, b

#define pos a
#define delta b
void Modify(int x, int l, int r, int pos, int delta){
    C[x] += delta; if (l < r){
        if (pos <= m) Modify(lc);
        else Modify(rc);
    }
}
#undef pos

int Sum(int x, int l, int r, int a, int b){
    if (a <= l && r <= b) return C[x];
    else return (a <= m ? Sum(lc) : 0) + (m < b ? Sum(rc) : 0);
}

#define v b[i]

inline void dfs(int u = 0){
    L[u] = ++cnt;
    for (int i=hd[u];i;i=nxt[i]) if (!L[v]){
        dfs(v);
    }
    R[u] = cnt;
}

int main(){

#ifndef ONLINE_JUDGE
    //freopen("in.txt", "r", stdin);
#endif

    FOR_C(i, 2, _RD(n) << 1){
        RD(a[i], b[i]), --a[i], --b[i], a[i|1] = b[i], b[i|1] = a[i];
        nxt[i] = hd[a[i]], hd[a[i]] = i; ++i;
        nxt[i] = hd[a[i]], hd[a[i]] = i;
    }

    dfs(); REP_1(i, n) Modify(root, i, 1);

    char cmd; int pos; DO_C(RD()){
        RC(cmd); --_RD(pos); if (cmd == 'C'){
            Modify(root, L[pos], Sum(root, L[pos], L[pos]) ? -1 : 1);
        }
        else{
            OT(Sum(root, L[pos], R[pos]));
        }
    }
}

http://acm.hust.edu.cn/vjudge/problem/viewSource.action?id=1169082

const int N = 100009, M = 2 * N;

int L[N], R[N], cnt;
// Vertex .. .
int hd[N], nxt[M], a[M], b[M];
// Adjacent List .. .
int C[N];
// Interval Tree
int n;


void Modify(int x, int d){
    while (x <= n) C[x] += d, x += low_bit(x);
}

int Sum(int x){
    int res = 0; while (x) res += C[x], x ^= low_bit(x);
    return res;
}

int Sum(int l, int r){
    return Sum(r) - Sum(l-1);
}

int Single(int x){
    int res = C[x], p = low_bit(x); --x;
    while (x && low_bit(x) < p){
        res -= C[x];
        x ^= low_bit(x);
    }
    return res;
}

#define v b[i]

inline void dfs(int u = 0){
    L[u] = ++cnt;
    for (int i=hd[u];i;i=nxt[i]) if (!L[v]){
        dfs(v);
    }
    R[u] = cnt;
}

int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif

    FOR_C(i, 2, _RD(n) << 1){
        RD(a[i], b[i]), --a[i], --b[i], a[i|1] = b[i], b[i|1] = a[i];
        nxt[i] = hd[a[i]], hd[a[i]] = i; ++i;
        nxt[i] = hd[a[i]], hd[a[i]] = i;
    }

    dfs(); REP_1(i, n) Modify(i, 1);

    char cmd; int pos; DO_C(RD()){
        RC(cmd); --_RD(pos); if (cmd == 'C'){
            Modify(L[pos], Single(L[pos]) ? -1 : 1);
        }
        else{
            OT(Sum(L[pos], R[pos]));
        }
    }
}

External link:

http://poj.org/problem?id=3321

Posted by xiaodao
Category: POJ