只要会了回滚莫队的话

这道题还是很好做的

不然的话就可能陷入普通莫队加线段树修改的O（n*sqrt(n)*logn）的误区

用双向链表实现

不过我写了半天也没有写出来

干脆就不写了

顺手再贴上dalao的优美代码（真实）

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define my_min(a,b) ((a)<(b)?(a):(b))#define my_max(a,b) ((a)>(b)?(a):(b))using namespace std;struct questions{ int l,r,xh; questions(int _xh=0,int _l=0,int _r=0){ xh=_xh , l=_l , r=_r ; }}qs[500005],que[500005];bool cmp_l(const questions &a,const questions &b){ return a.l
          
           =i && qs[now].l<=my_min(n,i+b_size-1)) que[++qnum]=qs[now] , ++now ; if(!qnum) continue ; ++TTT ; //for(int j=1;j<=n;++j) has[j]=false , bl[j]=br[j]=j ; / sort(que+1,que+qnum+1,cmp_r) ; int now_r=my_min(n,i+b_size-1) ; for(int j=1;j<=qnum;++j){ while(now_r
           
            =que[j].l;--k){ int t=P[k] ; get_it(t,true) ; } ans[que[j].xh]=now_ans , restore() ; for(int k=my_min(my_min(n,i+b_size-1),que[j].r);k>=que[j].l;--k){ has[P[k]]=false ; } now_ans=t_ans ; } } for(int i=1;i<=m;++i) printf("%d\n",ans[i]) ;}int main(){ freopen("ants.in","r",stdin) ; freopen("ants.out","w",stdout) ; scanf("%d%d",&n,&m) ; for(int i=1;i<=n;++i) scanf("%d",&P[i]) ; for(int i=1;i<=m;++i){ scanf("%d%d",&qs[i].l,&qs[i].r) ; qs[i].xh=i ; } solve(); return 0 ;}