题目描述

Description

Input

修正一下
l = (l_0 + x - 1) mod n + 1, r = (r_0 + x - 1) mod n + 1

Output

Sample Input

6 3 
1 2 3 2 1 2 
1 5 
3 6 
1 5 

Sample Output

1 
2 
1 

HINT

题目分析

区间众数 的做法
分块。
先需处理出块和块之间的众数
再存储每个数出现的位置
对于每次询问 整块的众数直接查询 零散的部分每个数二分出在询问的位置里的个数

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m,siz;
struct your
{           
    int val,id;
}a[40010];
int cmp(your j,your k)
{
    return j.val<k.val;
}
int v[40010],ref[40010];
vector<int> pos[40010];
int ans,maxx;
int num[40010];
int sum[810][810];
void work(int x,int y,int c)
{
    if(!c||num[c]) return ;
    int l=0,r=pos[c].size()-1,mid;
    int dx=0;
    while(l<r)
    {
        mid=(l+r)>>1;
        if(pos[c][mid]>=x) r=mid;
        else l=mid+1;
    }
    dx=r;
    l=0,r=pos[c].size();
    int dy=0;
    while(l<r)
    {
        mid=(l+r)>>1;
        if(pos[c][mid]<=y) l=mid+1;
        else r=mid;
    }
    dy=l-1;
    num[c]=dy-dx+1;
    if(num[c]>num[maxx]||(num[c]==num[maxx]&&c<maxx)) 
        maxx=c;
    return ;
}
int main()
{
    scanf("%d%d",&n,&m);
    siz=int(sqrt(double(n)/log(n)));
    for(int i=0;i<n;i++) scanf("%d",&a[i].val),a[i].id=i;
    sort(a,a+n,cmp);
    for(int i=0;i<n;i++)
    {
        if(!i||a[i].val>a[i-1].val) ref[++ref[0]]=a[i].val;
        v[a[i].id]=ref[0];
    }
    for(int i=0;i<n;i++) pos[v[i]].push_back(i);
    for(int i=0;i*siz<n;i++)
    {
        memset(num,0,sizeof num);
        maxx=0;
        for(int j=i*siz;j<n;j++)
        {
            num[v[j]]++;
            if(num[v[j]]>num[maxx]||(num[v[j]]==num[maxx]&&v[j]<maxx))
                maxx=v[j];
            sum[i][j/siz]=maxx;
        }
    }
    memset(num,0,sizeof num);
    for(int x,y,i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        x=(x+ans-1+n)%n,y=(y+ans-1+n)%n;
        if(x>y) swap(x,y);
        if(x/siz==y/siz)
        {
            maxx=0;
            for(int j=x;j<=y;j++)
            {
                num[v[j]]++;
                if(num[v[j]]>num[maxx]||(num[v[j]]==num[maxx]&&v[j]<maxx))
                    maxx=v[j];
            }
            ans=ref[maxx];
            printf("%d\n",ans);
            for(int j=x;j<=y;j++) num[v[j]]--;
        }
        else
        {
            maxx=0;
            work(x,y,sum[x/siz+1][y/siz-1]);
            for(int j=x;j<x/siz*siz+siz;j++) work(x,y,v[j]); 
            for(int j=y/siz*siz;j<=y;j++) work(x,y,v[j]);
            ans=ref[maxx];
            printf("%d\n",ans);
            num[sum[x/siz+1][y/siz-1]]=0;
            for(int j=x;j<x/siz*siz+siz;j++) num[v[j]]=0; 
            for(int j=y/siz*siz;j<=y;j++) num[v[j]]=0;
        }
    }
    return 0;
}