写一篇博客纪念一下第一道AC的黑题~
题目链接
题目分析
神仙分块……做完之后感觉分块比我理解的要深刻很多啊
思路参考洛咕第一篇题解，特别巧妙
首先预处理两个数组：
\(s[i][j]\)：前缀和，前\(i\)（含第\(i\)块）个块中\(j\)的出现次数
\(p[i][j]\)：第\(i\)到\(j\)个块的最小众数
如何预处理：
这一段题解写得比较略……可能是我太弱了，码了半天才从\(O(n^2)\)压成\(O(n \sqrt n)\)的，所以讲细一点
对于\(s[i][j]\)：
第一层循环枚举\(i\)，对于每个\(i\)，先枚举\(j\)将\(i - 1\)的总数转移过来，再扫描本块内的数并累加
对于\(p[i][j]\)：
开一个辅助数组B，记录每个元素出现了多少次第一层循环枚举\(i\)，第二层循环枚举\(j\)，第三层循环枚举块\(j\)内的每一个元素并累加，每一次\(i\)更改的时候清空B
如何询问：
分两种情况：
- 若\(pos[r]-pos[l]<=1\)，则暴力统计众数并返回答案
- 若\(pos[r] - pos[l] >= 2\)，则对于零散块内的每个元素，先将大块内的出现次数用\(s\)数组前缀和\(O(1)\)处理出来，再暴力统计零散块内的出现次数并更新答案，最后再和大块内的众数（\(p\)数组记录）比较一下即可
代码
#include#define N (100000 + 5)#define int long long using namespace std;inline int read() { int cnt = 0, f = 1; char c = getchar(); while (!isdigit(c)) {if (c == '-') f = -f; c = getchar();} while (isdigit(c)) {cnt = (cnt << 3) + (cnt << 1) + c - '0'; c = getchar();} return cnt * f;}int n, a[N], b[N], q, t, tmp = 10000000, gmax, m;int L[305], R[305], pos[N], s[305][N / 2], p[305][N / 2], t0;int ans, l, r;int B[N / 2];inline void Discretize () { sort (b + 1, b + n + 1); q = unique(b + 1, b + n + 1) - b - 1; for (register int i = 1; i <= n; ++i) a[i] = lower_bound(b + 1, b + q + 1, a[i]) - b;}inline void pre_work() { t = sqrt(n) + log(n)/log(2); t0 = n / t; for (register int i = 1; i <= t; ++i) { L[i] = (i - 1) * t0 + 1; R[i] = i * t0; } if (R[t] < n) { ++t; L[t] = R[t - 1] + 1; R[t] = n; } for (register int i = 1; i <= t; ++i) for (register int j = L[i]; j <= R[i]; ++j) pos[j] = i; for (register int i = 1; i <= t; ++i) { for (register int j = 1; j <= n; ++j) s[i][j] = s[i - 1][j]; for (register int j = L[i]; j <= R[i]; ++j) s[i][a[j]]++; } for (register int i = 1; i <= t; ++i) { memset(B, 0, sizeof(B)); tmp = 10000000, gmax = 0; for (register int j = i; j <= t; ++j) { for (register int k = L[j]; k <= R[j]; ++k) { B[a[k]]++; if (B[a[k]] >= gmax) { if (B[a[k]] > gmax) tmp = a[k]; else if (tmp > a[k]) tmp = a[k]; gmax = B[a[k]]; } } p[i][j] = tmp; } }} inline int query(int l, int r) { memset(B, 0, sizeof(B)); int ans = 50000, tmp = 0; int x = pos[l], y = pos[r]; if (x == y || x + 1 == y) { for (register int i = l; i <= r; ++i) { ++B[a[i]]; if (B[a[i]] > B[ans]) ans = a[i]; else if (B[a[i]] == B[ans] && a[i] < ans) ans = a[i]; } } else { for (register int i = l; i <= R[x]; ++i) { B[a[i]] = (s[y - 1][a[i]] - s[x][a[i]]); } for (register int i = L[y]; i <= r; ++i) { B[a[i]] = (s[y - 1][a[i]] - s[x][a[i]]); } for (register int i = l; i <= R[x]; ++i) { ++B[a[i]]; if (B[a[i]] > B[ans]) ans = a[i]; else if (B[a[i]] == B[ans] && a[i] < ans) ans = a[i]; } for (register int i = L[y]; i <= r; ++i) { ++B[a[i]]; if (B[a[i]] > B[ans]) ans = a[i]; else if (B[a[i]] == B[ans] && a[i] < ans) ans = a[i]; } tmp = p[x + 1][y - 1]; if (s[y - 1][tmp] - s[x][tmp] > B[ans]) ans = tmp; else if ((s[y - 1][tmp] - s[x][tmp] == B[ans]) && tmp < ans) ans = tmp; } return b[ans];}signed main() { n = read(), m = read(); for (register int i = 1; i <= n; ++i) a[i] = b[i] = read(); Discretize(); pre_work(); ans = 0; for (register int i = 1; i <= m; ++i){ l = read(); r = read(); l = (l + ans - 1) % n + 1, r = (r + ans - 1) % n + 1; if (l > r) swap(l, r); ans = query(l, r); printf("%lld\n", ans); } return 0;}