数列所有公式大全_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);
}
}