回滚莫队求条

#include<bits/stdc++.h>
using namespace std;
int ans[300005];
int l[300005],r[300005],b[300005];
int lx[1005],ry[1005];
int be[300005],tot;
int c,n,m,k,a[300005],x,y;
int tab[600015],len;
struct block
{
    int l,r,id;
};
block bl[3000005];
inline bool cmp(block l,block r)
{
    if(be[l.l]==be[r.l])return l.r<r.r;
    return be[l.l]<be[r.l];
}
inline void add(int x)
{
    ++tab[x];
    if(tab[x]>tab[c])
    	c=x;
    if(tab[x]==tab[c]&&x<c)
        c=x;
}
inline void del(int x)
{
    --tab[x];
}
int ttab[600005];
signed main()
{
    cin>>n;m=n;
    len=sqrt(n);
    for(int i=1;i<=n;i++)
        cin>>a[i],b[i]=a[i];
    sort(b+1,b+n+1);
    int len_=unique(b+1,b+n+1)-b-1;
    for(int i=1;i<=n;i++)
    	a[i]=lower_bound(b+1,b+len_+1,a[i])-b;
    tot=n/len;
    if(n%len)++tot;
    for(int i=1;i<=tot;i++)
    	lx[i]=(i-1)*len+1,ry[i]=i*len;
    ry[tot]=n;
    for(int i=1;i<=n;i++)
    	be[i]=(i-1)/len+1;
    for(int i=1;i<=m;i++)
        cin>>bl[i].l>>bl[i].r,bl[i].id=i;
    sort(bl+1,bl+m+1,cmp);
    x=1,y=1,c=a[1],tab[a[1]]=1;
    int backup=a[1];
    for(int i=1;i<=m;i++)
    	cout<<bl[i].l<<" "<<bl[i].r<<" "<<bl[i].id<<'\n';
    for(int i=1;i<=m;i++)
    {
		int p=be[bl[i].l],tc=0,ac=0;
    	if(p!=be[bl[i-1].l])
		{
			y=ry[p],x=y,c=a[ry[p]];
			//cout<<i<<"-"<<c<<endl;
			memset(tab,0,sizeof(tab));
			backup=c;
			tab[c]=1;
		}
    	if(p==be[bl[i].r])
    	{
    		for(int j=bl[i].l;j<=bl[i].r;j++)
    			ttab[a[j]]++;
    		for(int j=bl[i].l;j<=bl[i].r;j++)
    			if(ttab[a[j]]>tc)
					tc=ttab[a[j]],ac=a[j];
    		memset(ttab,0,sizeof(ttab));
    		ans[bl[i].id]=ac;
    		//cout<<i<<":"<<ac<<"\n";
    		continue;
		}
        while(y<bl[i].r)++y,add(a[y]);
        backup=c;
        int yx=x;
		while(x>bl[i].l)--x,add(a[x]);
		ans[bl[i].id]=c;
		while(x<yx)del(a[x]),++x;
		c=backup;
        //cout<<i<<" "<<c<<"\n";
       // while(y>bl[i].r)del(a[y]),--y;
        
    }
    for(int i=1;i<=m;i++)
    	cout<<b[ans[i]]<<'\n';
    return 0;
}