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\) 同阶)
[code]#include #define for_(i,a,b) for (int i = (a); i < (b); i++)#define rep_(i,a,b) for (int i = (a); i > n >> m; // while (t * t * t < n) t++; t--; // t = n / t; //the lenth of a bar // rep_(i, 1, n) { cin >> a; b = a; } sort(b + 1, b + 1 + n); int len = unique(b + 1, b + 1 + n) - b - 1; rep_(i, 1, n) { a = lower_bound(b + 1, b + 1 + len, a) - b; } // for (int i = 1; i 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 |
