poj 3321 Apple Tree(一维树状数组)

题意：

苹果树上n个分叉，Q是询问，C是改变状态。。。。

开始的处理比较难，参考了一下大神的思路，构图成邻接表并用DFS编号

白书上一维树状数组模板：

 1 int lowbit(int x)
 2 {
 3     return x&(-x);
 4 }
 5 void add(int x,int d)   //c[]的下标要从 1开始。
 6 {
 7     while(x <= n)
 8     {
 9         c[x] += d;
10         x +=lowbit(x);
11     }
12 }
13 int sum(int x)  //前x项的和。
14 {
15     int ret = 0;
16     while(x > 0)
17     {
18         ret += c[x];
19         x -= lowbit(x);
20     }
21     return ret;
22 }

AC代码：

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <cstdlib>
  5 #include <algorithm>
  6 using namespace std;
  7 const int maxn = 100010;
  8 int s[maxn],e[maxn],c[maxn],num;
  9 int head[maxn],n,cnt;
 10 bool vis[maxn];
 11 struct node
 12 {
 13     int v,next;
 14 }g[maxn];
 15 
 16 void init()
 17 {
 18     int i;
 19     memset(head,-1,sizeof(head));
 20     cnt = 0; num = 0;
 21     for(i=0; i<=n; i++)
 22     {
 23         c[i] = 0;
 24         vis[i] = false;
 25     }
 26 }
 27 void add_e(int u,int v)
 28 {
 29     g[cnt].v = v;
 30     g[cnt].next = head[u];
 31     head[u] = cnt++;
 32 }
 33 int lowbit(int x)
 34 {
 35     return x&(-x);
 36 }
 37 
 38 void add(int x,int d)
 39 {
 40     while(x <= n)
 41     {
 42         c[x] += d;
 43         x +=lowbit(x);
 44     }
 45 }
 46 int sum(int x)
 47 {
 48     int ret = 0;
 49     while(x > 0)
 50     {
 51         ret += c[x];
 52         x -= lowbit(x);
 53     }
 54     return ret;
 55 }
 56 void dfs(int pos)
 57 {
 58     s[pos] = ++num;
 59     for (int i = head[pos]; i != -1; i = g[i].next)
 60     {
 61         int v = g[i].v;
 62         dfs(v);
 63     }
 64     e[pos] = num;
 65 }
 66 
 67 int main()
 68 {
 69     int x,y,i,q;
 70     char op[5];
 71     scanf("%d",&n);
 72     init();
 73     for(i = 0; i < n-1; i++)
 74     {
 75         cin>>x>>y;
 76         add_e(x,y); //邻接表构图
 77     }
 78     dfs(1); //编号
 79     for (i = 1; i <= n; i++)
 80     add(i,1);
 81     cin>>q;
 82     while (q--)
 83     {
 84         cin>>op>>x;
 85         if (op[0] == 'Q')
 86             printf("%d
",sum(e[x]) - sum(s[x] - 1));  //输出连续的和
 87         else       //改变状态
 88         {
 89             if (!vis[x])
 90             {
 91                 add(s[x],-1); 
 92                 vis[x] = true;
 93             }
 94             else
 95             {
 96                 add(s[x],1);
 97                 vis[x] = false;
 98             }
 99         }
100     }
101     return 0;
102 }

 1 //今天帮师兄做的笔试题，一个数组，求每个数前面比它大的个数
 2 #include <iostream>
 3 #include <cstring>
 4 const int maxn = 2e5 + 10;
 5 using namespace std;
 6 
 7 int c[maxn], n = maxn;
 8 
 9 int lowbit(int x)
10 {
11     return x&(-x);
12 }
13 void add(int x,int d)
14 {
15     while(x <= n)    //这里的n指c数组总数
16     {
17         c[x] += d;
18         x +=lowbit(x);
19     }
20 }
21 int sum(int x)  //求c[1]到c[x]的和
22 {
23     int ret = 0;
24     while(x > 0)
25     {
26         ret += c[x];
27         x -= lowbit(x);
28     }
29     return ret;
30 }
31 
32 int main()
33 {
34     int i, t, n1;
35     while(cin>>n1)
36     {
37         memset(c, 0, sizeof(c));
38         for(i = 1; i <= n1; i++) //c数组从1开始
39         {
40             cin>>t;
41             add(t, 1);
42             if(i != n1)
43             cout<<sum(maxn-10)-sum(t)<<" ";
44             else
45             cout<<sum(maxn-10)-sum(t)<<endl;
46         }
47     }
48     return 0;
49 }