BJOI2017 喷式水战改

#include <cstdio>
#include <cstring>

#include <algorithm>

#define LOG(FMT...) // fprintf(stderr, FMT)

using namespace std;

typedef long long ll;

struct data {
    ll dp[4][4];

    data()
    { memset(dp, 0, sizeof(dp)); }

    data(const data& x)
    { memcpy(dp, x.dp, sizeof(dp)); }

    data(int a, int b, int c, int x);

    data operator+(const data& x) const;
};

struct node {
    ll a, b, c, sz, cnt;
    int rnd;
    data d, sum;
    node *ls, *rs;
};

const int N = 100010;

int n;
node* root;

int fast_rand();
ll get_cnt(node* p);
node* create(int a, int b, int c, int x);
void update(node* p);
void insert(node*& p, node* q, ll x);
void zig(node*& p);
void zag(node*& p);
void order(node* p);

int main() {
    int a, b, c, x;
    ll p;
    ll lste = 0, cure;
    scanf("%d", &n);
    while (n--) {
        scanf("%lld%d%d%d%d", &p, &a, &b, &c, &x);
        insert(root, create(a, b, c, x), p);
        cure = root->sum.dp[0][3];
        printf("%lld\n", cure - lste);
        lste = cure;
        LOG("\n");
    }
    return 0;
}

void order(node* p) {
    if (!p)
        return;
    order(p->ls);
    LOG(" %d", p->sz);
    order(p->rs);
}

inline int fast_rand() {
    static int x = 19260817, y = x << 4, z = x >> 2, t;
    t = x ^ y ^ z;
    x ^= y << 2;
    x ^= z >> 4;
    z = y;
    y = x;
    x = t;
    return t;
}

inline ll get_cnt(node* p)
{ return p ? p->cnt : 0; }

inline void update(node* p) {
    p->cnt = p->sz + get_cnt(p->ls) + get_cnt(p->rs);
    p->sum = p->d;
    if (p->ls)
        p->sum = p->ls->sum + p->sum;
    if (p->rs)
        p->sum = p->sum + p->rs->sum;
}

inline node* create(int a, int b, int c, int x) {
    static node pool[N << 1];
    static node* p = pool;
    ++p;
    p->d = data(a, b, c, x);
    p->a = a;
    p->b = b;
    p->c = c;
    p->sz = x;
    p->sum = p->d;
    p->rnd = fast_rand();
    p->cnt = x;
    return p;
}

inline void zig(node*& p) {
    node* son = p->ls;
    p->ls = son->rs;
    son->rs = p;
    update(p);
    p = son;
    update(p);
}

inline void zag(node*& p) {
    node* son = p->rs;
    p->rs = son->ls;
    son->ls = p;
    update(p);
    p = son;
    update(p);
}

void insert(node*& p, node* q, ll x) {
    if (!p) {
        LOG("%d\n", x);
        p = q;
        return;
    }
    if (x <= get_cnt(p->ls)) {
        insert(p->ls, q, x);
        update(p);
        if (p->rnd > p->ls->rnd)
            zig(p);
        return;
    }
    x -= get_cnt(p->ls);
    if (x >= p->sz) {
        insert(p->rs, q, x - p->sz);
        update(p);
        if (p->rnd > p->rs->rnd)
            zag(p);
        return;
    }
    p->d = data(p->a, p->b, p->c, p->sz - x);
    node* r = create(p->a, p->b, p->c, x);
    p->sz -= x;
    r->ls = p->ls;
    p->ls = r;
    r->rs = q;
    update(r);
    update(p);
}

data::data(int a, int b, int c, int x) {
    dp[0][0] = dp[3][3] = (ll)a * x;
    dp[1][1] = (ll)b * x;
    dp[2][2] = (ll)c * x;
    for (int i = 0; i < 4; ++i)
        for (int j = i + 1; j < 4; ++j)
            dp[i][j] = max(dp[i][j - 1], dp[j][j]);
}

data data::operator+(const data& x) const {
    data ret;
    for (int i = 0; i < 4; ++i)
        for (int j = i; j < 4; ++j)
            for (int k = i; k <= j; ++k)
                ret.dp[i][j] = max(ret.dp[i][j], dp[i][k] + x.dp[k][j]);
    return ret;
}