Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## Re:树状数组 5272K 391MS

Posted by 1093824239 at 2019-01-18 09:44:34 on Problem 3321
In Reply To:树状数组 5272K 391MS Posted by:322019281 at 2018-08-28 10:23:03
```> #include<cstdio>
> using namespace std;
>
> const int N=100001,INF=2000000000;
> struct edge
> {
> 	int v,next;
> }e[N<<1];
> bool vis[N];
> char s[101];
>
> int min(int a,int b)
> {
> 	if(a<b)return a;
> 	return b;
> }
>
> {
> 	while(x<=n)
> 	{
> 		c[x]+=v;
> 		x+=x&-x;
> 	}
> }
>
> void dfs(int u)
> {
> 	vis[u]=true;
> 	int i,v;
> 	{
> 		v=e[i].v;
> 		if(!vis[v])
> 		{
> 			dfs(v);
> 			end[u]=min(end[u],end[v]);
> 		}
> 	}
> 	id++;
> 	pos[u]=id;
> 	end[u]=min(end[u],id);
> }
>
> int sum(int x)
> {
> 	int res=0;
> 	while(x)
> 	{
> 		res+=c[x];
> 		x-=x&-x;
> 	}
> 	return res;
> }
>
> int main()
> {
> 	int m,i,tot=0,u,v,x;
> 	scanf("%d",&n);
> 	for(i=1;i<n;i++)
> 	{
> 		scanf("%d%d",&u,&v);
> 		tot++;
> 		e[tot].v=v;
> 		tot++;
> 		e[tot].v=u;
> 		end[i]=INF;
> 	}
> 	end[n]=INF;
> 	dfs(1);
> 	scanf("%d",&m);
> 	while(m)
> 	{
> 		scanf("%s%d",s,&x);
> 		if(s[0]=='Q')printf("%d\n",sum(pos[x])-sum(end[x]-1));
> 		else
> 		{
> 			vis[x]=!vis[x];
> 		}
> 		m--;
> 	}
> 	return 0;
> }
```

Followed by: