rt。record

主要这种写法不开vec会CE捏

#include <bits/stdc++.h>
using namespace std;
const int VL{1},VR(1e6),N(1e6);
struct tnode;
vector<tnode> mem;
struct pnode
{
    int id;
    tnode& operator*(){return mem[id];}
    tnode* operator->(){return &mem[id];}
    pnode& operator=(pnode n){id=n.id;return *this;}
    pnode(int p=0):id{p}{}
};
struct tnode
{
    pnode l,r;
    int sz;
};
pnode new_tnode(){mem.emplace_back();return mem.size()-1;}
pnode tree[N+5];
int pre[VR+5];
pnode Insert(pnode p,int k,int v,int cnt)
{
    pnode q{new_tnode()};*q=*p;
    q->sz+=v;
    if (cnt==1) return q;
    int cp{cnt>>1};
    if (k<=cp) q->l=Insert(p->l,k,v,cp);
    else q->r=Insert(p->r,k-cp,v,cnt-cp);
    return q;
}
int query(pnode p,int k,int cnt)
{
    if (p.id==0) return 0;
    if (cnt==1) return p->sz;
    int cp{cnt>>1};
    if (k<=cp) return p->r->sz+query(p->l,k,cp);
    else return query(p->r,k-cp,cnt-cp);
}
int main()
{
    int n;cin>>n;
    mem.emplace_back();
    for (int i{1};i<=n;++i)
    {
        int a;scanf("%d",&a);
        tree[i]=Insert(tree[i-1],i,1,n);
        if (pre[a]) tree[i]=Insert(tree[i],pre[a],-1,n);
        pre[a]=i;
    }
    int m;cin>>m;
    while (m--)
    {
        int l,r;scanf("%d %d",&l,&r);
        printf("%d\n",query(tree[r],l,n));
    }
    return 0;
}