主席树调了1h,只能有95分

// luogu-judger-enable-o2
#include<bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)

using namespace std;

inline char nc()
{
    static char buf[1000000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}

inline int read()
{
    char ch;
    int fl=1;
    int x=0;
    do{
      ch= nc();
      if(ch=='-')
        fl=-1;
    }while(ch<'0'||ch>'9');
    do{
        x=(x<<3)+(x<<1)+ch-'0';
        ch=nc();
    }while(ch>='0'&&ch<='9');
    return x*fl;
}

const int MAXN = 40000+10;

struct p_tree
{
    int sum;
    int lcc;
    int rcc;    
} ;

p_tree t[MAXN*20];

int root[MAXN],cnt=0;

struct node
{
    int val;
    int id;
    friend bool operator < (node a1,node a2)
    {
        return a1.val<a2.val;   
    } 
};

node a[MAXN];

int c[MAXN];

int zsi,zsz;

bool bz; 

int ck;

inline void update(int& rt,int x,int k,int l,int r)
{
    t[++cnt]=t[rt];
    rt = cnt;
    t[rt].sum+=k;
    if(l==r) return;
    int mid=(l+r)>>1;
    if(x<=mid) update(t[rt].lcc,x,k,l,mid);
    else update(t[rt].rcc,x,k,mid+1,r);
}

inline void query(int l,int r,int x,int y)
{
    if(bz) return;
    if(x==y)
    {
        if(zsz<t[r].sum-t[l].sum)
        {
            zsz=t[r].sum-t[l].sum;
            zsi=x;
        }
        if(zsz>(ck)/2) 
        {
            bz = true;
        }
        return;
    }
    else
    {
        if(zsz<t[t[r].lcc].sum-t[t[l].lcc].sum)
        {
            query(t[l].lcc,t[r].lcc,x,(x+y)>>1);    
        }
        if(zsz<t[t[r].rcc].sum-t[t[l].rcc].sum)
        {
            query(t[l].rcc,t[r].rcc,((x+y)>>1)+1,y);    
        } 
    } 
}

int n,q;

int rankk[MAXN];

int main()
{
    n=read(),q=read();
    for(register int i=1;i<=n;i++) a[i].val=read(),a[i].id=i;;
    root[0]=0;
    t[0].sum=t[0].lcc=t[0].rcc=0;
    sort(a+1,a+n+1);
    int top=0;
    for(register int i=1;i<=n;i++)
    {
        if(a[i].val!=a[i-1].val) top++;
        c[a[i].id]=top;
        rankk[top]=a[i].val;
    }
    for(register int i=1;i<=n;i++)
    {
        root[i]=root[i-1];
        update(root[i],c[i],1,1,40000);
    }
    zsi=0,zsz=0;
    for(register int i=1;i<=q;i++)
    {
        bz = false;
        int l0=read(),r0=read();
        int u=(l0+rankk[zsi]-1)%n+1,v=(r0+rankk[zsi]-1)%n+1;
        if(u>v) swap(u,v);
        ck = v-u+1;
        zsi = 0,zsz = 0;
        query(root[u-1],root[v],1,40000);
        printf("%d\n",rankk[zsi]);
    }
} 

第八个点卡不过去。。。已放弃