bzoj 1878 离线+树状数组/主席树（区间不同数个数）

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=1878

题意：

求给定区间内不同数的个数。

之前详细用主席树解过，现在主要练习下离线做法（好写并且很快）

比莫队好一点的方法是树状数组

last记录该数之前出现的位置。

将询问按右端点排序。

i表示右端点，不断右移，前缀和记录有多少数，询问按下标往后移，与i相同时查询一下。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;

struct node{
    int l,r,id;
    bool operator <(node a)const{
        return r<a.r;
    }
}que[maxn];

int n,m,tree[maxn],a[maxn],pre[maxn],last[maxn],ans[maxn];

int lowbit(int i){
    return i&(-i);
}

void add(int i,int x){
    while(i<=n){
        tree[i]+=x;
        i+=lowbit(i);
    }
}
int query(int i){
    int sum=0;
    while(i>0){
        sum+=tree[i];
        i=i-lowbit(i);
    }
    return sum;
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&que[i].l,&que[i].r);
        que[i].id=i;
    }
    sort(que+1,que+1+m);
    int rnow=1;
    for(int i=1;i<=n;i++){
        if(last[a[i]]) add(last[a[i]],-1);
        add(i,1);
        //printf("%d %d %d  %d\n",i,a[i],last[a[i]],rnow);
        last[a[i]]=i;
        while(que[rnow].r==i){
            ans[que[rnow].id]=query(que[rnow].r)-query(que[rnow].l-1);
            rnow++;
        }
    }
    for(int i=1;i<=m;i++)
        printf("%d\n",ans[i]);
    return 0;
}