蒲公英（分块）
Acwing249蒲公英[洛谷](蒲公英 - 洛谷)
(249. 蒲公英 - AcWing题库)
前言
“好诗意的题目啊......
那就用很诗意的代码写吧”
思路
首先， 这题是给你 \(l, r\) 的限制目的是强制在线，所以莫队啥的不能用。
由于不满足“区间可加性”（已知\( \cup\) 的众数，不能得出 \(\) 的众数）， 所以树状数组/线段树就很难维护。
考虑分块，首先离散。 设块的长度为 \(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 #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; ia) mx = N], _S = a; } // Mid if (id + 1 < id && N + 1, id - 1)]] == 0) { int _O = s + 1, id - 1)]; int Tmp = v + 1, id - 1)]; if (mx < Tmp || mx == Tmp && _S > _O) { mx = Tmp; _S = _O; } } } _X = b; cout
页:
[1]