题目大意：给定一个区间，查询子区间里出现次数不小于二的数的个数
此题想了好久没想出来，后来是在网上学习的一个方法
首先按查询区间的右端点进行排序，按右端点从小到大处理
假设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)，用树状数组维护的话
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define maxn 1000100
using namespace std;
struct node{
int l,r,id;
}q[maxn];
int n,m,c,p[maxn],left[maxn],pre[maxn],a[maxn],res[maxn];
bool cmp(node a, node b){
return a.r<b.r;
}
void add(int x, int c){
while (x<=n){
p[x]+=c;
x+=x&-x;
}
}
int get_sum(int x){
;
while (x){
tot+=p[x];
x-=x&-x;
}
return tot;
}
void change(int x){
left[x]=pre[a[x]];
pre[a[x]]=x;
if (left[x]){
add(left[left[x]]+,);
add(left[x]+,-);
}
}
int main(){
scanf("%d%d%d", &n, &c, &m);
memset(p,,sizeof(p));
memset(left,,sizeof(left));
; i<=n; i++){
scanf("%d", &a[i]);
}
; i<=m; i++){
scanf("%d%d", &q[i].l, &q[i].r);
q[i].id=i;
}
sort(q+,q++m,cmp);
;
; i<=n; i++){
change(i);
for (;q[head].r==i;head++)
res[q[head].id]=get_sum(q[head].l);
}
; i<=m; i++) printf("%d\n", res[i]);
;
}