【2020NOI.AC省选模拟#8】C. 海盗

题目链接

原题解：

可以发现，在给定的规则下，若前$i$个人参与分配，则每个人得到的金币个数是固定的。

假设在前$i-1$个海盗参与分配时，某个海盗能得到$x$个金币，则第$i$个海盗需要给他$x+1$个金币才能得到支持。

如果某个海盗在前$i-1$个海盗分配时会被扔到海里，那么他一定会支持第$i$个海盗。

可以发现，如果我们用收益$-1$来表示被扔到海里，$i$号海盗需要给某个在$i-1$给个海盗分配时收益为$x$的海盗$x+1$个金币才能得到支持。

为了获得尽量多的金币，海盗一定会获取收益尽量低的$V_i-1$个海盗的收益，然后把其他金币全都分配给自己。

我们可以用平衡树维护这个过程，需要支持区间赋值，区间加，分裂，合并。

如果总的金币数足够获得$V_i-1$个其他海盗的支持，那这$V_i-1$个海盗的收益会增加$1$，$i$号海盗 的收益为剩下的金币数，其他海盗的金币数变成了$0$。

否则，$i$号海盗的收益是$-1$，其他海盗的收益不变。

补充：

如果连续有几个海盗被扔进海里，他们的收益会都保持为$-1$，直到出现一个没被扔进海里的海盗。

代码（100分）：

#include <bits/stdc++.h>

template <class T>

inline void read(T &res)

{

    res = 0; bool bo = 0; char c;

    while (((c = getchar()) < '0' || c > '9') && c != '-');

    if (c == '-') bo = 1; else res = c - 48;

    while ((c = getchar()) >= '0' && c <= '9')

        res = (res << 3) + (res << 1) + (c - 48);

    if (bo) res = ~res + 1;

}

typedef long long ll;

const int N = 2e6 + 5;

int n, delta, sze[N], fa[N], lc[N], rc[N], cnt[N], Root, ToT;

ll K, val[N], sum[N];

bool which(int x) {return rc[fa[x]] == x;}

void upt(int x)

{

    sze[x] = sze[lc[x]] + sze[rc[x]] + cnt[x];

    sum[x] = sum[lc[x]] + sum[rc[x]] + val[x] * cnt[x];

}

void rotate(int x)

{

    int y = fa[x], z = fa[y], b = lc[y] == x ? rc[x] : lc[x];

    if (z) (lc[z] == y ? lc[z] : rc[z]) = x;

    fa[x] = z; fa[y] = x; if (b) fa[b] = y;

    if (lc[y] == x) rc[x] = y, lc[y] = b;

    else lc[x] = y, rc[y] = b; upt(y);

}

void splay(int x, int tar)

{

    while (fa[x] != tar)

    {

        if (fa[fa[x]] != tar)

        {

            if (which(x) == which(fa[x])) rotate(fa[x]);

            else rotate(x);

        }

        rotate(x);

    }

    upt(x); if (!tar) Root = x;

}

int ins(int &x, int np, ll num, int c, int ft)

{

    if (!x) return x = np, fa[x] = ft, x = np, sze[x] = cnt[x] = c,

        val[x] = num, sum[x] = num * c, lc[x] = rc[x] = 0, x;

    if (val[x] == num) return sze[x] += c, cnt[x] += c, sum[x] += num * c, x;

    sze[x] += c; sum[x] += num * c;

    if (num < val[x]) ins(lc[x], np, num, c, x);

    else ins(rc[x], np, num, c, x);

}

int kth(int x, int k)

{

    while (x)

    {

        int lw = sze[lc[x]], mw = cnt[x];

        if (lw < k && k <= lw + mw) return x;

        if (k <= lw) x = lc[x];

        else x = rc[x], k -= lw + mw;

    }

    return 0;

}

int main()

{

    //freopen("c.in", "r", stdin);

    //freopen("c.out", "w", stdout);

    int cur = 0, V;

    read(n); read(K);

    for (int i = 1; i <= n; i++)

    {

        read(V);

        if (cur + 1 >= V)

        {

            if (i == 1) Root = ToT = 1, delta = fa[1] = lc[1] = rc[1] = 0,

                sze[1] = cnt[1] = 1, val[1] = sum[1] = K;

            else Root = 1, delta = fa[1] = lc[1] = lc[2] = rc[2] = 0,

                sze[1] = i, cnt[1] = i - 1, val[1] = 0, sum[1] = sum[2] = val[2] = K,

                    fa[2] = cnt[2] = sze[2] = 1, rc[1] = ToT = 2;

            printf("%lld\n", K); cur = 0; continue;

        }

        int k = V - cur - 1; splay(kth(Root, k), 0);

        ll s = 1ll * (delta + 1) * k + sum[lc[Root]] + val[Root] * (k - sze[lc[Root]]);

        if (s > K) {puts("-1"); cur++; continue;}

        printf("%lld\n", K - s); cur = 0;

        delta++; rc[Root] = 0; cnt[Root] = k - sze[lc[Root]]; upt(Root);

        if (i - k - 1) splay(ins(Root, ++ToT, -delta, i - k - 1, 0), 0);

        splay(ins(Root, ++ToT, K - s - delta, 1, 0), 0);

    }

    return 0;

}

【2020NOI.AC省选模拟#8】C. 海盗的相关教程结束。