[Violet] 蒲公英（分块）

区间众数要求即有次数又要数字最小

#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef vector<string> VS;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
inline int log_2(int x) {return 31-__builtin_clz(x);}
inline int popcount(int x) {return __builtin_popcount(x);}
inline int lowbit(int x) {return x&-x;}
vector<int> vx;
void divide(){sort(vx.begin(),vx.end());vx.erase(unique(vx.begin(),vx.end()),vx.end());}
inline int mp(int x) {return upper_bound(vx.begin(),vx.end(),x)-vx.begin();}
const int N = 40010 , B = 300;
//f[i][j]表示i块到j块的众数出现次数和是谁
int a[N],s[B][N],st[B],en[B],c[N];
PII f[B][B];
inline void up(PII &a,int v,int x) 
{
	if(a.x < v) a.x = v, a.y = x;
	else if(a.x == v) a.y = min(x,a.y);
}
int n,q;
inline int sum(int L,int R,int x) {return s[R][x] - s[L-1][x];}
void pre_f()
{
	int m = n/B;
    for(int i=0;i<=m;++i)
    {
        PII ans = {0,0};
        for(int j=i;j<=m;++j)
        {
        	for(int k=st[j];k<=en[j];++k)
         	c[a[k]]++, up(ans,c[a[k]],a[k]);
         	f[i][j] = ans;
        } 
        memset(c,0,sizeof c);
    }
}
void pre_s()
{
	memset(s,0,sizeof s);
	int m = n/B;
	for(int i=1;i<=n;++i) s[i/B][a[i]] ++;
	for(int i=1;i<=m;++i)
	 for(int j=1;j<=n;++j)
	 s[i][j] += s[i-1][j];
}
PII query(int l,int r)
{
    int L = l/B, R = r/B;
    //一定要注意此处是L+1>=R,符号不要写反了
    if(L+1>=R)
    {
        PII ans = {0,0};
        for(int i=l;i<=r;++i) c[a[i]]++, up(ans,c[a[i]],a[i]);
        for(int i=l;i<=r;++i) c[a[i]] = 0;
        return ans;
    }
    PII ans = f[L+1][R-1];
    for(int i=l;i<=en[L];++i) c[a[i]]++, up(ans,c[a[i]]+sum(L+1,R-1,a[i]),a[i]);
    for(int i=st[R];i<=r;++i) c[a[i]]++, up(ans,c[a[i]]+sum(L+1,R-1,a[i]),a[i]);
    for(int i=l;i<=en[L];++i) c[a[i]] = 0;
    for(int i=st[R];i<=r;++i) c[a[i]] = 0;
    return ans;
}
void solve()
{
    vx.clear();
    memset(s,0,sizeof s);
    cin>>n>>q;
    for(int i=1;i<=n;++i) en[i/B] = i;
    for(int i=n; i;--i) st[i/B] = i;
    for(int i=1;i<=n;++i) 
    {
        cin>>a[i];
        vx.push_back(a[i]);
    }
    //离散化
    divide();
    for(int i=1;i<=n;++i) a[i] = mp(a[i]);
    
    pre_f(), pre_s();
    memset(c,0,sizeof c);
    PII ans = {0,0};
    int res = 0;
    while(q--)
    {
        int l,r;
        cin>>l>>r;
        l = (l+res-1+n)%n + 1, r = (r+res-1+n)%n + 1;
        if(l>r) swap(l,r);
        ans = query(l,r);
        res = vx[ans.y-1];
        cout<<res<<'\n';
    } 
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T = 1;
    //cin>>T;
    while(T--)
    {
        solve();
    }
}