poj3321——Apple Tree//树状数组
记住树状数组的基本操作：http://hi.baidu.com/wuxyy/blog/item/a4ad808b59be8bd2fd1f109d.htmlhttp://writeblog.csdn.net/PostEdit.aspx?entryId=6376639
int lowbit(int x){ return x&(x^(x–1));}利用机器补码的特点，这个函数可以改得更方便int lowbit(int i){ return i&(-i);}如果要把a增加m，可以通过调用如下函数实现void add(int i,int v){ while (i<=n) { a+=v; i+=lowbit(i); }}如果要统计a到a之间的和，可以通过调用如下函数实现int sum(int i){ int s=0; while (i>0) { s+=a; i-=lowbit(i); } return s;}
此题思路：将每个点定一个时间戳。比如题目中给的树dfs()之后，点1为1,6，点2为2,3，点3为4,5.这样，查询1时，统计1--6之间的apple，再将结果除以2即可。
#include<iostream>#include<cstdio>#include<string>using namespace std;#define maxn 1000005int n,m;class map{public:int v,next;};map g;int head,cnt,c;bool have;class tree{public:int st,ed;};tree st;void dfs(int v){st.st =++cnt;int i;for(i=head;i;i=g.next ){dfs(g.v );}st.ed =++cnt;}int lowbit(int x){return x&(-x);}void add(int t,int v){while(t<maxn){c+=v;t+=lowbit(t);}}int getsum(int t){int s=0;while(t>0){s+=c;t-=lowbit(t);}return s;}int main(){int i,a,b,lsum,rsum;char ch;cnt=0;scanf("%d",&n);for(i=1;i<n;i++){scanf("%d%d",&a,&b);g[++cnt].v =b;g.next =head;head=cnt;}cnt=0;dfs(1);memset(have,true,sizeof(have));for(i=1;i<=n;i++){add(st.st,1);add(st.ed,1);}scanf("%d",&m);getchar();while(m--){scanf("%c %d",&ch,&a);getchar();if(ch=='Q'){lsum=getsum(st.st-1 );rsum=getsum(st.ed );printf("%d\n",(rsum-lsum)/2);}else if(ch=='C'){if(have){have=false;add(st.st ,-1);add(st.ed ,-1);}else {have=true;add(st.st ,1);add(st.ed ,1);}}}return 0;}
页:
[1]