题解：P11455 [USACO24DEC] Cowdepenence G

· · 题解

对于固定 x，和一个有 c 个的标号，有一个 O(c) 的贪心，考虑从左往右扫，每次一段尽量长，这样答案是 O(\dfrac n x) 的，正确性显然。看到这个答案大小，再观察一手样例发现答案单调递减（由于贪心策略显然），就可以想到枚举标号之后根号分治。

当 x \le B 时，直接暴力，复杂度 O(B\sum c) = O(nB)。

当 x > B 时，答案只有 \dfrac n B 种，二分变化点，时间复杂度 O(\dfrac n B \log n \sum c) = O(\dfrac n B n \log n)。

由均值取等，B 取 \sqrt{n \log n}。

const int N = 1e5 + 5;
int n, B, a[N], ds[N]; vector <int> p[N];
void update(int l, int r, int k) { ds[l] += k; ds[r + 1] -= k; }
int calc(int c, int x) {
    int lst = -1e9, ans = 0;
    for (int t : p[c]) if (t - lst > x) ans++, lst = t;
    return ans;
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n; B = sqrt(n * __lg(n));
    for (int i = 1; i <= n; i++) cin >> a[i], p[a[i]].push_back(i);
    for (int i = 1; i <= n; i++) if (p[i].size()) {
        for (int x = 1; x <= B; x++) update(x, x, calc(i, x));
        for (int x = B + 1; x <= n; ) {
            int l = x, r = n, ans = l, t = calc(i, x);
            while (l <= r) {
                int mid = (l + r) >> 1;
                if (calc(i, mid) == t) l = mid + 1, ans = mid;
                else r = mid - 1;
            }
            update(x, ans, t); x = ans + 1;
        }
    }
    for (int i =  1; i <= n; i++) cout << (ds[i] += ds[i - 1]) << '\n';
    return 0;
}