题解 | #Rating#

C Rating
每次取最小的rating一定能保证上升最快，下降最慢
不过我脑子短路没想到写堆

#include <cstdio>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#define ine inline
#define MAXN maxn
using namespace std;
typedef const int coi;

ine int rd(){
    int ans = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        ans = (ans << 3) + (ans << 1) + ch - 48;
        ch = getchar();
    }

    return ans * f;
}
coi maxn = 6e5 + 3;

int n, m;

int tot, root;
int son[MAXN][2],key[MAXN],  sz[MAXN];
double v[MAXN];

int New(double val) {
    v[++tot] = val, key[tot] = rand(), sz[tot] = 1;
    return tot;
}

void update(int p) {
    sz[p] = sz[son[p][0]] + sz[son[p][1]] + 1;
}

void split(int p, double val, int &x, int &y) {  // val / left : <= val /
    if (!p) {
        x = y = 0;
        return ;
    } else if (v[p] <= val)
        x = p, split(son[p][1], val, son[p][1], y);
    else
        y = p, split(son[p][0], val, x, son[p][0]);

    update(p);
}

int merge(int x, int y) {
    if (!x || !y)
        return x + y;

    if (v[x] > v[y])
        swap(x, y);

    if (key[x] < key[y]) {
        son[x][1] = merge(son[x][1], y), update(x);
        return x;
    } else {
        son[y][0] = merge(x, son[y][0]), update(y);
        return y;
    }
}

int xx, yy, zz;
void ins(double val) {
    split(root, val, xx, yy);
    root = merge(xx, merge(yy, New(val)));
}

void del(double val) {
    split(root, val, xx, zz), split(xx, val - 1, xx, yy);
    yy = merge(son[yy][0], son[yy][1]);
    root = merge(zz, merge(xx, yy));
}

int askk(double val) {  // kth
    split(root, val - 1, xx, yy);
    int ret = sz[xx] + 1;
    root = merge(xx, yy);
    return ret;
}

double askv(int p, int kth) {  // val
    if (kth <= sz[son[p][0]])
        return askv(son[p][0], kth);
    else if (kth == sz[son[p][0]] + 1)
        return v[p];
    else
        return askv(son[p][1], kth - sz[son[p][0]] - 1);
}

int main() {
    int x;
    srand(time(NULL));
    n = rd(),m = rd();
    double sum = 0;
    for(int i = 1; i <= n; i ++){
        x = rd();
        ins(x);
        sum += x;
    }
    for(int i = 1; i <= m; i ++){
        double tt;
        cin >> tt;
        double y = askv(root,1);
        sum += (tt-y)/2;
        del(y); ins((tt+y)/2);
        cout << fixed << setprecision(2) << sum << endl;
    }

    return 0;
}