[NTUJ] 0903. Shadow Hunters
題目連結:http://acm.csie.org/ntujudge/problem.php?id=903
有趣的好題,想了很久只想的到樹鍊剖分的作法,被雷了才知道更好的做法QQ
對於全子樹加一其實很簡單,就把樹壓扁後把$[in[x], out[x]]$全部加一就好,然後詢問時則單點詢問邊即可。但是另外兩個操作就會變得很難做,所以要用另外一種方式想,考慮一條邊若或被加值,則一定是因為它下面的點有被加值,所以其實對最底下的點加值即可,然後為了怕太上面的人也會被算到,記得超過最頂之後要再減一以免多算,這樣就變成單點加值區間查詢了。
有趣的好題,想了很久只想的到樹鍊剖分的作法,被雷了才知道更好的做法QQ
對於全子樹加一其實很簡單,就把樹壓扁後把$[in[x], out[x]]$全部加一就好,然後詢問時則單點詢問邊即可。但是另外兩個操作就會變得很難做,所以要用另外一種方式想,考慮一條邊若或被加值,則一定是因為它下面的點有被加值,所以其實對最底下的點加值即可,然後為了怕太上面的人也會被算到,記得超過最頂之後要再減一以免多算,這樣就變成單點加值區間查詢了。
#include <bits/stdc++.h>
using namespace std;
#define PB push_back
const int N = 100000 + 5;
class BIT1{
#define lowbit(x) ((x)&(-(x)))
private:
int arr[N], size;
inline int query(int x){
int r=0;
while(x){
r+=arr[x];
x-=lowbit(x);
}
return r;
}
public:
inline void init(int x){
fill(arr, arr+size, 0);
size=x;
}
inline int query(int l, int r){
// 1-base (l, r]
return query(r)-query(l);
}
inline void add(int x, int v){
while(x<size){
arr[x]+=v;
x+=lowbit(x);
}
}
#undef lowbit
} bit1;
class BIT2{
#define lowbit(x) ((x)&(-(x)))
private:
int arr[N], size;
inline void add(int x, int v){
while(x){
arr[x]+=v;
x-=lowbit(x);
}
}
public:
inline void init(int x){
fill(arr, arr+size, 0);
size=x;
}
inline void add(int l, int r, int v){
//1-base (l, r]
add(l, -v);
add(r, v);
}
inline int query(int x){
int r=0;
while(x<size){
r+=arr[x];
x+=lowbit(x);
}
return r;
}
#undef lowbit
} bit2;
int timer;
vector<int> G[N];
int time_in[N], time_out[N];
inline void init(int);
void dfs(int,int);
inline bool anc(int,int);
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int t; cin>>t;
while(t--){
int n; cin>>n;
init(n);
for(int i=0;i<n-1;i++){
int u, v; cin>>u>>v;
G[u].PB(v);
G[v].PB(u);
}
dfs(0, 0);
int q; cin>>q;
while(q--){
char type; cin>>type;
if(type=='s'){
int x, y; cin>>x>>y;
bit1.add(time_in[x], 1);
bit1.add(time_in[y], -1);
}else if(type=='h'){
int x; cin>>x;
bit2.add(time_in[x]-1, time_out[x]-1, 1);
}else if(type=='n'){
int x; cin>>x;
bit1.add(time_in[x], 1);
}else if(type=='q'){
int x, y; cin>>x>>y;
if(!anc(x, y)) swap(x,y);
int sm = bit2.query(time_in[x]);
sm+=bit1.query(time_in[y]-1, time_out[y]-1);
cout<<sm<<'\n';
}
}
}
return 0;
}
inline void init(int n){
for(int i=0;i<n;i++) G[i].clear();
timer=1;
bit1.init(n+3);
bit2.init(n+3);
}
void dfs(int w, int f){
time_in[w]=timer++;
for(auto i:G[w]){
if(i == f) continue;
dfs(i, w);
}
time_out[w]=timer;
}
inline bool anc(int a, int b){
return (time_in[a]<=time_in[b])and(time_out[b]<=time_out[a]);
}
留言
張貼留言