Given a sequence of integers a1, a2, ..., an and q pairs of integers (l 1, r1), (l2, r2), ..., (lq, rq), find count(l1, r1), count(l2, r2), ..., count(lq, rq) where count(i, j) is the number of different integers among a 1, a2, ..., ai , aj , aj + 1, ..., an.
输入描述：
The input consists of several test cases and is terminated by end-of-file. The first line of each test cases contains two integers n and q.
The second line contains n integers a 1, a2, ..., an. The i-th of the following q lines contains two integers l i and ri .
输出描述： For each test case, print q integers which denote the result.
备注 * 1 ≤ n, q ≤ 10 5 * 1 ≤ ai ≤ n * 1 ≤ l i , ri ≤ n * The number of test cases does not exceed 10.
示例1:
输入
3 2 1 2 1 1 2 1 3 4 1 1 2 3 4 1 3
输出
2 1 3
题意就是求去掉(i-1,j-1)区间得数以后剩余的不同数的个数
也就是求(1,l)和(r,n)中不同数的个数,因为这两个区间不能直接合并在一起，所以比赛的时候我是通过倍增区间使两个区间合并在一起
倍增区间后，我们所要求的区间就是(r,n+l)，然后就是一个求区间不同数的问题了
比赛的时候我用的是主席树，比赛结束后叉姐直播说用的树状数组，于是看了别人的博客用树状数组写了遍
参考博客：https://www.cnblogs.com/kkrisen/p/3879517.html
下面是树状数组的用法：
我的做法是把区间排好序，针对某个区间在树状数组上更新以及查询相应值，这样能准确查出结果，但又不影响之后的查询
具体来说，先把区间按右端点进行排序，然后从小区间开始，树状数组的含义就是指以当前r为结尾的前缀区间的元素种类数，简单点说，就是我当前扫到l _ r区间，把l - r区间还没在树状数组上更新的值，更新一遍，在之前已经存在了的值先删掉再更新一遍，确保我确定的元素都是往r靠的，这样才能保证求取区间正确
比如我 1 2 2 1 3，当我r移到3的时候，加入前面的1还没在树状数组里更新过（但其实之前已经有读过1了）那就把之前的1的影响删掉，重新在这个3左边这个下标为4的位置给树状数组 add 1.这样确保之后不管我是查询 4 5 或者 1 5，元素1都只算了一次，但都没遗落（想想如果元素1一直在下标1那里，我查询4 5，就不会有1了）
总之：
所以这就是这个离线用法的妙处，尤其要理解树状数组在这个题目代表的含义是什么，即当前 以r结尾的区间的元素种类个数，为了维护这个值的准确性，必须把没出现过的，加入到树状数组中，之前已经出现过了并且再次出现的，以再次出现的位置为准。
每次对区间不用一开始就扫，每个就只要扫一次就可以了，用个vis数组记录哪个出现了，出现在什么位置，就不用重新扫了，否则会超时，这样，总共也就扫了n下而不是n*q（这里数字小用vis更快，用map会tle）
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
const int N = 300010*2;
int n, vis[N];
struct BIT {
int c[N];
void init(int n) {
for (int i=0;i<=n;i++) c[i]=0;
}
void add(int loc,int v) {
while (loc<=2*n) {
c[loc]+=v;
loc+=loc&(-loc);
}
}
int sum(int loc) {
int ret=0;
while (loc) {
ret+=c[loc];
loc-=loc&(-loc);
}
return ret;
}
}T;
struct node {
int l,r,id;
bool operator <(const node&rhs) const {
//if (l==rhs.l) return r<rhs.r;
return r<rhs.r;
}
}query[2000000+10];
int ans[2000000+10];
int A[N];
int main() {
while (scanf("%d",&n)!=EOF) {
int q;
scanf("%d",&q);
memset( vis, 0, sizeof(vis) );
T.init(2*n);
for (int i=1;i<=n;i++) scanf("%d",&A[i]), A[n+i] = A[i];
for (int i=0;i<q;i++) {
int le, ri;
scanf("%d%d",&le,&ri);
query[i].l = ri, query[i].r = n+le;
//scanf("%d%d",&query[i].l,&query[i].r);
query[i].id=i;
}
sort(query,query+q);
int cur=1;
for (int i=0;i<q;i++) {
for (int j=cur;j<=query[i].r;j++) {
if (vis[A[j]]) {
T.add(vis[A[j]],-1);
}
T.add(j,1);
vis[A[j]] = j;
}
cur=query[i].r+1;
ans[query[i].id]=T.sum(query[i].r)-T.sum(query[i].l-1);
}
for (int i=0;i<q;i++) {
printf("%d
",ans[i]);
}
}
return 0;
}
在贴一份主席树的代码，比赛时候A的代码，他优化数据后还是过了
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1e6 + 10;
int n,q;
int cnt = 0;
struct Node
{
int l,r,sum;
} p[maxn << 3];
int la[maxn << 3];
int a[maxn << 3];
int root[maxn << 3];
int build(int l,int r)
{
int nc = ++cnt;
p[nc].sum = 0;
p[nc].l = p[nc].r = 0;
if (l == r) return nc;
int m = l + r >> 1;
p[nc].l = build(l,m);
p[nc].r = build(m+1,r);
return nc;
}
int update(int pos,int c,int v,int l,int r)
{
int nc = ++cnt;
p[nc] = p[c];
p[nc].sum += v;
if (l == r) return nc;
int m = l+r>>1;
if (m >= pos)
{
p[nc].l = update(pos,p[c].l,v,l,m);
}
else
{
p[nc].r = update(pos,p[c].r,v,m+1,r);
}
return nc;
}
int query(int pos,int c,int l,int r)
{
if (l == r) return p[c].sum;
int m = l + r >> 1;
if (m >= pos)
{
return p[p[c].r ].sum + query(pos,p[c].l,l,m);
}
else return query(pos,p[c].r,m+1,r);
}
int main()
{
while(scanf("%d %d",&n,&q) != EOF)
{
cnt=0;
memset(la,-1,sizeof la);
for (int i = 1; i <= n; ++i)
{
scanf("%d",a+i);
a[n+i]=a[i];
}
root[0] = build(1,2*n);
for (int i = 1 ; i <= 2*n; ++i)
{
int v = a[i];
if (la[v] == -1)
{
root[i] = update(i,root[i-1],1,1,2*n);
}
else
{
int t = update(la[v],root[i-1],-1,1,2*n);
root[i] = update(i,t,1,1,2*n);
}
la[v] = i;
}
while(q--)
{
int x,y;
scanf("%d %d",&x, &y);
printf("%d
",query(y,root[n + x],1,2*n));
///printf("%d
",query(1,root[x],1,2*n)+query(y,root[n],1,2*n));
}
}
return 0;
}