https://www.acwing.com/problem/content/251/
题意：给一段长度至多40000的序列，每次强制在线访问一段区间[L,R]，询问区间的众数（若有多个，输出最小的），询问至多50000次。
思路：lyd给的方法一，一种全新的分块思路。众数不可以通过线段树操控，当然也不可以又多个块的众数合并而得。这种全新的思路是用长短不一的大块去覆盖整个区间。每次访问的时候找到包含于询问区间的最大的大块，直接在大块上面修改并统计，最后撤销修改。
细节蛮多的。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
int a[40005];
int rnk[40005], ele;
struct Block {
int L, R;
int cnt[40005];
int maxcnt, maxcntid;
void Build(int _L, int _R) {
L = _L, R = _R;
memset(cnt, 0, sizeof(cnt[0]) * (ele + 1));
maxcnt = 0, maxcntid = -1;
for(int i = L; i <= R; ++i) {
cnt[a[i]]++;
if(cnt[a[i]] > maxcnt || cnt[a[i]] == maxcnt && a[i] <= maxcntid) {
maxcnt = cnt[a[i]];
maxcntid = a[i];
}
}
}
} block[1800];
int T = 1000, btop;
void Build() {
btop = 0;
for(int L = 1; L <= n; L += T) {
for(int R = L - 1 + T;; R += T) {
if(R > n)
R = n;
//printf("[%d,%d]\n", L, R);
block[++btop].Build(L, R);
if(R == n)
break;
}
}
}
int X;
void Query(int L, int R) {
int bL = ((L + T - 1) / T * T) + 1;
int bR = R / T * T;
int id = -1;
if(bR < bL) {
id = 0;
int curcnt = 0, curcntid = 1e9;
for(int i = L; i <= R; ++i) {
block[id].cnt[a[i]]++;
if(block[id].cnt[a[i]] > curcnt || block[id].cnt[a[i]] == curcnt && a[i] <= curcntid) {
curcnt = block[id].cnt[a[i]];
curcntid = a[i];
}
}
for(int i = L; i <= R; ++i)
block[id].cnt[a[i]]--;
X = rnk[curcntid];
printf("%d\n", X);
} else {
//printf("bL=%d bR=%d\n", bL, bR);
for(int i = 1; i <= btop; ++i) {
if(block[i].L == bL && block[i].R == bR) {
id = i;
break;
}
}
int curcnt = block[id].maxcnt, curcntid = block[id].maxcntid;
for(int i = L; i < bL; ++i) {
block[id].cnt[a[i]]++;
if(block[id].cnt[a[i]] > curcnt || block[id].cnt[a[i]] == curcnt && a[i] <= curcntid) {
curcnt = block[id].cnt[a[i]];
curcntid = a[i];
}
}
for(int i = bR + 1; i <= R; ++i) {
block[id].cnt[a[i]]++;
if(block[id].cnt[a[i]] > curcnt || block[id].cnt[a[i]] == curcnt && a[i] <= curcntid) {
curcnt = block[id].cnt[a[i]];
curcntid = a[i];
}
}
for(int i = L; i < bL; ++i)
block[id].cnt[a[i]]--;
for(int i = bR + 1; i <= R; ++i)
block[id].cnt[a[i]]--;
X = rnk[curcntid];
printf("%d\n", X);
}
}
int main() {
#ifdef Yinku
freopen("Yinku.in", "r", stdin);
#endif // Yinku
X = 0;
int m;
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
rnk[i] = a[i];
}
sort(rnk + 1, rnk + 1 + n);
ele = unique(rnk + 1, rnk + 1 + n) - (rnk + 1);
for(int i = 1; i <= n; ++i)
a[i] = lower_bound(rnk + 1, rnk + 1 + ele, a[i]) - rnk;
Build();
while(m--) {
int L, R;
scanf("%d%d", &L, &R);
L = (L + X - 1) % n + 1;
R = (R + X - 1) % n + 1;
if(L > R)
swap(L, R);
Query(L, R);
}
return 0;
}