zoj3686(ZOJ Monthly, March 2013 A题)

终于A了前不久比赛的A题,当时完全木有想到线段树啊,主要是对树的先序遍历序列的性质陌生:在树的先序遍历序列中,一棵子树占据连续的一段序列。所以求出先序序列的同时记录每个节点代表的子树的起始index和最后index。然后就能在o i的时候更新线段树[sub[i].begin,sub[i].end]部分即可。
被异或运算和成段更新坑了好久。。

#include<stdio.h>
#include<stdlib.h>
#include<vector>
using namespace std;
vector<int> head[100000+10];
int ord[100000+10];
typedef struct Sub{
	int begin;
	int end;
}Sub;
Sub sub[100000+10];
int cnt=0;
typedef struct Tree{
	int l,r;
	int sum;
	int lazy;
}Tree;
Tree tree[4*100000+10];
void pushup(int rt)
{
	tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum;
	return;
}
void pushdown(int rt)
{
	tree[rt<<1].lazy^=1;
	tree[rt<<1|1].lazy^=1;
	tree[rt<<1].sum=(tree[rt<<1].r-tree[rt<<1].l+1)-tree[rt<<1].sum;
	tree[rt<<1|1].sum=(tree[rt<<1|1].r-tree[rt<<1|1].l+1)-tree[rt<<1|1].sum;
	tree[rt].lazy=0;
	return;
}
void build(int rt,int l,int r)
{
	tree[rt].l=l;
	tree[rt].r=r;
	tree[rt].lazy=0;
	if(l==r)
	{
		tree[rt].sum=0;
		return;
	}
	int m=(l+r)/2;
	build(rt<<1,l,m);
	build(rt<<1|1,m+1,r);
	pushup(rt);
	return;
}
void update(int rt,int L,int R)
{
	if(L<=tree[rt].l && tree[rt].r<=R)
	{
		int len=tree[rt].r-tree[rt].l+1;
		tree[rt].sum=len-tree[rt].sum;
		tree[rt].lazy^=1;
		return;
	}
	if(tree[rt].lazy)
		pushdown(rt);
	int m=(tree[rt].l+tree[rt].r)/2;
	if(L<=m)
		update(rt<<1,L,R);
	if(R>m)
		update(rt<<1|1,L,R);
	pushup(rt);
	return;
}
int query(int rt,int L,int R)
{
	if(L<=tree[rt].l && tree[rt].r<=R)
	{
		return tree[rt].sum;
	}
	if(tree[rt].lazy)
		pushdown(rt);
	int m=(tree[rt].l+tree[rt].r)/2;
	int ans=0;
	if(L<=m)
		ans+=query(rt<<1,L,R);
	if(R>m)
		ans+=query(rt<<1|1,L,R);
	return ans;
}
void dfs(int cur)
{
	ord[++cnt]=cur;
	sub[cur].begin=cnt;
	int i;
	for(i=0;i<head[cur].size();i++)
	{
		int v=head[cur][i];
		dfs(v);
	}
	sub[cur].end=cnt;
	return;
}
int main()
{
	int n,m;
	int i,j;
	while(scanf("%d %d",&n,&m)!=EOF)
	{
		for(i=1;i<=n;i++)
			if(!head[i].empty())
				head[i].clear();
		int fa;
		for(i=2;i<=n;i++)
		{
			scanf("%d",&fa);
			head[fa].push_back(i);
		}
		getchar();
		cnt=0;
		dfs(1);
		build(1,1,n);
		char c;
		int node;
		for(i=1;i<=m;i++)
		{
			scanf("%c %d",&c,&node);
			getchar();
			if(c=='o')
			{
				update(1,sub[node].begin,sub[node].end);

			
			}
			else
			{
				int ans=query(1,sub[node].begin,sub[node].end);
				printf("%d\n",ans);
			
			}
		}
		printf("\n");
	}
//system("pause");
return 0;
}


发表评论

电子邮件地址不会被公开。 必填项已用 * 标注

*

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>