分块莫队

分块

结合二分查找和

??“蒲公英吗……”

??在乡下的小路旁种着许多蒲公英，而我们的问题正是与这些蒲公英有关。

??为了简化起见，我们把所有的蒲公英看成一个长度为 n 的序列 ()，其中  为一个正整数，表示第 i 棵蒲公英的种类编号。

??而每次询问一个区间[l, r]，你需要回答区间里出现次数最多的是哪种蒲公英，如果有若干种蒲公英出现次数相同，则输出种类编号最小的那个。

注意，你的算法必须是在线的。

输入格式

第一行两个整数 n, m，表示有 n 株蒲公英，m 次询问。

接下来一行 n 个空格分隔的整数 ，表示蒲公英的种类。

再接下来 m 行每行两个整数 ，我们令上次询问的结果为 x（如果这是第一次询问，则 x = 0）。

令 ，如果 l > r，则交换 l, r。

最终的询问区间为[l, r]。

输出格式

输出 m 行。每行一个整数，表示每次询问的结果。

const int N=4e4+100;
int n,m,a[N],map_a[N],map_n;
int cnt,l[300],r[300],pos[N];
vector<int>data[N];
int a_cnt[N],fast[300][300],fast_cnt[300][300],x;
int vis[N];
inline int baoli(int l0,int r0)
{
    memset(a_cnt,0,sizeof(a_cnt));int pot=0,pot_cnt=0;
    _f(k,l0,r0)
    {
        a_cnt[map_a[k]]++;
        if(map_a[k]==pot)pot_cnt++;
        else if(a_cnt[map_a[k]]==pot_cnt)
        {
            if(map_a[k]a_cnt[map_a[k]];
        }
        else if(a_cnt[map_a[k]]>pot_cnt)
        {
            pot=map_a[k],pot_cnt=a_cnt[map_a[k]];
        }
    }
    return pot;
}
inline int erfen(int pot,int l,int r)
{
    int ll=0;int rr=data[pot].size()-1;//都代表data的下标位置
    while(data[pot][ll]<l)
    ll++;
    while(data[pot][rr]>r)
    rr--;
    return rr-ll+1;
}
inline void solve()
{
    int l0=re(),r0=re();
    l0=(l0+x-1)%n+1,r0=(r0+x-1)%n+1;
    if(l0>r0)swap(l0,r0);
    if(l0==r0)
    {
        x=map_a[l0];
        x=a[x];
        chu("%d\n",x);
        return;
    }
    if(pos[l0]==pos[r0])
    {
        x=baoli(l0,r0);
        x=a[x];
        chu("%d\n",x);
        return;
    }
    int k_l0=pos[l0],k_r0=pos[r0];
    if((l[k_l0]==l0)&&(r[k_r0]==r0))
    {
        x=fast[k_l0][k_r0];
        x=a[x];
        chu("%d\n",x);
        return;
    }
    memset(vis,0,sizeof(vis));
    //中间取出来一个众数，两头暴力 扫描
    int pot=fast[k_l0+1][k_r0-1],pot_cnt=fast_cnt[k_l0+1][k_r0-1];//那这数字是多少呢？
    _f(i,l0,l[k_l0+1]-1)
    {
        if(vis[map_a[i]])continue;
        vis[map_a[i]]=1;
        int maybe=erfen(map_a[i],l0,r0);
        if(maybe>pot_cnt)pot=map_a[i],pot_cnt=maybe;
        else if((maybe==pot_cnt)&&(map_a[i]maybe;
        else if(maybe>pot_cnt)pot=map_a[i],pot_cnt=maybe;
    }
    _f(i,r[k_r0-1]+1,r0)
    {
        if(vis[map_a[i]])continue;
        vis[map_a[i]]=1;
        int maybe=erfen(map_a[i],l0,r0);
        if(maybe>pot_cnt)pot=map_a[i],pot_cnt=maybe;
        else if((maybe==pot_cnt)&&(map_a[i]maybe;
        else if(maybe>pot_cnt)pot=map_a[i],pot_cnt=maybe;
    }
    x=pot;x=a[x];
    chu("%d\n",x);
    return;
}
void datamake()
{
    _f(i,1,n)
    {
        data[map_a[i]].push_back(i);
    }
}
 int main()
{
//    freopen("exam.txt","r",stdin);
    n=re();    m=re();
    _f(i,1,n)
    {
        a[i]=re();map_a[i]=a[i]; 
    }
    sort(a+1,a+1+n);//
    map_n=unique(a+1,a+1+n)-a-1;
    _f(i,1,n)
    {
        map_a[i]=lower_bound(a+1,a+1+map_n,map_a[i])-a;
    //    chu("map[%d]:%d\n",i,map_a[i]);
    }
    cnt=sqrt(n);
    _f(i,1,cnt)
    l[i]=cnt*(i-1)+1,r[i]=cnt*i;
    if(r[cnt]1]+1,r[cnt]=n;//这仅仅代表一个块
    _f(i,1,cnt)
    {
        _f(j,l[i],r[i])pos[j]=i;
    }
    _f(i,1,cnt)//从哪个块开始
    {
        memset(a_cnt,0,sizeof(a_cnt));
        int pot=0,pot_cnt=0;//最大众数，出现次数
        int st=l[i],en=r[i];
        _f(k,st,en)
        {
            a_cnt[map_a[k]]++;
            if(map_a[k]==pot)pot_cnt++;
            else if(a_cnt[map_a[k]]==pot_cnt)
            {
                if(map_a[k]a_cnt[map_a[k]];
            }
            else if(a_cnt[map_a[k]]>pot_cnt)
            {
                pot=map_a[k],pot_cnt=a_cnt[map_a[k]];
            }
        }
        fast[i][i]=pot;fast_cnt[i][i]=pot_cnt;
        _f(j,i+1,cnt)//截至哪个块
        {
            st=l[j],en=r[j];
            _f(k,st,en)
            {
                a_cnt[map_a[k]]++;
                if(map_a[k]==pot)pot_cnt++;
                else if(a_cnt[map_a[k]]==pot_cnt)
                {
                if(map_a[k]a_cnt[map_a[k]];
                }
                else if(a_cnt[map_a[k]]>pot_cnt)
                {
                    pot=map_a[k],pot_cnt=a_cnt[map_a[k]];
                }
            }
            fast[i][j]=pot;fast_cnt[i][j]=pot_cnt;
        }
    }//还要处理出来data
    datamake();

//    chu("m:%d\n",m);
    for(register int i=1;i<=m;i++)
    {
        //chu("route:%d\n",i);
        solve();
    }

    return 0;
}
/*
先离散化
分块，q[i][j]存i块，j类蒲公英的出现次数
maxx[i][j]:处在i--j块里面的众数 ,直接大暴力
每个询问{x,y}
处在同一块：遍历：纯二分
不同块， 遍历，二分找呗

6 3 
1 2 3 2 1 2 
1 5 
3 6 
1 5 
*/