Implicit Splay Tree

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll LINF = 1e18;

struct Data {
    ll val, sum, pref, suff, seg;
    Data() : val(0), sum(0), pref(-LINF), suff(-LINF), seg(-LINF) {}
    Data(ll v) : val(v), sum(v), pref(v), suff(v), seg(v) {}
};

Data combine(const Data& a, const Data& b) {
    Data r;
    r.sum = a.sum + b.sum;
    r.pref = max(a.pref, a.sum + b.pref);
    r.suff = max(b.suff, b.sum + a.suff);
    r.seg = max({a.seg, b.seg, a.suff + b.pref});
    return r;
}

struct ImplicitSplay {
    struct Node {
        Node *ch[2], *par;
        Data d;
        int sz;
        Node() : sz(0) { par = ch[0] = ch[1] = this; }
        Node(ll v) : d(v), sz(1) { par = ch[0] = ch[1] = EMPTY; }
        void pull() {
            sz = ch[0]->sz + ch[1]->sz + 1;
            ll v = d.val;
            d = combine(ch[0]->d, combine(Data(v), ch[1]->d));
            d.val = v;
        }
    };

    static Node* EMPTY;
    Node* root;

    ImplicitSplay() : root(EMPTY) {}

    void link(Node* p, Node* c, int dir) {
        if (p != EMPTY) { p->ch[dir] = c; p->pull(); }
        if (c != EMPTY) c->par = p;
    }

    int dir(Node* p, Node* c) { return p->ch[1] == c; }

    void rotate(Node* p, int d) {
        Node* q = p->ch[d], *g = p->par;
        link(p, q->ch[!d], d);
        link(q, p, !d);
        link(g, q, dir(g, p));
    }

    void splay(Node* q) {
        while (q->par != EMPTY) {
            Node* p = q->par, *g = p->par;
            int d1 = dir(p, q), d2 = dir(g, p);
            if (g == EMPTY) rotate(p, d1);
            else if (d1 == d2) { rotate(g, d2); rotate(p, d1); }
            else { rotate(p, d1); rotate(g, d2); }
        }
        root = q;
    }

    Node* at(Node* p, int k) {
        if (p == EMPTY || k >= p->sz) return EMPTY;
        int ls = p->ch[0]->sz;
        if (k < ls) return at(p->ch[0], k);
        if (k == ls) return p;
        return at(p->ch[1], k - ls - 1);
    }

    Node* splayIdx(Node* p, int k) {
        p = at(p, k); splay(p); return p;
    }

    void split(Node* p, int k, Node*& l, Node*& r) {
        if (k >= p->sz) { l = p; r = EMPTY; return; }
        p = splayIdx(p, k);
        l = p->ch[0]; r = p;
        link(r, EMPTY, 0);
        if (l != EMPTY) l->par = EMPTY;
    }

    Node* merge(Node* l, Node* r) {
        if (l == EMPTY) return r;
        if (r == EMPTY) return l;
        r = splayIdx(r, 0);
        link(r, l, 0);
        return r;
    }

    void insert(int idx, ll val) {
        Node *l, *r;
        split(root, idx, l, r);
        root = merge(merge(l, new Node(val)), r);
    }

    void erase(int idx) {
        Node *l, *r, *mid;
        split(root, idx + 1, l, r);
        split(l, idx, l, mid);
        delete mid;
        root = merge(l, r);
    }

    ll query(int l, int r) {
        Node *a, *b, *mid;
        split(root, r + 1, a, b);
        split(a, l, a, mid);
        ll ans = mid->d.seg;
        root = merge(merge(a, mid), b);
        return ans;
    }

    int size() { return root->sz; }
};

ImplicitSplay::Node* ImplicitSplay::EMPTY = new ImplicitSplay::Node();