FHQ-Treap 20pts 求助

#include "bits/stdc++.h"
using namespace std;

#define int long long 
const int N = 500005, de = -1e18, inf = 1e18;

mt19937 rnd(time(0));

struct Node 
{
    int l, r;
    int val, key;
    int siz;

    int m, lm, rm, sum;
    int flip, set;

    void init(int _val)
    {
        flip = 0, set = de;
        val = _val, siz = 1;
        m = sum = _val, lm = rm = max(0ll, _val);
        l = r = 0;
        key = rnd(); 
    }

    void init0()
    {
        l = r = val = key = siz = m = lm = rm = sum = flip = 0;
        set = de;
    }
} tr[N];
int stk[N], top, root;

int n, m;

// memory management
void init(int n)
{
    top = -1;
    for (int i = 1; i <= n; ++i)
        stk[++ top] = i;
}

int create(int val)
{
    int cur = stk[top --];
    tr[cur].init(val);
    return cur;
}

void del(const int &u)
{
    if (!u) return ;
    del(tr[u].l), del(tr[u].r);
    stk[++ top] = u;
}

// over-written func
void pushup(int u)
{
    if (!u) return ;

    tr[u].siz = tr[tr[u].l].siz + tr[tr[u].r].siz + 1;
    tr[u].sum = tr[tr[u].l].sum + tr[tr[u].r].sum + tr[u].val;
    tr[u].lm = max({tr[tr[u].l].sum + tr[u].val + tr[tr[u].r].lm, tr[tr[u].l].lm});
    tr[u].rm = max({tr[tr[u].l].rm + tr[u].val + tr[tr[u].r].sum, tr[tr[u].r].rm});
    tr[u].m = max({tr[tr[u].l].m, tr[tr[u].r].m, tr[u].val, tr[tr[u].l].rm + tr[tr[u].r].lm + tr[u].val, tr[u].val});
}

void modify(int u, int k)
{
    if (!u) return ;
    
    tr[u].val = tr[u].set = k;
    tr[u].sum = tr[u].siz * k;
    tr[u].m = max(k, tr[u].sum);
    tr[u].lm = tr[u].rm = max(0ll, tr[u].sum);
    tr[u].flip = 0;
}

void flip(int u)
{
    if (!u) return ;

    swap(tr[u].l, tr[u].r);
    swap(tr[u].lm, tr[u].rm);

    tr[u].flip ^= 1;
}

void pushdown(int u)
{
    if (!u) return ;
    
    if (tr[u].set != de) 
    {
        modify(tr[u].l, tr[u].set), modify(tr[u].r, tr[u].set);
        tr[u].set = de;
    }
    else if (tr[u].flip)
    {
        flip(tr[u].l), flip(tr[u].r);
        tr[u].flip = 0;
    }
}

// fhq
void split(int u, int k, int &x, int &y)
{
    if (!u) return x = y = 0, void();   
    pushdown(u);
    if (tr[tr[u].l].siz + 1 <= k)
    {
        x = u;
        split(tr[u].r, k - tr[tr[u].l].siz - 1, tr[x].r, y);
        pushup(x);
    }
    else 
    {
        y = u;
        split(tr[u].l, k, x, tr[y].l);
        pushup(y);
    }
}

int merge(int x, int y)
{
    if (!x || !y) return x + y;
    if (tr[x].key > tr[y].key) 
    {
        pushdown(x);
        tr[x].r = merge(tr[x].r, y);
        pushup(x);
        return x;
    }
    else 
    {
        pushdown(y);
        tr[y].l = merge(x, tr[y].l);
        pushup(y);
        return y;
    }
}

// template<class ..._T>
// int merge(int x, int y, _T ...args)
// {
//     return merge(x, merge(y, args));
// }

// test
void disp(int u, bool endl = 1)
{
    if (!u) return ;
    pushdown(u);
    disp(tr[u].l, 0);
    cerr << tr[u].val << ' ';
    disp(tr[u].r, 0);
    if (endl) cerr << '\n';
}

int32_t main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    tr[0].init0();
    tr[0].m = -inf;
    cin >> n >> m;
    init(500003ll); // init the memory pool

    // create 
    for (int i = 1, a; i <= n; ++ i)
    {
        cin >> a;
        root = merge(root, create(a));
        // disp(root);
    }

    while (m --)
    {
        string c; 
        cin >> c;

        if (c == "INSERT") // insert
        {
            int pos, num, t, r = 0;
            cin >> pos >> num;
            while (num --)
            {
                cin >> t;
                r = merge(r, create(t));
            }

            // if (!pos) root = merge(r, root);
            // else 
            // {
                int x, y;
                split(root, pos, x, y);
                root = merge(x, merge(r, y));
            // }
        }
        else if (c == "DELETE") // delete
        {
            int pos, cnt;
            cin >> pos >> cnt;

            int x, y, z;
            split(root, pos - 1, x, y);
            split(y, cnt, y, z);

            del(y);

            root = merge(x, z);
        }
        else if (c == "MAKE-SAME") // make-same
        {
            int pos, cnt, k;
            cin >> pos >> cnt >> k;

            int x, y, z;
            split(root, pos - 1, x, y);
            split(y, cnt, y, z);

            modify(y, k);

            root = merge(merge(x, y), z);
        }
        else if (c == "REVERSE") // reverse
        {
            int pos, cnt;
            cin >> pos >> cnt;

            int x, y, z;
            split(root, pos - 1, x, y);
            split(y, cnt, y, z);

            flip(y);

            root = merge(merge(x, y), z);
        }
        else if (c == "GET-SUM") // get-sum
        {
            int pos, cnt;
            cin >> pos >> cnt;

            int x, y, z;
            split(root, pos - 1, x, y);
            split(y, cnt, y, z);

            cout << tr[y].sum << '\n';

            root = merge(merge(x, y), z);
        }
        else // max-sum
            cout << tr[root].m << '\n';

        // disp(root);
    }

    return 0;
}