pku 3321 树状数组.txt~

ACM资料大集合

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <iterator>
using namespace std;
#define PB push_back
//PKU 3321 树状数组

#define NMAX 100005
#define MMAX 100005
#define INFI 99999999

typedef struct ooparc
{
	int first;
	int second;
}ooparc;

typedef struct oopnode
{
	int begin;
	int end;
	int fa;
}oopnode;

typedef struct oopxulie
{
	int data;
	int has;
}oopxulie;

oopxulie xulie[NMAX*2+5];//DFS序列，data表示点的标号，has表示改点是否有苹果
ooparc arc[MMAX*2];//重复边集=输入的arc序列+将first,second倒置后的序列
oopnode node[NMAX];//在重复边集中，（arc.fisrt已排序），arc.first对应的开始点和结束点
oopnode node2[NMAX];//记录DFS序列某点的第一次出现和第二次出现的位置
int xxx;
int szsz[NMAX*2+5];

int getlow(int k)
{
	return k & (k ^ (k-1));
}

void add(int p)
{
	while(p<NMAX*2)
	{
		szsz[p]++;
		p+=getlow(p);
	}
}

void del(int p)
{
	while(p<NMAX*2)
	{
		szsz[p]--;
		p+=getlow(p);
	}
}

int getsum(int p)
{
	int sum=0;
	while(p>=1)
	{
		sum+=szsz[p];
		p-=getlow(p);
	}
	return sum;
}

void print_xulie(int num)
{
	int i;
	for(i=1;i<=num;i++) printf("%d ",xulie[i].data);
	printf("\n");
	for(i=1;i<=num;i++) printf("%d ",xulie[i].has);
}

bool cmparc(ooparc a,ooparc b)
{
	return a.first<b.first;
}

void build(int now)
{
	int i,p;
	xxx++;
	xulie[xxx].has=1;
	xulie[xxx].data=now;
	node2[now].begin=xxx;
	for(i=node[now].begin;i<=node[now].end;i++)
	{
		p=arc[i].second;
		if(node[now].fa!=p)
		{
			node[p].fa=now;
			build(p);
		}
	}
	xxx++;
	xulie[xxx].has=0;
	xulie[xxx].data=now;
	node2[now].end=xxx;
}

void change(int p)
{
	if(xulie[node2[p].begin].has==0) 
	{
		add(node2[p].begin);
		xulie[node2[p].begin].has=1;
	}
	else 
	{
		del(node2[p].begin);
		xulie[node2[p].begin].has=0;
	}
}

int cal(int p)
{
	return getsum(node2[p].end)-getsum(node2[p].begin-1);
}

void init(int mnum)
{
//	假设树的结构是：
//	   1
//	 2   5
//  3   4 6
//        7
//  则编列得到的DFS序列为：
//  1 2 3 3 2 5 4 4 6 7 7 6 5 1
//  则某点的子树为该序列里两次出现的这一点之间的标号，我们称其为该点的DFS区间
//  如标号5的子树，对应的DFS区间为5 4 4 6 7 7 6 5
//  建树时第一次出现的标号对应的has值为1，否则为0，则该DFS序列对应的has为：
//  1 1 1 0 0 1 1 0 1 1 0 0 0 0
//  要查找某点子树的has值之和，只要求这一点的DFS区间上的has之和即可
//  求区间上的数之和，树状数组最擅长。
	int i;
	for(i=1;i<=mnum;i++) 
	{
		arc[mnum+i].first=arc[i].second;
		arc[mnum+i].second=arc[i].first;
	}
	sort(arc+1,arc+2*mnum+1,cmparc);
	node[arc[1].first].begin=1;
	for(i=2;i<=2*mnum;i++)
	{
		if(arc[i-1].first!=arc[i].first) 
		{
			node[arc[i].first].begin=i;
			node[arc[i-1].first].end=i-1;
		}
	}
	node[arc[i-1].first].end=2*mnum;
	for(i=1;i<NMAX;i++)
	{
		node[i].fa=-10;
	}
	node[1].fa=-1;
	xxx=0;
	build(1);
	for(i=1;i<=2*mnum+2;i++)
	{
		if(xulie[i].has==1) add(i);
	}
//	print_xulie(2*mnum+2);
}

int main()
{
	int num,i,qnum,x,y;
	char str[3];
	scanf("%d",&num);
	for(i=1;i<=num-1;i++)
	{
		scanf("%d %d",&arc[i].first,&arc[i].second);
	}
	init(num-1);
	scanf("%d",&qnum);
	for(i=1;i<=qnum;i++)
	{
		scanf("%s %d",&str,&x);
		if(str[0]=='Q') printf("%d\n",cal(x));
		else change(x);
	}
	return 0;
}