rockdu
题目描述
请写一个程序，要求维护一个数列，支持以下 6 种操作：（请注意，格式栏 中的下划线‘ _ ’表示实际输入文件中的空格）
输入输出格式
输入格式：
输入文件的第 1 行包含两个数 N 和 M，N 表示初始时数列中数的个数，M 表示要进行的操作数目。 第 2 行包含 N 个数字，描述初始时的数列。 以下 M 行，每行一条命令，格式参见问题描述中的表格
输出格式：
对于输入数据中的 GET-SUM 和 MAX-SUM 操作，向输出文件依次打印结 果，每个答案（数字）占一行。
输入输出样例
输入样例#1： 复制
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： 复制
-1 10 1 10
说明
你可以认为在任何时刻，数列中至少有 1 个数。
输入数据一定是正确的，即指定位置的数在数列中一定存在。
50%的数据中，任何时刻数列中最多含有 30 000 个数；
100%的数据中，任何时刻数列中最多含有 500 000 个数。
100%的数据中，任何时刻数列中任何一个数字均在[-1 000, 1 000]内。
100%的数据中，M ≤20 000，插入的数字总数不超过 4 000 000 。
平衡树裸题，就是写的有点蛋疼……维护和最大的一串的话，就按基本套路。左端点开始的最大，右端点开始的最大中间的最大。每一次查询root就可以了。
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn = 5e5 + 5;
const int inf = 0x3f3f3f3f >> 1;
char s[10];
namespace Splay {
const int L = 0, R = 1;
struct node {
int ch[2], size, num, fa;
int sum, edit, rev, Lmax, Rmax, Mmax;
}tree[maxn];
queue<int > Mempool;
int root, cnt, null;
int Newnode() {
if(Mempool.empty()) return ++cnt;
null = Mempool.front(); Mempool.pop();
return tree[null] = (node){}, tree[null].edit = -inf, null;
}
void push_up(int rt) {
int tl = tree[rt].ch[L], tr = tree[rt].ch[R];
tree[rt].sum = tree[tl].sum + tree[tr].sum + tree[rt].num;
tree[rt].Lmax = max(tree[tl].sum + tree[rt].num + tree[tr].Lmax, tree[tl].Lmax);
tree[rt].Rmax = max(tree[tr].sum + tree[rt].num + tree[tl].Rmax, tree[tr].Rmax);
tree[rt].Mmax = max(max(tree[tl].Mmax, tree[tr].Mmax), tree[tl].Rmax + tree[rt].num + tree[tr].Lmax);
tree[rt].size = tree[tl].size + tree[tr].size + 1;
}
void push_down(int rt) {
int tl = tree[rt].ch[L], tr = tree[rt].ch[R];
if(tree[rt].edit >= -100000) {
int w = tree[rt].edit, sz = tree[rt].size;
tree[tl].edit = tree[tl].num = tree[tr].edit = tree[tr].num = w;
tree[rt].rev = tree[tl].rev = tree[tr].rev = 0;
tree[tl].sum = w * tree[tl].size, tree[tr].sum = w * tree[tr].size;
if(tl) {
tree[tl].Lmax = tree[tl].Rmax = max(tree[tl].sum, 0);
tree[tl].Mmax = max(tree[tl].sum, w);
}
if(tr) {
tree[tr].Lmax = tree[tr].Rmax = max(tree[tr].sum, 0);
tree[tr].Mmax = max(tree[tr].sum, w);
}
tree[rt].edit = -inf;
} else if(tree[rt].rev) {
tree[tl].rev ^= 1, tree[tr].rev ^= 1;
swap(tree[rt].ch[L], tree[rt].ch[R]);
swap(tree[tl].Lmax, tree[tl].Rmax);
swap(tree[tr].Lmax, tree[tr].Rmax);
tree[rt].rev = 0;
}
}
void recyc(int rt) {
Mempool.push(rt);
if(tree[rt].ch[L]) recyc(tree[rt].ch[L]);
if(tree[rt].ch[R]) recyc(tree[rt].ch[R]);
}
void rotate(int rt) {
int p = tree[rt].fa, a = tree[p].fa;
int r = tree[p].ch[R] == rt, l = r ^ 1;
if(a) tree[a].ch[tree[a].ch[R] == p] = rt;
tree[rt].fa = a, tree[p].fa = rt, tree[tree[rt].ch[l]].fa = p;
tree[p].ch[r] = tree[rt].ch[l], tree[rt].ch[l] = p;
push_up(p), push_up(rt);
}
void splay(int rt, int y) {
int des = tree[y].fa;
while(tree[rt].fa != des) {
int p = tree[rt].fa, a = tree[p].fa;
push_down(p), push_down(rt);
if(p != y) {
if((tree[a].ch[R] == p) ^ (tree[p].ch[R] == rt)) rotate(rt);
else rotate(p);
}
rotate(rt);
}
if(y == root) root = rt;
push_up(rt);
}
int qnode(int rank) {
int now = root;
++rank, push_down(now);
for(int tl = tree[now].ch[L]; now; push_down(now), tl = tree[now].ch[L]) {
if(rank <= tree[tl].size) now = tl;
else if(rank > tree[tl].size + 1)
rank -= tree[tl].size + 1, now = tree[now].ch[R];
else return now;
}
return now;
}
void Rev(int l, int r) {
int ls = qnode(l - 1), rs = qnode(r + 1), rt;
splay(ls, root), splay(rs, tree[ls].ch[R]);
tree[rt = tree[rs].ch[L]].rev ^= 1;
swap(tree[rt].Lmax, tree[rt].Rmax);
push_up(rs), push_up(ls);
}
void build(int & rt, int l, int r, int last, int * arr) {
int mid = l + r >> 1, w = arr[mid];
rt = Newnode();
if(l == r) {
tree[rt].size = 1;
tree[rt].rev = 0, tree[rt].sum = w;
}
tree[rt].Lmax = tree[rt].Rmax = max(w, 0);
tree[rt].Mmax = w, tree[rt].edit = -inf;
tree[rt].num = w, tree[rt].fa = last;
if(l < mid) build(tree[rt].ch[L], l, mid - 1, rt, arr);
if(r > mid) build(tree[rt].ch[R], mid + 1, r, rt, arr);
if(tree[rt].size != 1) push_up(rt);
}
void Ins(int n, int pos, int * arr) {
if(!n) return;
int pr = qnode(pos), su = qnode(pos + 1);
splay(pr, root), splay(su, tree[root].ch[R]);
build(tree[su].ch[L], 1, n, su, arr);
push_up(su), push_up(pr);
}
void Del(int pos, int len) {
if(!len) return;
int pr = qnode(pos - 1), su = qnode(pos + len);
splay(pr, root), splay(su, tree[root].ch[R]), recyc(tree[su].ch[L]);
tree[su].ch[L] = 0, push_up(su), push_up(pr);
}
void Edit(int pos, int len, int w) {
if(!len) return;
int pr = qnode(pos - 1), su = qnode(pos + len);
splay(pr, root), splay(su, tree[root].ch[R]);
int now = tree[su].ch[L];
tree[now].edit = tree[now].num = w;
tree[now].sum = tree[now].size * w;
tree[now].Lmax = tree[now].Rmax = max(tree[now].sum, 0);
tree[now].Mmax = max(tree[now].sum, w);
push_up(su), push_up(pr);
}
int GetSum(int pos, int len) {
if(!len) return 0;
int pr = qnode(pos - 1), su = qnode(pos + len);
splay(pr, root), splay(su, tree[root].ch[R]);
return tree[tree[su].ch[L]].sum;
}
}
int n, m, u, v, arr[maxn], a, b, c;
int main() {
using namespace Splay;
scanf("%d%d", &n, &m);
tree[0].Mmax = arr[0] = arr[n + 1] = -inf;
tree[0].Mmax = -inf;
for(register int i = 1; i <= n; ++i) scanf("%d", &arr[i]);
build(root, 0, n + 1, 0, arr);
while(m--) {
scanf("%s", s);
if(s[2] == 'X') {
printf("%d\n", tree[root].Mmax);
} else {
scanf("%d%d", &a, &b);
if(s[2] == 'S') {
for(register int i = 1; i <= b; ++i) scanf("%d", &arr[i]);
Ins(b, a, arr);
} else if(s[2] == 'L') Del(a, b);
else if(s[2] == 'K') scanf("%d", &c), Edit(a, b, c);
else if(s[2] == 'V') Rev(a, a + b - 1);
else if(s[2] == 'T') printf("%d\n", GetSum(a, b));
}
}
return 0;
}
没有帐号? 立即注册