rt. #13TLE，本机跑4s多，其他点最大67ms，求卡常

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

int read()
{
    int s = 0,w = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-') w = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        s = (s << 1) + (s << 3) + (ch ^ 48);
        ch = getchar();
    }
    return s * w;
}

void write(int a)
{
    if(a < 0) putchar('-'),a = -a;
    if(a > 9) write(a / 10);
    putchar(a % 10 + '0');
}

const int N = 4e6 + 10,inf = 2147483647;

int n,m,c,x,y,z,a[N];
int pos,tot;
int stk[N >> 3],len;
string opt;

struct FHQ
{

int tot,root;
int val[N],dat[N],size[N],son[N][2];
int sum[N],maxqz[N],maxhz[N],maxzd[N],cov[N];
bool lazy[N],tag[N];

int New(int x)
{
    tot = stk[len--];
    val[tot] = sum[tot] = x;
    size[tot] = 1,dat[tot] = rand();
    son[tot][0] = son[tot][1] = lazy[tot] = tag[tot] = 0;
    maxqz[tot] = maxhz[tot] = max(x,0);
    maxzd[tot] = x;
    return tot;
}

void reverse(int p)
{
    if(p == 0) return;
    swap(son[p][0],son[p][1]);
    swap(maxhz[p],maxqz[p]);
    lazy[p] ^= 1;
    pushdown(p);
}

void cover(int p,int c)
{
    val[p] = cov[p] = c,sum[p] = size[p] * c;
    maxqz[p] = maxhz[p] = max(sum[p],0);
    maxzd[p] = max(c,sum[p]);
    tag[p] = 1;
    pushdown(p);
}

void pushup(int p)
{
    if(p == 0) return;
    size[p] = size[son[p][0]] + size[son[p][1]] + 1;
    sum[p] = sum[son[p][0]] + sum[son[p][1]] + val[p];
    maxqz[p] = max(max(maxqz[son[p][0]],maxqz[son[p][1]] + val[p] + sum[son[p][0]]),0);
    maxhz[p] = max(max(maxhz[son[p][1]],maxhz[son[p][0]] + val[p] + sum[son[p][1]]),0);
    maxzd[p] = val[p] + max(maxqz[son[p][1]] + maxhz[son[p][0]],0);
    if(son[p][0]) maxzd[p] = max(maxzd[p],maxzd[son[p][0]]);
    if(son[p][1]) maxzd[p] = max(maxzd[p],maxzd[son[p][1]]);
}

void pushdown(int p)
{
    if(p == 0) return;
    if(lazy[p])
    {
        if(son[p][0]) reverse(son[p][0]);
        if(son[p][1]) reverse(son[p][1]);
        lazy[p] = 0;
    }
    if(tag[p])
    {
        if(son[p][0]) cover(son[p][0],cov[p]);
        if(son[p][1]) cover(son[p][1],cov[p]);
        tag[p] = cov[p] = 0;
    }
}

void split(int p,int k,int &x,int &y)
{
    if(p) pushdown(p);
    if(p == 0) {x = y = 0;return;}
    if(size[son[p][0]] + 1 <= k) x = p,split(son[p][1],k - size[son[p][0]] - 1,son[p][1],y);
    else y = p,split(son[p][0],k,x,son[p][0]);
    pushup(p);
}

int merge(int u,int v)
{
    if(u == 0 || v == 0) return u | v;
    if(dat[u] > dat[v])
    {
        pushdown(u);
        son[u][1] = merge(son[u][1],v);
        pushup(u);
        return u;
    }
    else
    {
        pushdown(v);
        son[v][0] = merge(u,son[v][0]);
        pushup(v);
        return v;
    }
}

void remove(int p)
{
    if(p == 0) return;
    stk[++len] = p;
    if(son[p][0]) remove(son[p][0]);
    if(son[p][1]) remove(son[p][1]);
}

int get_node(int p,int k)
{
    while(1)
    {
        if(k <= size[son[p][0]]) p = son[p][0];
        else if(k == size[son[p][0]] + 1) return p;
        else k -= size[son[p][0]] + 1,p = son[p][1];
    }
}

int get_val(int p,int k){return val[get_node(p,k)];}

int build(int l,int r)
{
    if(l == r){return New(a[l]);}
    int mid = (l + r) >> 1;
    int x = merge(build(l,mid),build(mid + 1,r));
    return x;
}

}tree;

int main()
{
    // freopen("input.in","r",stdin);
    // freopen("out.out","w",stdout);
    srand(time(0));
    n = read(),m = read();
    for(int i = 1;i <= 2e5;i++) stk[++len] = i;
    for(int i = 1;i <= n;i++) a[i] = read();
    tree.root = tree.merge(tree.root,tree.build(1,n));
    while(m--)
    {
        cin >> opt;
        if(opt == "INSERT")
        {
            int x,y,z;
            pos = read(),tot = read();
            tree.split(tree.root,pos,x,y);
            for(int i = 1;i <= tot;i++) a[i] = read();
            tree.root = tree.merge(tree.merge(x,tree.build(1,tot)),y);
        }
        if(opt == "DELETE")
        {
            int x,y,z;
            pos = read(),tot = read();
            tree.split(tree.root,pos - 1,x,y);
            tree.split(y,tot,y,z);
            tree.remove(y);
            tree.root = tree.merge(x,z);
        }
        if(opt == "MAKE-SAME")
        {
            int x,y,z;
            pos = read(),tot = read(),c = read();
            tree.split(tree.root,pos - 1,x,y);
            tree.split(y,tot,y,z);
            tree.cover(y,c);
            tree.root = tree.merge(tree.merge(x,y),z);
        }
        if(opt == "REVERSE")
        {
            int x,y,z;
            pos = read(),tot = read();
            tree.split(tree.root,pos - 1,x,y);
            tree.split(y,tot,y,z);
            tree.reverse(y);
            tree.root = tree.merge(tree.merge(x,y),z);
        }
        if(opt == "GET-SUM")
        {
            int x,y,z;
            pos = read(),tot = read();
            tree.split(tree.root,pos - 1,x,y);
            tree.split(y,tot,y,z);
            write(tree.sum[y]),putchar('\n');
            tree.root = tree.merge(tree.merge(x,y),z);
        }
        if(opt == "GET")
        {
            pos = read();
            write(tree.get_val(tree.root,pos)),putchar('\n');
        }
        if(opt == "MAX-SUM")
        {
            int x,y,z;
            pos = read(),tot = read();
            tree.split(tree.root,pos - 1,x,y);
            tree.split(y,tot,y,z);
            write(tree.maxzd[y]),putchar('\n');
            tree.root = tree.merge(tree.merge(x,y),z);
        }
    }
    return 0;
}