CF 786C Till I Collapse

题目描述

https://codeforces.com/problemset/problem/786/C

简要题意：给定一个长度为 $n$ 的序列 $a_i$，现在需要对于所有 $k\in[1,n]$，最少能将 $a_i$ 分成多少个连续段满足每个连续段内的不同数字的种数不超过 $k$

$n\le 10^5$

Solution

注意到总答案小于 $O(n\log n)$

所以我们考虑对于每一段的左端点暴力去找右端点，这一步我们用主席树可以做到单次 $O(\log n)$

所以总的时间复杂度为 $O(n\log^2 n)$

#include <iostream>
#include <cstdio>
#define maxn 100010
using namespace std;

int n, a[maxn];

int vis[maxn];

#define lc T[i].ch[0]
#define rc T[i].ch[1]
#define Lc T[j].ch[0]
#define Rc T[j].ch[1]
struct zhuxi {
    int v, ch[2]; 
} T[maxn * 40]; int top, rt[maxn];
void update(int &i, int j, int l, int r, int k, int v) {
    i = ++top; T[i] = T[j]; T[i].v += v; 
    if (l == r) return ; int m = l + r >> 1;
    if (k <= m) update(lc, Lc, l, m, k, v);
    else update(rc, Rc, m + 1, r, k, v); 
}

int query(int i, int l, int r, int k) {
    if (l == r) return k >= T[i].v ? l : 0;
    int m = l + r >> 1;
    if (k < T[lc].v) return query(lc, l, m, k);
    else if (k > T[lc].v) return query(rc, m + 1, r, k - T[lc].v);
    else return max(m, query(rc, m + 1, r, 0)); 
} 

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n; 
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = n; i; --i) {
        rt[i] = rt[i + 1]; 
        if (vis[a[i]]) update(rt[i], rt[i], 1, n, vis[a[i]], -1);
        vis[a[i]] = i; 
        update(rt[i], rt[i], 1, n, vis[a[i]], 1); 
    } 
    for (int k = 1; k <= n; ++k) {
        int p = 1, ans = 0;  
        while (p <= n) {
            p = query(rt[p], 1, n, k) + 1;
            ++ans;
        }
        cout << ans << " ";
    } 
    return 0;
}