线段树36pts求调

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[1000010],latest[1000010],last[1000010],ans[1000010],n,m;
bool f[1000010];
struct node{
    int id,l,r;
}d[1000010];
bool operator < (const node &a,const node &b){
    return a.r<b.r;
}
struct SegmentTree{
    int l,r,sum;
    #define l(p) t[p].l
    #define r(p) t[p].r
    #define sum(p) t[p].sum
}t[4000010];
template<typename T> inline void read(T &x){
    x=0;
    char ch=getchar();
    bool fl=true;
    while(!isdigit(ch)){
        if(ch=='-') fl=false;
        ch=getchar();
    }
    while(isdigit(ch)){
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    if(!fl) x=-x;
}
template<typename T> inline void write(T x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9) write(x/10);
    putchar(x%10^48);
}
inline void build(int p,int l,int r){
    l(p)=l,r(p)=r;
    if(l==r) return;
    int mid=(l+r)>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
}
inline void change(int p,int x,int v){
    if(l(p)==r(p)){
        sum(p)=v;
        return;
    }
    int mid=(l(p)+r(p))>>1;
    if(x<=mid) change(p<<1,x,v);
    else change(p<<1|1,x,v);
    sum(p)=sum(p<<1)+sum(p<<1|1);
}
inline int ask(int p,int l,int r){
    if(l<=l(p)&&r>=r(p)) return sum(p);
    int mid=(l(p)+r(p))>>1,val=0;
    if(l<=mid) val+=ask(p<<1,l,r);
    if(r>mid) val+=ask(p<<1|1,l,r);
    return val;
}
signed main(){
    int x=1;
    read(n);
    for(int i=1;i<=n;++i){
        read(a[i]);
        if(!f[a[i]]) latest[a[i]]=i;
        else{
            last[i]=latest[a[i]];
            latest[i]=i;
        }
        f[a[i]]=true;
    }
    build(1,1,n);
    read(m);
    for(int i=1;i<=m;++i){
        read(d[i].l),read(d[i].r);
        d[i].id=i;
    }
    sort(d+1,d+m+1);
    for(int pos=1;pos<=n&&x<=m;++pos){
        change(1,pos,1);
        if(last[pos]) change(1,last[pos],0);
        while(pos==d[x].r){
            ans[d[x].id]=ask(1,d[x].l,d[x].r);
            ++x;
        }
    }
    for(int i=1;i<=m;++i){
        write(ans[i]);
        putchar('\n');
    }
    return 0;
}