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

为什么没用vector，就随机访问数组也超时

Posted by JeremyCorbyn at 2018-04-07 19:04:09 on Problem 3321
```#include<cstdio>
#define N 100005

int n, atree[N],bit[N];

struct folk
{
int apple, start, end,offcnt,p[10];
}tree[N];

int lowbit(int k)
{
return k&(-k);
}

{
while (k <= n)
{
atree[k] += v;
k += bit[k];
}
}

int sum(int k)
{
int s=0;
while(k>0)
{
s += atree[k];
k -= bit[k];
}
return s;
}

void dfs(int a,int &pos)
{
int i;
tree[a].start = pos;
for (i = 0; i < tree[a].offcnt; i++)
dfs(tree[a].p[i], ++pos);
tree[a].end = pos;
}

int main()
{
int i,m,t1,t2;
char c;
scanf_s("%d", &n);
for(i=0;i<n-1;i++)
{
scanf_s("%d%d", &t1, &t2);
tree[t1].p[tree[t1].offcnt++] = t2;
}
for (i = 1; i <= n; i++)
bit[i] = lowbit(i);
t1 = 1;
dfs(1, t1);
for (i = 1; i <= n; i++)
scanf_s("%d", &m);
for(i=0;i<m;i++)
{
getchar();
scanf_s("%c%d", &c, 1, &t1);
if (c == 'C')
{
tree[t1].apple ^= 1;
}
else
printf("%d\n", sum(tree[t1].end) - sum(tree[t1].start - 1));
}
return 0;
}```

Followed by: