数列所有公式大全_splay树

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元售后保障童叟无欺

请写一个程序，要求维护一个数列，支持以下 6 种操作：（请注意，格式栏中的下划线 _ 表示实际输入文件中的空格）

在这里插入图片描述

输入格式
第 1 行包含两个数 N 和 M，N 表示初始时数列中数的个数，M 表示要进行的操作数目。

第 2 行包含 N 个数字，描述初始时的数列。

以下 M 行，每行一条命令，格式参见问题描述中的表格。

输出格式
对于输入数据中的 GET-SUM 和 MAX-SUM 操作，向输出文件依次打印结果，每个答案（数字）占一行。

数据范围与约定
你可以认为在任何时刻，数列中至少有 1 个数。

输入数据一定是正确的，即指定位置的数在数列中一定存在。

50% 的数据中，任何时刻数列中最多含有 30000 个数；100% 的数据中，任何时刻数列中最多含有 500000 个数。

100% 的数据中，任何时刻数列中任何一个数字均在 [−1000,1000] 内。

100% 的数据中，M≤20000，插入的数字总数不超过 4000000 个，输入文件大小不超过 20 MBytes。

输入样例：
9 8
2 -6 3 5 1 -5 -3 6 3
GET-SUM 5 4
MAX-SUM
INSERT 8 3 -5 7 2
DELETE 12 1
MAKE-SAME 3 3 2
REVERSE 3 6
GET-SUM 5 4
MAX-SUM
输出样例：
-1
10
1
10


#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);
        
    }
}