2479431_ac_1119ms_23232k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <vector>
#include <algorithm>
#define INIT (Node *)malloc(sizeof(Node))
using namespace std;

int n, no;
vector <int> tree[100001];
vector <int> seg_tree[1<<18+1];
int pre[100001], back[100001], status[100001];

typedef struct node
{
	int L, R;
	int v;
	struct node *l, *r;
}Node;

Node *root;

void dfs(int v,int pa)
{
	int i;

	pre[v] = no;
	for(i = 0; i < tree[v].size(); i++)
	{
		if(tree[v][i]!=pa)
		{
			no++;
			dfs(tree[v][i],v);
		}
	}
	back[v] = no;
}

int sum(Node *s,int l,int r)
{
	int mid;

	if(s->L==l&&s->R==r)
		return s->v;
	mid = (s->L+s->R)/2;
	if(l>mid)
		return sum(s->r,l,r);
	else
		if(r<=mid)
			return sum(s->l,l,r);
	return sum(s->l,l,mid)+sum(s->r,mid+1,r);
}

void update(Node *s,int b,int v)
{
	int mid;

	s->v += v;
	if(s->L==s->R&&s->L==b)
		return ;
	mid = (s->L+s->R)/2;
	if(b<=mid)
		update(s->l,b,v);
	else
		update(s->r,b,v);
}

Node *creat_seg_tree(Node *s,int l,int r)
{
	int mid;
	Node *p, *q;

	
	mid = (l+r)/2;
	s->v = r-l+1;
	s->L = l,s->R = r;
	if(l==r)
	{
		s->l = NULL;
		s->r = NULL;
		return s;
	}
	p = INIT,q = INIT;
	s->l = creat_seg_tree(p,l,mid);
	s->r = creat_seg_tree(q,mid+1,r);
	return s;
}

void check(Node *s)
{
	if(s->l)
		check(s->l);
	printf("%d %d\n",s->L,s->R);
	if(s->r)
		check(s->r);
}

int main()
{
	int i, m;
	int a, b;

	scanf("%d",&n);
	no = 1;
	root = INIT;
	creat_seg_tree(root,1,n);
	//check(root);
	for(i = 1; i < n; i++)
	{
		scanf("%d%d",&a,&b);
		tree[a].push_back(b);
		tree[b].push_back(a);                                                
	}
	dfs(1,-1);
	
	memset(status,-1,sizeof(status));
	scanf("%d",&m);
	char str[2];
	while(m--)
	{
		scanf("%s%d",str,&a);
		if(str[0]=='C')
		{
			b = pre[a];
			update(root,b,status[b]);
			status[b] *= -1;
		}
		else
			printf("%d\n",sum(root,pre[a],back[a]));
	}
	return 1;
}