题目大意：给定一个区间，查询子区间里出现次数不小于二的数的个数
此题想了好久没想出来，后来是在网上学习的一个方法
首先按查询区间的右端点进行排序，按右端点从小到大处理
假设pre[a[i]]是与a[i]相同的前一个数的位置，记为left[i]
当查询到第i个数时，对left[left[i]]+1~left[i]的每个数的权值w[]加1
也就是说：左端点在left[left[i]]+1~left[i]内，右端点为i的区间里，出现次数不小于二的数+1
那么对于查询i，答案就是w[left[i]]
因为对于查询L~R，区间里的每个数都小于等于r，因此L~R里的每个数若出现了两次都可能会被w[left[i]]+1
所以这个算法是可行的，而且很奇妙。。
那么对于成段的区间修改，我们可以考虑用线段树lazy标记，但是很麻烦
所以可以用树状数组维护差分序列，更简洁。
差分序列是什么呢？
对于数列 a1, a2, a3 ... an
构造新数列 b1, b2, b3 .. bn
其中b1 = a1
b2 = a2 - a1
b3 = a3 - a2
....
bn = bn - bn-1
新数列就是差分序列
那么要得到ai，就只要算b1~bi的和就行了
用差分序列的好处就是，对于成段的区间修改i~j(权值+1)，出了第i和第j个数，中间的相邻的数的差是不变的
那么只要b(i) + 1, b(j+1) -1 就可以了
这样修改的时间复杂度由O(n)降为O(1)
而查询的时间复杂度由O(1) 升为log(n)，用树状数组维护的话
1 #include<stdio.h> 2 #include<string.h> 3 #include<algorithm> 4 #define maxn 1000100 5 using namespace std; 6 struct node{ 7 int l,r,id; 8 }q[maxn]; 9 int n,m,c,p[maxn],left[maxn],pre[maxn],a[maxn],res[maxn]; 10 11 bool cmp(node a, node b){ 12 return a.r<b.r; 13 } 14 15 void add(int x, int c){ 16 while (x<=n){ 17 p[x]+=c; 18 x+=x&-x; 19 } 20 } 21 22 int get_sum(int x){ 23 int tot=0; 24 while (x){ 25 tot+=p[x]; 26 x-=x&-x; 27 } 28 return tot; 29 } 30 31 void change(int x){ 32 left[x]=pre[a[x]]; 33 pre[a[x]]=x; 34 if (left[x]){ 35 add(left[left[x]]+1,1); 36 add(left[x]+1,-1); 37 } 38 } 39 40 int main(){ 41 scanf("%d%d%d", &n, &c, &m); 42 memset(p,0,sizeof(p)); 43 memset(left,0,sizeof(left)); 44 for (int i=1; i<=n; i++){ 45 scanf("%d", &a[i]); 46 } 47 for (int i=1; i<=m; i++){ 48 scanf("%d%d", &q[i].l, &q[i].r); 49 q[i].id=i; 50 } 51 sort(q+1,q+1+m,cmp); 52 int head=1; 53 for (int i=1; i<=n; i++){ 54 change(i); 55 for (;q[head].r==i;head++) 56 res[q[head].id]=get_sum(q[head].l); 57 } 58 for (int i=1; i<=m; i++) printf("%d ", res[i]); 59 return 0; 60 }