• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

Till I Collapse CodeForces – 786C

开发技术 开发技术 3小时前 1次浏览

题面

点过去看

题解

首相想当(k)固定怎么算, 很简单想出数据结构维护(nlogn)的做法,

关键当(k)(1)(n),怎么办

在仔细看看(k)固定时的复杂度,应该是(ans times logn),其中ans为答案

那从(1)(n)(sum ans)最坏情况是(nlogn)

所以当(k)(1)(n) 的复杂度不是(n^2logn) 而是 (nlog^2n)

int n, c[N];
 
void add(int x, int val) {for (; x <= n; x += -x & x) c[x] += val; }
 
int ask(int w) { 
    int p = 0;
    for (int i = 16; ~i; --i)
        if (p + (1 << i) <= n && c[p + (1 << i)] <= w) {
            p |= 1 << i;
            w -= c[p];
        }
    return p + 1;
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n;
    vector<int> nxt(n + 1, n + 1), ls(n + 1), ans(n + 1);
    vector<stack<int>> need(n + 1);
    for (int i = 1; i <= n; ++i) {
        int x; cin >> x;
        if (ls[x]) nxt[ls[x]] = i;
        else add(i, 1);
        ls[x] = i;
        need[1].emplace(i);
    }
 
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; !need[i].empty(); ++j) {
            int cur = ask(need[i].top());
            ++ans[need[i].top()];
            if (cur < n + 1)
                need[cur].emplace(need[i].top());
            need[i].pop();
        }
        add(i, -1);
        add(nxt[i], 1);
    }
    for (int i = 1; i <= n; ++i) cout << ans[i] << ' ';
    return 0;
}

程序员灯塔
转载请注明原文链接:Till I Collapse CodeForces – 786C
喜欢 (0)