题目大意：有$n(n\leqslant4\times10^4)$个数，$m(m\leqslant5\times10^4)$个询问，每次问区间$[l,r]$内的众数，若相同输出最小的，强制在线。
题解：先离散化，分块，设块大小为$S$，可以在$O(\dfrac n S n)$的复杂度内预处理出每两个块间的众数。考虑询问，发现询问中的众数要么是整块的那一个众数，要么就是非整块内出现过的数，可以用主席树查询区间数出现个数，比较一下即可，一次查询复杂度$O(2S\log_2 n)$。$S$开的比$\sqrt n$小一点就行了
卡点：主席树查询时左端点没有减一，数组开小
C++ Code：
#include#include #include #include namespace __IO { namespace R { int x, ch; inline int read() { while (isspace(ch = getchar())); for (x = ch & 15; isdigit(ch = getchar());) x = x * 10 + (ch & 15); return x; } }}using __IO::R::read;#define maxn 40010const int BSZ = 100, Bnum = maxn / BSZ + 5;namespace SgT {#define N (maxn * 20) int lc[N], rc[N], V[N], idx; void insert(int &rt, const int l, const int r, const int num) { lc[++idx] = lc[rt], rc[idx] = rc[rt], V[idx] = V[rt] + 1, rt = idx; if (l == r) return ; const int mid = l + r >> 1; if (num <= mid) insert(lc[rt], l, mid, num); else insert(rc[rt], mid + 1, r, num); } int query(const int L, const int R, const int l, const int r, const int num) { if (l == r) return V[R] - V[L]; const int mid = l + r >> 1; if (num <= mid) return query(lc[L], lc[R], l, mid, num); else return query(rc[L], rc[R], mid + 1, r, num); }#undef N}int n, m, ans, anscnt;int rt[maxn];int v[maxn], s[maxn], bl[maxn];int L[Bnum], R[Bnum], cnt[maxn];int Max[Bnum][Bnum];int main() { n = read(), m = read(); for (int i = 1; i <= n; i++) { v[i] = s[i] = read(); bl[i] = i / BSZ + 1; } int tot = (std::sort(v + 1, v + n + 1), std::unique(v + 1, v + n + 1) - v - 1); for (int i = 1; i <= n; i++) { SgT::insert(rt[i] = rt[i - 1], 1, tot, s[i] = std::lower_bound(v + 1, v + tot + 1, s[i]) - v); } const int B = bl[n]; for (int i = 1; i <= B; i++) L[i] = (i - 1) * BSZ, R[i] = L[i] + BSZ - 1; L[1] = 1, R[B] = n; for (int l = 1, r, M; l <= B; l++) { r = l, M = 0; memset(cnt, 0, sizeof cnt); for (int i = L[l]; i <= n; i++) { cnt[s[i]]++; if (cnt[s[i]] > cnt[M] || (cnt[s[i]] == cnt[M] && s[i] < M)) M = s[i]; if (i == R[r]) Max[l][r] = M, r++; } } while (m --> 0) { int l = (read() + ans - 1) % n + 1, r = (read() + ans - 1) % n + 1; if (l > r) std::swap(l, r); const int lb = bl[l], rb = bl[r]; ans = anscnt = 0;#define check(x) {\ const int tmp = SgT::query(rt[l - 1], rt[r], 1, tot, x); \ if (tmp > anscnt || (tmp == anscnt && x < ans)) ans = x, anscnt = tmp;\} if (lb == rb) { for (register int i = l; i <= r; i++) check(s[i]); } else { for (register int i = l; i <= R[lb]; i++) check(s[i]); if (lb + 1 <= rb - 1) check(Max[lb + 1][rb - 1]); for (register int i = L[rb]; i <= r; i++) check(s[i]); }#undef check printf("%d\n", ans = v[ans]); } return 0;}