hihoCoder 1145 幻想乡的日常（树状数组 + 离线处理）

http://hihocoder.com/problemset/problem/1145?sid=1244164

题意：

幻想乡一共有n处居所，编号从1到n。这些居所被n-1条边连起来，形成了一个树形的结构。

每处居所都居住着一个小精灵。每天小精灵们都会选出一个区间[l,r]，居所编号在这个区间内的小精灵一起来完成一项任务。

特别的，居所相邻的(有边相连的)两个小精灵会自发的组成一队，并且如果a和b相邻b和c相邻，那么a和c也在同一队里面。每天的任务完成之后，队伍就会解散；第二天再根据新的区间组成新的队伍。

给出每天小精灵们选出的区间，你知道每天组成的队伍数量吗？

思路：
越来越觉得树状数组在处理区间问题上真的很强。

将询问按右坐标排序，将顶点按从小到大的顺序看它的子节点是否可以插入。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 const int maxn = 100000+5;
 7 
 8 int tot,n,m;
 9 int head[maxn],c[maxn],ans[maxn];
10 
11 struct node
12 {
13     int v,next;
14 }e[2*maxn];
15 
16 struct Node
17 {
18     int l,r,id;
19     bool operator< (const Node& rhs) const
20     {
21         return r<rhs.r;
22     }
23 }query[maxn];
24 
25 void addEdge(int u, int v)
26 {
27     e[tot].v = v;
28     e[tot].next = head[u];
29     head[u] = tot++;
30 }
31 
32 int lowbit(int x)
33 {
34     return x&-x;
35 }
36 
37 int sum(int x)
38 {
39     int ret = 0;
40     while(x>0)
41     {
42         ret += c[x];
43         x -= lowbit(x);
44     }
45     return ret;
46 }
47 
48 int add(int x)
49 {
50     while(x<=n)
51     {
52         c[x] += 1;
53         x +=lowbit(x);
54     }
55 }
56 
57 int main()
58 {
59     //freopen("in.txt","r",stdin);
60     scanf("%d%d",&n,&m);
61     tot = 0;
62     memset(head,-1,sizeof(head));
63     for(int i=0;i<n-1;i++)
64     {
65         int u,v;
66         scanf("%d%d",&u,&v);
67         addEdge(u,v);
68         addEdge(v,u);
69     }
70     for(int i=0;i<m;i++)
71     {
72         scanf("%d%d",&query[i].l,&query[i].r);
73         query[i].id = i;
74     }
75     int pos = 0;
76     sort(query,query+m);
77     for(int u=1;u<=n;u++)
78     {
79         for(int i=head[u];i!=-1;i=e[i].next)
80             if(e[i].v<u)  add(e[i].v);
81         while(u==query[pos].r && pos<m)
82         {
83             ans[query[pos].id] = query[pos].r-query[pos].l+1-(sum(u)-sum(query[pos].l-1));
84             pos++;
85         }
86     }
87     for(int i=0;i<m;i++)
88         printf("%d
",ans[i]);
89     return 0;
90 }