询问次数那么多，本能想到线段树。对区间重标号，区间询问， 更新。
View Code int N,M,K, len;int ll[MM<<2], rr[MM<<2];int ff[MM<<2];int sum[MM<<2];vector edge[MM];void dfs(int u) { int i,j,k,v; ll[u]=len++; for(i=0;i >1; ff[lson]^=1; ff[rson]^=1; ff[rt]=0; sum[lson]=(mid-l+1)-sum[lson]; sum[rson]=(r-mid)-sum[rson]; }}void push_up(int rt) { sum[rt]=sum[lson]+sum[rson];}void update(int L,int R,int l,int r,int rt) { if(L<=l && r<=R) { sum[rt]=(r-l+1)-sum[rt]; ff[rt]^=1; return; } int mid=(l+r)>>1; push_down(l,r,rt); if(L<=mid) update(L,R,l,mid,lson); if(R>mid) update(L,R,mid+1,r,rson); push_up(rt);}int query(int L,int R,int l,int r,int rt) { if(L<=l && r<=R) { return sum[rt]; } push_down(l,r,rt); int mid=(l+r)>>1, ret=0; if(L<=mid) ret+=query(L,R,l,mid,lson); if(R>mid) ret+=query(L,R,mid+1,r,rson); push_up(rt); return ret;}void solve() { int i,j,k,a,l,r; char op; for(i=0;i<(MM<<2);i++) ff[i]=sum[i]=0; while(M--) { getchar(); scanf("%c%d",&op,&a); if(op=='o') { update(ll[a],rr[a],1,len-1,1); } else { printf("%d\n",query(ll[a],rr[a],1,len-1,1)); } } printf("\n"); }