A A Simple Tree Problem
線段樹成段更新 以前做過差不多的一題蘋果樹 dfs一次然後可以轉化成一維線段樹 好像叫時間戳。。。
#include#include #include using namespace std; const int MAX = 100010; int b[MAX]; int low[MAX]; int high[MAX]; int flag[MAX]; int map[MAX]; bool vis[MAX]; vector e[MAX]; int cnt; struct node { int l; int r; int sum; int flag; int num; }a[MAX*4]; void build(int l,int r,int rt) { a[rt].l = l; a[rt].r = r; a[rt].flag = 0; a[rt].sum = 0; if(l == r ) return; int m = (l + r) >> 1; build(l,m,rt<<1); build(m+1,r,rt<<1|1); } void update(int l,int r,int rt) { if(a[rt].l >= l && a[rt].r <= r) { a[rt].flag ^= 1; a[rt].sum = (a[rt].r - a[rt].l + 1) - a[rt].sum; return; } if(a[rt].flag) { int k = (a[rt].r - a[rt].l + 1); a[rt<<1].flag ^= 1 ; a[rt<<1|1].flag ^= 1; a[rt<<1].sum = (k - (k >> 1)) - a[rt<<1].sum; a[rt<<1|1].sum = (k >> 1) - a[rt<<1|1].sum; a[rt].flag = 0; } int m = (a[rt].l + a[rt].r) >> 1; if(l <= m) update(l,r,rt<<1); if(r > m) update(l,r,rt<<1|1); a[rt].sum = a[rt<<1].sum + a[rt<<1|1].sum; } int query(int l,int r,int rt) { if(a[rt].l >= l && a[rt].r <= r) return a[rt].sum; if(a[rt].flag) { int k = (a[rt].r - a[rt].l + 1); a[rt<<1].flag ^= 1 ; a[rt<<1|1].flag ^= 1; a[rt<<1].sum = (k - (k >> 1)) - a[rt<<1].sum; a[rt<<1|1].sum = (k >> 1) - a[rt<<1|1].sum; a[rt].flag = 0; } int m = (a[rt].l + a[rt].r) >> 1; int ret = 0; if(l <= m) ret += query(l,r,rt<<1); if(r > m) ret += query(l,r,rt<<1|1); return ret; } void init(int n) { for(int i = 1;i <= n; i++) e[i].clear(); memset(a,0,sizeof(a)); memset(map,0,sizeof(map)); memset(flag,0,sizeof(flag)); memset(high,0,sizeof(high)); memset(low,0,sizeof(low)); memset(vis,false,sizeof(vis)); cnt = 1; } void dfs(int u) { low[u] = cnt; vis[u] = true; for(int i = 0;i < e[u].size(); i++) { int v = e[u][i]; if(vis[v]) continue; cnt++; dfs(v); } high[u] = cnt; } int main() { int n,m; int i,u; char str[10]; while(scanf("%d %d",&n,&m)!=EOF) { init(n); build(1,n,1); for(i = 2;i <= n; i++) { scanf("%d",&u); e[u].push_back(i); } dfs(1); while(m--) { scanf("%s %d",str,&u); if(str[0] == 'o') { update(low[u],high[u],1); } else { printf("%d\n",query(low[u],high[u],1)); } } puts(""); } return 0; }
