自动搬运

查看原文

来自洛谷，原作者为

	VitrelosTia What you want, What you do ?

搬运于2025-08-24 23:07:28，当前版本为作者最后更新于2025-01-16 15:40:40，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

对于固定 $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;
}