题目：这里
题意：
在2016年，佳媛姐姐刚刚学习了树，非常开心。现在他想解决这样一个问题：给定一颗有根树（根为1），有以下
两种操作：1. 标记操作：对某个结点打上标记（在最开始，只有结点1有标记，其他结点均无标记，而且对于某个
结点，可以打多次标记。）2. 询问操作：询问某个结点最近的一个打了标记的祖先（这个结点本身也算自己的祖
先）你能帮帮他吗?
Input
输入第一行两个正整数N和Q分别表示节点个数和操作次数接下来N-1行，每行两个正整数u,v(1≤u,v≤n)表示u到v
有一条有向边接下来Q行，形如“opernum”oper为“C”时表示这是一个标记操作,oper为“Q”时表示这是一个询
问操作对于每次询问操作，1 ≤ N, Q ≤ 100000。
Output
输出一个正整数，表示结果
Sample Input
5 5
1 2
1 3
2 4
2 5
Q 2
C 2
Q 2
Q 5
Q 3
1 2
1 3
2 4
2 5
Q 2
C 2
Q 2
Q 5
Q 3
Sample Output
1
2
2
1
2
2
1
HINT
明显与两个相同的数在数组中的位置有关系。
求出颜色数组的前缀(前面一个该颜色值的位置)或者后缀(后一个该颜色的位置，以后缀为例)，这里可以用树状数组解决，将给没个询问区间按照左范围从小到大
排序，然后遍历一边大区间1到n，当 i 小于询问范围左端点的的时候将其加入树状数组，等于询问范围左端点的时候既求区间范围和，注意的是，由于只有同种
颜色的花的数目大于1才算，所以事先将符合条件的花先加进数组，然后遍历的时候考虑失去 i 这个位置的时候是加一还是减一
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 using namespace std; 6 7 const int M = 1e6 + 10; 8 int has[M],has1[M],vis[M],b[M],ans[M],n; 9 int q[M]; 10 11 struct node{ 12 int x,y,id; 13 }a[M]; 14 15 int lowbit(int x){return x&(-x);} 16 17 void add(int x,int y) 18 { 19 while (x<=M){ 20 has[x]+=y; 21 x+=lowbit(x); 22 } 23 } 24 25 int getsum(int x) 26 { 27 int ans=0; 28 while (x>0){ 29 ans+=has[x]; 30 x-=lowbit(x); 31 } 32 return ans; 33 } 34 35 bool cmp(node a,node b) 36 { 37 if (a.x==b.x) return a.y<b.y; 38 return a.x<b.x; 39 } 40 41 int main() 42 { 43 int c,m; 44 bool flag=false; 45 scanf("%d%d%d",&n,&c,&m); 46 memset(vis,0,sizeof(vis)); 47 memset(has1,0,sizeof(has1)); 48 for (int i=1 ; i<=n ; i++){ 49 scanf("%d",&b[i]); 50 /*if (has1[b[i]]==0) vis[i]=i,has1[b[i]]=i; 51 else{ 52 vis[i]=has1[b[i]]; 53 has1[b[i]]=i; 54 }*/ 55 } 56 for(int i=n ;i>=1 ; i--){ //求后缀 57 vis[i]=has1[b[i]]; 58 has1[b[i]]=i; 59 } 60 for (int i=1 ; i<=m ; i++){ 61 scanf("%d%d",&a[i].x,&a[i].y); 62 a[i].id=i; 63 } 64 for(int i=1 ; i<=c ; i++){ //满足的先加上 65 if (vis[has1[i]]) 66 add(vis[has1[i]],1); 67 //cout<<has1[i]<<endl; 68 } 69 sort(a+1,a+m+1,cmp); 70 int j=1; 71 // memset(q,0,sizeof(q)); 72 for(int i=1 ; i<=m ; i++){ 73 while (j<a[i].x){ 74 if (vis[vis[j]])add(vis[vis[j]],1); 75 if (vis[j]) add(vis[j],-1); 76 j++; 77 } 78 ans[a[i].id]=getsum(a[i].y)-getsum(a[i].x-1); 79 } 80 for (int i=1 ; i<=m ; i++){ 81 printf("%d ",ans[i]); 82 } 83 //cout<<getsum(1)<<endl; 84 return 0; 85 }