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

树状数组AC，线段树TLE……

Posted by liu_cheng_ao at 2016-09-17 13:03:20 on Problem 3321
```偷懒不记左右端点数组
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<algorithm>

using namespace std;

int n,m,a,b,cnt;
int l[120000],r[120000],fa[120000];
int tr[120000];
bool pcked[120000];
#define lbt(a) a&(-a);
#define lt(a) a<<1
#define rt(a) (a<<1)+1
void dfs(int k)
{
l[k]=++cnt;
{
if(to[i]!=fa[k])
{
fa[to[i]]=k;
dfs(to[i]);
}
}
r[k]=cnt;
}
int s(int l,int r,int no,int lq,int rq)
{
int m=(l+r)>>1;
if(l==lq&&r==rq)return tr[no];
else if(rq<=m)
return s(l,m,lt(no),lq,rq);
else if(lq>=m+1)
return s(m+1,r,rt(no),lq,rq);
else
return s(l,m,lt(no),lq,m)+s(m+1,r,rt(no),m+1,rq);
}

void build(int l,int r,int no)
{
int m=(l+r)>>1;
tr[no]=r-l+1;
if(r!=l)
{
build(l,m,lt(no));
build(m+1,r,rt(no));
}
}
void ad(int l,int r,int no,int p,int d)
{
tr[no]+=d;
int m=(l+r)>>1;
if(l!=r){
if(p<=m)
else
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<n;i++)
{
scanf("%d%d",&a,&b);
to[++cntv]=b;
to[++cntv]=a;
}
dfs(1);
build(1,n,1);
scanf("%d",&m);
char op[10];int x;
for(int i=1;i<=m;i++)
{
scanf("%s",&op);
scanf("%d",&x);
if(op[0]=='Q')
printf("%d\n",s(1,n,1,l[x],r[x]));
else if(op[0]=='C')
{
pcked[x]=!pcked[x];
}
}
return 0;
}```

Followed by: