树状数组例题。
“用DFS求出树结点对应的区间范围”比较难想……后面的区间值修改和查询都比较简单了。分别用了线段树和树状数组进行了求解。
线段树：
|
1 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 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 |
#include<cstdio> #include<cstring> int n,m,hd[100000],b[100000],nt[100000][2],el,t,ml; char s[2]; struct edge { int j,p; }e[200000]; struct node { bool b; int sum; node *l,*r; }mem[400000],*root; inline void adde(int i,int j) { e[el].j=j; e[el].p=hd[i]; hd[i]=el++; e[el].j=i; e[el].p=hd[j]; hd[j]=el++; } void dfs(int i) { int j,k,l; nt[i][0]=t++; for(l=hd[i];l!=-1;l=e[l].p) { j=e[l].j; if(b[j]) continue; b[j]=1; dfs(j); } nt[i][1]=t++; } void add(int e,int c) { int L=0,R=t,m; node *p=root; while(1) { p->sum+=c; if(L==R) break; m=L+R>>1; if(p->b) { p->b=0; p->l=&mem[ml++]; p->r=&mem[ml++]; p->l->b=p->r->b=1; p->l->sum=p->r->sum=0; } if(e<=m) { R=m; p=p->l; } else { L=m+1; p=p->r; } } } int que(int l,int r,int L,int R,node *p) { int m=L+R>>1; if(p->b||l==L&&r==R) return p->sum; if(r<=m) return que(l,r,L,m,p->l); if(l>m) return que(l,r,m+1,R,p->r); return que(l,m,L,m,p->l)+que(m+1,r,m+1,R,p->r); } int main() { int i,j,k,l; while(~scanf("%d",&n)) { el=t=ml=0; root=&mem[ml++]; root->b=1; root->sum=0; memset(hd,-1,sizeof hd); for(i=1;i<n;i++) { scanf("%d%d",&j,&k); adde(j-1,k-1); } memset(b,0,sizeof b); b[0]=1; dfs(0); --t; for(i=0;i<n;i++) add(nt[i][0],1); scanf("%d",&m); while(m--) { scanf("%s%d",s,&i); --i; if(s[0]=='Q') printf("%d\n",que(nt[i][0],nt[i][1],0,t,root)); else { if(b[i]) add(nt[i][0],-1); else add(nt[i][0],1); b[i]^=1; } } } return 0; } |
树状数组：
|
1 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 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 |
#include<cstdio> #include<cstring> int n,m,hd[100000],el,b[100000],nt[100000][2],t,c[200001]; char s[2]; struct edge { int j,p; }e[200000]; inline void adde(int i,int j) { e[el].j=j; e[el].p=hd[i]; hd[i]=el++; e[el].j=i; e[el].p=hd[j]; hd[j]=el++; } void dfs(int i) { int j,l; nt[i][0]=t++; for(l=hd[i];l!=-1;l=e[l].p) { j=e[l].j; if(b[j]) continue; b[j]=1; dfs(j); } nt[i][1]=t++; } inline void add(int e,int d) { int i; for(i=1;e<t;i<<=1) { if(e&i) { c[e]+=d; e+=i; } } } inline int val(int e) { int i,j; for(i=1,j=0;e;i<<=1) { if(e&i) { j+=c[e]; e-=i; } } return j; } inline int que(int l,int r) { return val(r)-val(l-1); } int main() { int i,j,k,l; while(~scanf("%d",&n)) { el=0; t=1; memset(hd,-1,sizeof hd); memset(c,0,sizeof c); for(i=1;i<n;i++) { scanf("%d%d",&j,&k); adde(j-1,k-1); } memset(b,0,sizeof b); b[0]=1; dfs(0); for(i=0;i<n;i++) add(nt[i][0],1); scanf("%d",&m); while(m--) { scanf("%s%d",s,&i); --i; if(s[0]=='Q') printf("%d\n",que(nt[i][0],nt[i][1])); else { if(b[i]) add(nt[i][0],-1); else add(nt[i][0],1); b[i]^=1; } } } return 0; } |