题意
给出一个序列，在线询问区间众数。如果众数有多个，输出最小的那个。
题解
这是一道分块模板题。
一个询问的区间的众数，可能是中间“整块”区间的众数，也可能是左右两侧零散的数中的任意一个。为了\(O(\sqrt n)\)求出究竟是哪一个，我们需要在一次对两侧零散点的扫描之后\(O(1)\)求出被扫数在区间内的的出现次数。
所以需要预处理的有：
- cnt[i][j]: i在前j块中出现的次数
- mode[i][j]: 第i块到第j块组成的大区间的众数
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
using namespace std;
typedef long long ll;
#define space putchar(' ')
#define enter putchar('\n')
template <class T>
void read(T &x){
char c;
bool op = 0;
while(c = getchar(), c < '0' || c > '9')
if(c == '-') op = 1;
x = c - '0';
while(c = getchar(), c >= '0' && c <= '9')
x = x * 10 + c - '0';
if(op) x = -x;
}
template <class T>
void write(T x){
if(x < 0) x = -x, putchar('-');
if(x >= 10) write(x / 10);
putchar('0' + x % 10);
}
const int N = 40005, B = 200;
int n, m, a[N], lst[N], idx, cnt[N][205], tot[N], vis[N], mode[205][205];
#define st(x) (((x) - 1) * B + 1)
#define ed(x) min((x) * B, n)
#define bel(x) (((x) - 1) / B + 1)
//这次代码写得非常丑陋……连个函数都没有……所以下面的代码中我会加一些注释解释代码含义
int main(){
//读入并离散化
read(n), read(m);
for(int i = 1; i <= n; i++)
read(a[i]), lst[i] = a[i];
sort(lst + 1, lst + n + 1);
idx = unique(lst + 1, lst + n + 1) - lst - 1;
//处理cnt[i][j]，表示数i(当然是离散化后的新数)在前j块中出现的次数
for(int i = 1; i <= n; i++){
a[i] = lower_bound(lst + 1, lst + idx + 1, a[i]) - lst;
for(int j = bel(i); st(j) <= n; j++)
cnt[a[i]][j]++;
}
//处理mode[i][j]，表示第i块到第j块的众数
for(int i = 1, md = 0; st(i) <= n; i++){
memset(tot, 0, sizeof(tot));
for(int j = i, k = st(i); k <= n; k++){
tot[a[k]]++;
if(tot[a[k]] > tot[md] || (tot[a[k]] == tot[md] && a[k] < md)) md = a[k];
if(k == ed(j)) mode[i][j] = md, j++;
}
if(i != 2) continue;
}
//回答询问
int ans = 0;
for(int T = 1; T <= m; T++){
int l, r, md = 0;
read(l), read(r);
l = (l + ans - 1) % n + 1, r = (r + ans - 1) % n + 1;
if(l > r) swap(l, r);
//如果询问的区间在某一个块中
if(bel(l) == bel(r)){
for(int i = l; i <= r; i++){
if(vis[a[i]] != T) tot[a[i]] = 0, vis[a[i]] = T;
tot[a[i]]++;
if(tot[a[i]] > tot[md] || (tot[a[i]] == tot[md] && a[i] < md)) md = a[i];
}
write(ans = lst[md]), enter;
continue;
}
//如果区间跨块，则答案可能是：1. 中间那几个整块表示的大区间的众数；2. 两边零散部分的数
md = mode[bel(l) + 1][bel(r) - 1]; //中间大区间的众数
vis[md] = T, tot[md] = 0;
//这里我一开始忘记了特殊处理md的vis数组，导致计算md出现次数时额外加上了上次询问更新出的tot。
for(int i = l; i <= ed(bel(l)); i++){ //处理左侧零散区间
if(vis[a[i]] != T) tot[a[i]] = 0, vis[a[i]] = T;
tot[a[i]]++;
int x = tot[a[i]] + cnt[a[i]][bel(r) - 1] - cnt[a[i]][bel(l)];
int y = tot[md] + cnt[md][bel(r) - 1] - cnt[md][bel(l)];
if(x > y || (x == y && a[i] < md)) md = a[i];
}
for(int i = st(bel(r)); i <= r; i++){ //处理右侧零散区间
if(vis[a[i]] != T) tot[a[i]] = 0, vis[a[i]] = T;
tot[a[i]]++;
int x = tot[a[i]] + cnt[a[i]][bel(r) - 1] - cnt[a[i]][bel(l)];
int y = tot[md] + cnt[md][bel(r) - 1] - cnt[md][bel(l)];
if(x > y || (x == y && a[i] < md)) md = a[i];
}
write(ans = lst[md]), enter;
}
return 0;
}