Acwing249蒲公英

[洛谷]([Violet]蒲公英 - 洛谷)

[Acwing(数据较强)](249. 蒲公英 - AcWing题库)

前言

“好诗意的题目啊......

那就用很诗意的代码写吧”

思路

首先， 这题是给你 \(l, r\) 的限制目的是强制在线，所以莫队啥的不能用。

由于不满足“区间可加性”（已知\([l, r] \cup[r+1,k]\) 的众数，不能得出 \([l, k]\) 的众数）， 所以树状数组/线段树就很难维护。

考虑分块，首先离散。 设块的长度为 \(T\) , 则有 \(n / T\) 块， 然后预处理第 \(i\) 到 \(j\) 块的众数以及数的出现次数， 这段时间复杂度 \(O(NT^2)\)。 之后两段暴力维护, \(O(N/T)\)

总的时间复杂度 \(O(NT^2 + MN/T)\)

所以如果 \(T=\sqrt{N}\) 时间复杂度就为 \(O(N\sqrt{N})\) ( \(N,M\) 同阶)

#include <bits/stdc++.h>
#define for_(i,a,b) for (int i = (a); i < (b); i++)
#define rep_(i,a,b) for (int i = (a); i <= (b); i++)
#define _Pos(i, j) (((i)-1)*cnt+(j))
using namespace std;
const int maxn = 4e5 + 10, mod = 1e9 + 7;// mod = 1949777;
const double EPS = 1e-3;
int n, m, t, cnt;
int a[maxn], id[maxn], l[maxn], r[maxn], b[maxn], s[maxn];
void solve() {
}
signed main() {
#ifdef LOCAL
 freopen("w.in", "r", stdin);
 freopen("w.ans", "w", stdout);
#endif
 ios::sync_with_stdio(false);
 cin.tie(nullptr);
 cin >> n >> m;
 //
 while (t * t * t < n)
 t++;
 t--; //
 t = n / t; //the lenth of a bar
 //
 rep_(i, 1, n) {
 cin >> a[i];
 b[i] = a[i];
 }
 sort(b + 1, b + 1 + n);
 int len = unique(b + 1, b + 1 + n) - b - 1;
 rep_(i, 1, n) {
 a[i] = lower_bound(b + 1, b + 1 + len, a[i]) - b;
 }
 //
 for (int i = 1; i <= n / t; i++) {
 l[i] = (i - 1) * t + 1;
 r[i] = i * t;
 }
 cnt = n / t;
 if (r[cnt] < n) {
 l[cnt + 1] = r[cnt] + 1;
 r[cnt + 1] = n;
 cnt++;
 }
 for (int i = 1; i <= cnt; i++) {
 for (int j = l[i]; j <= r[i]; j++) {
 id[j] = i;
 }
 }
 vector<vector<int>> v(cnt * cnt + 1, vector<int>(n, 0));
 //
 for (int i = 1; i <= cnt; i++) {
 for (int j = i; j <= cnt; j++) {
 for (int k = l[i]; k <= r[j]; k++) {
 v[_Pos(i, j)][a[k]]++;
 }
 int mx = 0, _S = 0;
 for (int k = 1; k <= n; k++) {
 if (mx < v[_Pos(i, j)][k] || mx == v[_Pos(i, j)][k] && _S > k) {
 mx = v[_Pos(i, j)][k];
 _S = k;
 }
 }
 s[_Pos(i, j)] = _S;
 }
 }
 //
 vector<int> N(n + 1, 0);
 int _X = 0;
 for (int i = 1, L, R; i <= m; i++) {
 cin >> L >> R;
 L = (L + _X - 1) % n + 1, R = (R + _X - 1) % n + 1;
 if (L > R)
 swap(L, R);
 int mx = 0, _S = 0;
 if (id[L] == id[R]) {
 for (int j = L; j <= R; j++) {
 N[a[j]]++;
 if (mx < N[a[j]] || mx == N[a[j]] && _S > a[j])
 mx = N[a[j]], _S = a[j];
 }
 } else {
 // Left
 for (int j = L; id[j] == id[L]; j++) {
 N[a[j]]++;
 if (N[a[j]] == 1) {
 if (id[L] + 1 < id[R]) {
 N[a[j]] += v[_Pos(id[L] + 1, id[R] - 1)][a[j]];
 }
 }
 if (mx < N[a[j]] || mx == N[a[j]] && _S > a[j])
 mx = N[a[j]], _S = a[j];
 }
 // Right
 for (int j = R; id[j] == id[R]; j--) {
 N[a[j]]++;
 if (N[a[j]] == 1) {
 if (id[L] + 1 < id[R]) {
 N[a[j]] += v[_Pos(id[L] + 1, id[R] - 1)][a[j]];
 }
 }
 if (mx < N[a[j]] || mx == N[a[j]] && _S > a[j])
 mx = N[a[j]], _S = a[j];
 }
 // Mid
 if (id[L] + 1 < id[R] && N[s[_Pos(id[L] + 1, id[R] - 1)]] == 0) {
 int _O = s[_Pos(id[L] + 1, id[R] - 1)];
 int Tmp = v[_Pos(id[L] + 1, id[R] - 1)][_O];
 if (mx < Tmp || mx == Tmp && _S > _O) {
 mx = Tmp;
 _S = _O;
 }
 }
 }
 _X = b[_S];
 cout << _X << endl;
 // clear
 for (int j = L; id[j] == id[L]; j++)
 N[a[j]] = 0;
 for (int j = R; id[j] == id[R]; j--)
 N[a[j]] = 0;
 }
 return 0;
}