Problem A. Monsters (easy version)

易知，最后一定是消成 [1,2,…,b] 这样的情况，然后一次连锁操作全部删除（好像炉石里有张类似的卡）。
对于只需要处理一次询问的情况，我们可以直接对 a 数组进行排序，然后贪心得到最后的 b 即可。

const int N = int(2e5) + 9;
int a[N];
int n;

int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif

	Rush {
        RD(n); REP(i, n) RD(a[i]);
        LL s = 0, b = 0; sort(a, a+n);
        REP(i, n) if (a[i] > b) s += a[i] - ++b;
        cout << s << endl;
	}
}

Problem B. Letter Exchange

分情况讨论，贪心一下即可（证明感觉可以类比排列的循环分解）。

Problem C. Monsters (hard version)

第一想法，虽然现在无法排序了，但是总能用平衡树去维护的，又因为 a 的值域很小，因此用线段树或者树状数组一定会是更好的选择，具体需要维护什么，需要进一步分析。

每次加入一个新的数，我们依然需要分情况讨论，第一种是 a[i] > b 的情况，那么依然可以 ++b。
第二种 a[i] <= b 的情况，这种情况看起来比较复杂，我们需要找一个数进行替换，并重新调整当前的答案。
but wait… a[i] <= b 的情况，b 就一定不会增加了吗？

答案是否定的，比如我们看 1,1 和 2,1 … 在第二轮，虽然 1 都满足 a[i] <= b，但是前者 b 不会被更新，而后者 b 依然要更新。
因此我们发现这里用 a[i] > b 当做判定条件并不是最合适的。

事实上我们有更强的条件，每一轮次我们线段树的内部都是在和 [1,2,…,b] 这个序列进行比较，并且时刻要保证它的每个前缀不能比较的时候使用了更多的数，
所以我们可以将线段树初始化为 [-1, -1, -1, …, -1]，然后保证任意时刻前缀和 <= 0 即可，也就是支持：

1. 单点修改。
2. 查询前缀和最早 > 0 的位置。

这个查询出的位置，就是上面所说的被替换出的数，我们用它调整答案即可。
（这个操作似乎也是可以树状数组的，我不会 >_<。）

这个做法和前几天 Universal Cup 的 E 题很像。

const int N = int(2e5) + 9;
int a[N];
int n;
 
int ss[4*N], mx[4*N];
 
#define lx (x<<1)
#define rx (lx|1)
#define ml ((l+r)>>1)
#define mr (ml+1)
#define lc lx,l,ml
#define rc rx,mr,r
#define rt 1,1,n
 
void upd(int x) {
    ss[x] = ss[lx] + ss[rx];
    mx[x] = max(mx[lx], ss[lx] + mx[rx]);
}
 
void Build(int x, int l, int r) {
    ss[x] = mx[x] = -1;
    if (l < r) {
        Build(lc); Build(rc);
        upd(x);
    }
}
 
int Query(int x, int l, int r, int k) {
    if (l == r) return l;
    return mx[lx] > k ? Query(lc, k) : Query(rc, k-ss[lx]);
}
 
void Add(int x, int l, int r, int a, int d) {
    if (l == r) {
        ss[x] += d; mx[x] += d;
    } else {
        if (a < mr) Add(lc, a, d);
        else Add(rc, a, d);
        upd(x);
    }
}
 
int main(){
 
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
 
	Rush {
        RD(n); Build(rt); LL s = 0; int b = 0;
        REP(i, n) {
            int a; s += RD(a); Add(rt, a, 1);
            if (mx[1] <= 0) {
                s -= ++b;
            } else {
                int x = Query(rt, 0);
                Add(rt, x, -1);
                s -= x;
            }
            printf("%lld ", s);
        }
        puts("");
	}
}
 
// 单点修改
// 查询前缀和最早 > 0 的位置

Posted by xiaodao
Category: 日常