TIOJ 1272 The Agency [segment tree]

poao899    6496K    511MS    G++    2.10K     2009-12-07 18:51:45                                                      .


DFS + segment tree

唔笨了好久不開心~"~

是說沒被捏就不好想~"~


//*****************************

#include<stdio.h>
int stamp[200010],time=1;
int trans[100010][2];
int getint(){
	int g=0,c=getchar();
	while(c==10||c==32||c==9)c=getchar();
	while(c>='0'&&c<='9'){
		g=g*10+c-48;
		c=getchar();
	}
	return g;
}
struct node{
	node *bro,*son;
	void set(node *p){
		node *q = son;
		son=p;
		p->bro = q;
	}
}N[100010],*s[100010];
struct segment{
	segment *lch,*rch;
	int l,r;
	int change;
	void sneeze(int,int);
	int query(int);
}Seg[400080];
segment* get(int l,int r){
	static int cnt = 1;
	segment* p = Seg+cnt;
	cnt++;
	p->l = l;p->r = r;
	return p;
}
void segment::sneeze(int _l , int _r){
	if(l==_l && r==_r){change++;return;}
	int mid = (l+r)/2;
	if(lch == NULL){
		lch = get(l , mid);
		rch = get(mid+1 , r);
	}
	if(_r<=mid){
		lch->sneeze(_l , _r);
	}else if(_l>mid){
		rch->sneeze(_l , _r);
	}else{
		lch->sneeze(_l , mid);
		rch->sneeze(mid+1 , _r);
	}
}
int segment::query(int i){
	if(!lch)return change;
	int mid = (l+r)/2;
	if(i>mid)return rch->query(i)+change;
	else return lch->query(i)+change;
}
int stack[100010],top=1;
int n,m,a,b;
int main(){
	n=getint();
	m=getint();
	//Input
	for(int i=1;i<=n;i++){
		a=getint();
		while(a--)(N+i)->set(N+getint());
	}
	//DFS
	stack[top]=1;s[top]=(N+1)->son;
	while(top){
		if(!trans[stack[top]][0]){
			stamp[time]=stack[top];
			trans[stack[top]][0]=time++;
		}
		if(s[top]==NULL){
			//printf("%d over top=%d\n",stack[top],top);
			stamp[time]=stack[top];
			trans[stack[top]][1]=time++;
			top--;
		}
		else{
			node *p=s[top];
			s[top]=s[top]->bro;
			top++;
			stack[top]=p-N;
			s[top]=p->son;
		}
	}
	//Initialize
	Seg->l=1;Seg->r=time-1;Seg->change=0;
	//Query
	while(m--){
		a=getint();
		b=getint();
		if(a){
			putchar(((Seg->query(trans[b][0]))&1)+48);
			putchar('\n');
		}else{
			Seg->sneeze(trans[b][0] , trans[b][1]);
		}
	}
}