原题解：
可以发现，在给定的规则下，若前$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; }
原文：https://www.cnblogs.com/Hansue/p/13067873.html
