数列所有公式大全_finish验证失败是什么意思

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 3000010, INF = 1e9;
int nodes[N], tt;
struct Node{ 
   
    int s[2], v, p;
    int same, rev;
    int siz, ms, ls, rs, sum;
    void init(int _p, int _v)
    { 
   
        v = _v, p = _p; s[0] = s[1] = 0;
        same = rev = 0;
        siz = 1; sum = ms = v; ls = rs = max(v, 0);
    }
}t[N];
int root, idx;
int w[N];
void pushup(int u)
{ 
   
    auto &fa = t[u], &l = t[t[u].s[0]], &r = t[t[u].s[1]];
    fa.siz = l.siz + r.siz + 1;
    fa.ms = max(max(l.ms, r.ms), l.rs + r.ls + fa.v);
    fa.ls = max(l.ls, l.sum + r.ls + fa.v);
    fa.rs = max(r.rs, r.sum + l.rs + fa.v);
    fa.sum = l.sum + r.sum + fa.v;
}
void pushdown(int x)
{ 
   
    auto &u = t[x], &l = t[t[x].s[0]], &r = t[t[x].s[1]];
    if(u.same)
    { 
   
        u.same = u.rev = 0;
        if(u.s[0]) l.same = 1, l.v = u.v, l.sum = l.siz * l.v;
        if(u.s[1]) r.same = 1, r.v = u.v, r.sum = r.siz * r.v;
        if(u.v > 0)
        { 
   
            if(u.s[0]) l.ls = l.rs = l.ms = l.sum;
            if(u.s[1]) r.ls = r.rs = r.ms = r.sum;
        }
        else 
        { 
   
            if(u.s[0]) l.ls = l.rs = 0, l.ms = l.v;
            if(u.s[1]) r.ls = r.rs = 0, r.ms = r.v;
        }
    }
    else if(u.rev)
    { 
   
        u.rev = 0; l.rev ^= 1, r.rev ^= 1;
        swap(l.s[0], l.s[1]); swap(l.ls, l.rs);
        swap(r.s[0], r.s[1]); swap(r.ls, r.rs);
    }
}
void rotate(int x)
{ 
   
    int y = t[x].p, z = t[y].p;
    int k = t[y].s[1] == x;
    t[z].s[t[z].s[1] == y] = x; t[x].p = z;
    t[y].s[k] = t[x].s[k ^ 1], t[t[x].s[k ^ 1]].p = y;
    t[x].s[k ^ 1] = y; t[y].p = x;
    pushup(y); pushup(x);
}
void splay(int x, int p)
{ 
   
    while(t[x].p != p)
    { 
   
        int y = t[x].p, z = t[y].p;
        if(z != p)
            if(t[y].s[1] == x ^ t[z].s[1] == y) rotate(x);
            else rotate(y);
        rotate(x);
    }
    if(!p) root = x;
}
int build(int l, int r,int p)
{ 
   
    int mid = l + r >> 1;
    int u = nodes[tt --];
    t[u].init(p, w[mid]);
    if(mid > l) t[u].s[0] = build(l, mid - 1, u); 
    if(mid < r) t[u].s[1] = build(mid + 1, r, u);
    pushup(u);
    return u;
}
int get_k(int siz)
{ 
   
    int u = root;
    while(u)
    { 
   
        pushdown(u);
        if(t[t[u].s[0]].siz >= siz) u = t[u].s[0];
        else if(t[t[u].s[0]].siz + 1 == siz) return u;
        else siz -= t[t[u].s[0]].siz + 1, u = t[u].s[1];
    }
    return -1;
}
void dfs(int u)
{ 
   
    if(t[u].s[0]) dfs(t[u].s[0]);
    if(t[u].s[1]) dfs(t[u].s[1]);
    nodes[++ tt] = u;
}
int main()
{ 
   
    for(int i = 1; i < N; ++ i) nodes[++ tt] = i;
    int n, m; scanf("%d%d", &n, &m);

    w[0] = -INF, w[n + 1] = -INF;
    t[0].ms = -INF;
    for(int i = 1; i <= n; ++ i) scanf("%d", &w[i]);
    root = build(0, n + 1, 0);
    char op[10];
    while(m --)
    { 
   
        scanf("%s", op);
        if(!strcmp(op, "INSERT"))
        { 
   
            int pos, len;
            scanf("%d%d", &pos, &len);
            for(int i = 0; i < len; ++ i) scanf("%d", &w[i]);
            int l = pos + 1, r = pos + 2;
            l = get_k(l); r = get_k(r);
            splay(l, 0); splay(r, l);
            t[r].s[0] = build(0, len - 1, r);
            pushup(r); pushup(l);
        }
        else if(!strcmp(op, "DELETE"))
        { 
   
            int pos, len;scanf("%d%d", &pos, &len);
            int l = get_k(pos), r = get_k(pos + len + 1);
            splay(l, 0); splay(r, l);
            dfs(t[r].s[0]);
            t[r].s[0] = 0;
            pushup(r); pushup(l);
            
        }
        else if(!strcmp(op, "MAKE-SAME"))
        { 
   
            int pos, len, c; scanf("%d%d%d", &pos, &len, &c);
            int l =get_k(pos), r = get_k(pos + len + 1);
            splay(l, 0); splay(r, l);
            auto &ch = t[t[r].s[0]];
            ch.same = 1; ch.v = c; ch.sum = c * ch.siz;
            if(c > 0) ch.ms = ch.ls = ch.rs = ch.sum;
            else ch.ms = ch.v, ch.ls = ch.rs = 0;
            pushup(r); pushup(l);
        }
        else if(!strcmp(op, "REVERSE"))
        { 
   
            int pos, len; scanf("%d%d", &pos, &len);
            int l =get_k(pos), r = get_k(pos + len + 1);
            splay(l, 0); splay(r, l);
            auto &ch = t[t[r].s[0]];
            ch.rev ^= 1;
            swap(ch.s[0], ch.s[1]);
            swap(ch.ls, ch.rs);
            pushup(r); pushup(l);
        }
        else if(!strcmp(op, "GET-SUM"))
        { 
   
            int pos, len; scanf("%d%d", &pos, &len);
            int l =get_k(pos), r = get_k(pos + len + 1);
            splay(l, 0); splay(r, l);
            printf("%d\n", t[t[r].s[0]].sum);
        }
        else printf("%d\n", t[root].ms);
        
    }
}