[TIOJ] 1272. The Agency
題目連結:http://tioj.infor.org/problems/1272
給定一棵樹,然後要求詢問某個節點的值是偶數或奇數,或者對一整顆子樹加一。不妨把樹壓平後,透過進入時間戳與出去的時間戳,得到一個區間$[in[x], out[x])$,而其實這個區間就是x的子樹,所以發現要對子樹加值就是對那個區間加值,而查詢則是查$in[x]$。把問題轉成單點查詢區間加值後,其實一個BIT就可以做到了。
給定一棵樹,然後要求詢問某個節點的值是偶數或奇數,或者對一整顆子樹加一。不妨把樹壓平後,透過進入時間戳與出去的時間戳,得到一個區間$[in[x], out[x])$,而其實這個區間就是x的子樹,所以發現要對子樹加值就是對那個區間加值,而查詢則是查$in[x]$。把問題轉成單點查詢區間加值後,其實一個BIT就可以做到了。
#include <bits/stdc++.h>
using namespace std;
#define PB push_back
const int N = 100000 + 5;
class BIT{
private:
int arr[N], size=0;
inline int lowbit(int x){
return x&-x;
}
public:
void init(int s){
fill(arr, arr+s, 0);
size=s;
}
//1-base (l, r]
void add(int l, int r, int v){
add(l, -v);
add(r, v);
}
void add(int s, int v){
while(s){
arr[s]+=v;
s-=lowbit(s);
}
}
int query(int x){
int r=0;
while(x<size){
r+=arr[x];
x+=lowbit(x);
}
return r;
}
} bit;
vector<int> G[N];
int step=1, in[N], out[N];
void dfs(int);
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int n, m; cin>>n>>m;
for(int i=1;i<=n;++i){
int s; cin>>s;
while(s--){
int x; cin>>x;
G[i].PB(x);
}
}
dfs(1);
bit.init(step+3);
while(m--){
bool type;int who;
cin>>type>>who;
if(type)
cout<<(bit.query(in[who])&1)<<'\n';
else
bit.add(in[who]-1, out[who]-1, 1);
}
return 0;
}
void dfs(int x){
in[x]=step++;
for(auto i:G[x]) dfs(i);
out[x]=step;
}
留言
張貼留言