区间众数要求即有次数又要数字最小
#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();
}
}
没有回复内容