某岛

… : "…アッカリ～ン . .. . " .. .
July 13, 2010

POJ 3321. Apple Tree

Brief description:

• 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];
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];
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]));
}
}
}