Link: http://tioj.ck.tp.edu.tw/problems/1272
用DFS入出順序做樹壓平，壓平後用資料結構維護即可。
可以用支援區間修改單點查詢的線段樹維護，不過這裡我用BIT。
一般的BIT是維護總和(加法)，不過XOR也有和加法一樣的性質(sum(a,b)=c -> a=c-b, xor(a,b)=c -> a=c xor b)，因此也能使用BIT維護。
區間修改+單點查詢，也能轉換成 單點修改+區間查詢，做個差分就行了(也就是說新數列b[i]=原數列a[i]-a[i-1])，要對 L~R 加 V 就 add(L,V), add(R+1,-V) 即可，查詢 i 的數值就 sum(0~i)。 (以上用加法說明，xor反而更簡單)
BIT寫完後就輕鬆AC + 拿TopCoder囉!
AC code1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
| #include <bits/stdc++.h>
using namespace std;
int n;
vector<int> g[100010];
int now=0;
int in[100010],out[100010];
void dfs(int i)
{
in[i]=++now;
for(int j:g[i])
dfs(j);
out[i]=now;
}
bool bit[100010];
void add(int i)
{
while(i<=n)
{
bit[i]^=1;
i+=i&-i;
}
}
bool sum(int i)
{
bool s=0;
while(i>0)
{
s^=bit[i];
i-=i&-i;
}
return s;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
int cnt;
cin>>cnt;
while(cnt--)
{
int v;
cin>>v;
g[i].push_back(v);
}
}
dfs(1);
while(m--)
{
int a,b;
cin>>a>>b;
if(a==0)
{
add(in[b]);
add(out[b]+1);
}
else
{
cout<<sum(in[b])<<'\n';
}
}
}
|