【问题描述】
【输入格式】
输入文件的第 1 行包含两个数 N 和 M,N 表示初始时数列中数的个数,M表示要进行的操作数目。第 2 行包含 N 个数字,描述初始时的数列。以下 M 行,每行一条命令,格式参见问题描述中的表格。
【输出格式】
对于输入数据中的 GET-SUM 和 MAX-SUM 操作,向输出文件依次打印结果,每个答案(数字)占一行。
【输入样例】
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
【样例说明】
初始时,我们拥有数列 2 -6 3 5 1 -5 -3 6 3 执行操作 GET-SUM 5 4,表示求出数列中从第 5 个数开始连续 4 个数字之和,1+(-5)+(-3)+6 = -1:
2 -6 3 5 1 -5 -3 6 3
执行操作 MAX-SUM,表示要求求出当前数列中最大的一段和,应为 3+5+1+(-5)+(-3)+6+3 = 10:
2 -6 3 5 1 -5 -3 6 3
执行操作 INSERT 8 3 -5 7 2,即在数列中第 8 个数字后插入-5 7 2,
2 -6 3 5 1 -5 -3 6 -5 7 2 3
执行操作 DELETE 12 1,表示删除第 12 个数字,即最后一个:
2 -6 3 5 1 -5 -3 6 -5 7 2
执行操作 MAKE-SAME 3 3 2,表示从第 3 个数开始的 3 个数字,统一修改为 2:
2 -6 3 5 1 -5 -3 6 -5 7 2
改为
2 -6 2 2 2 -5 -3 6 -5 7 2
执行操作 REVERSE 3 6,表示取出数列中从第 3 个数开始的连续 6 个数:
2 -6 2 2 2 -5 -3 6 -5 7 2
如上所示的灰色部分 2 2 2 -5 -3 6,翻转后得到 6 -3 -5 2 2 2,并放回原来位置:
2 -6 6 -3 -5 2 2 2 -5 7 2
最后执行 GET-SUM 5 4 和 MAX-SUM,不难得到答案 1 和 10。
2 -6 6 -3 -5 2 2 2 -5 7 2
BZOJ 版
题解
本题要求维护 动态连续最大连续和 和 区间和
所以要用 Max,和 Sum 来记录
类似线段树我们需要Pushdown和Pushup函数
此外对于Max 为了更新他的值,我们还需要维护两个变量
l,r 分别记录前缀最大和&后缀最大和
向上传递的
-
对于一个节点更新Max时要分一下几种情况讨论
- 它的左儿子的Max
- 它的右儿子的Max
- 它的左儿子的r加上本节点的权值v
- 它的右儿子的l加上本节点的权值v
- 它的左儿子的r加上本节点的权值v加上右儿子的l
用一张图来表示是这样的
-
我们还需要维护一个节点的 l 与上面相似 要分三种情况
- 它的左儿子的 l
- 它的左儿子的 sum 加上 本节点的权值v
- 它的左节点的 sum 加上 本节点的权值v 加上 他的右儿子的 l
用另一张张图来表示是这样的
-
r与上面的相似
- 它的右儿子的 r
- 它的右儿子的 sum 加上 本节点的权值v
- 它的右节点的 sum 加上 本节点的权值v 加上 他的左儿子的 r
不想画图了╭(╯^╰)╮
-
然后是Sum 直接加起来就好了
向下传递的
-
首先是旋转标记
- 直接下传然后交换左右儿子即可
- 注意异或的用法
-
然后是修改标记
-
首先你不能暴力修改 有一个点会超时,亲测
-
所以想线段树一样我们需要一个标记
-
下传时注意维护Max,sum,l,r 这些值
对于Sum 直接乘就好
对于Max,l,r 要分类讨论
- 如果改变的值为负数那这三个的值都未你改变成的值
- 否则这等于Sum
-
-
对于插入
直接新建一颗树插进去就可以了
最后一步 码代码 调程序
能Pushdown() 就Pushdown()
能Pushup() 就Pushup()
fhq Treap 真好
如果打Splay 我会死的
另外需要注意如果子树为空的返回值
链接们
fhq大佬 挖掘Treap的潜力 - fanhq666的日志
我的板子来源
非旋转Treap及可持久化[Merge,Split] Memphis’s Blog
附朋友的题解
[您有新的未分配科技点] 无旋treap:从单点到区间(例题 BZOJ1500&NOI2005 维护数列 )
[您有新的未分配科技点]无旋treap:从好奇到入门(例题:bzoj3224 普通平衡树)
C++ Code
/* * @Author: WildRage * @Date: 2017-07-15 10:32:15 * @Last Modified by: WildRage * @Last Modified time: 2017-07-15 15:07:46 */#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#define INF 0x3f3f3f3fusing namespace std;struct Node{ int v, key, size, rev; int Max, l, r, sum, change; Node *ch[2]; Node(int x) { v = x; key = rand(); size = 1; rev = 0; change = -INF; Max = x; l = x; r = x; sum = x; ch[0] = ch[1] = NULL; }#define size(_) ((_) ? (_)->size : (0))#define sum(_) ((_) ? (_)->sum : (0))#define l(_) ((_) ? (_)->l : (-INF))#define r(_) ((_) ? (_)->r : (-INF))#define Max(_) ((_) ? (_)->Max : (-INF))#define change(_) ((_) ? (_)->change : (-INF)) void Pushup() { size = 1 + size(ch[1]) + size(ch[0]); l = max(l(ch[0]), max(sum(ch[0]) + v, sum(ch[0]) + v + l(ch[1]))); r = max(r(ch[1]), max(sum(ch[1]) + v, sum(ch[1]) + v + r(ch[0]))); Max = max(Max(ch[0]), max(Max(ch[1]), max(r(ch[0]) + v, max(l(ch[1]) + v, max(r(ch[0]) + l(ch[1]) + v, v))))); sum = sum(ch[0]) + sum(ch[1]) + v; } void reverse() { if (!this) return; swap(ch[0], ch[1]); swap(l, r); rev ^= 1; } void Update() { if (!this) return; if (ch[1]) ch[1]->change = change; if (ch[0]) ch[0]->change = change; sum = size * change; v=change; l=r=Max=max(change,size*change); //change = -INF; } void Pushdown() { if (!this) return; if (rev) { ch[0]->reverse(); ch[1]->reverse(); rev = 0; } if (change != -INF) { ch[0]->Update(); ch[1]->Update(); change=-INF; } }} * root;typedef pair<Node *, Node *> DNode;Node *Merge(Node *A, Node *B){ if (!A) return B; if (!B) return A; if (A->key < B->key) { A->Pushdown(); A->ch[1] = Merge(A->ch[1], B); A->Pushup(); return A; } else { B->Pushdown(); B->ch[0] = Merge(A, B->ch[0]); B->Pushup(); return B; }}DNode Split(Node *rt, int k){ if (!rt) return DNode(NULL, NULL); DNode o; rt->Pushdown(); if (size(rt->ch[0]) >= k) { o = Split(rt->ch[0], k); rt->ch[0] = o.second; rt->Pushup(); o.second = rt; } else { o = Split(rt->ch[1], k - size(rt->ch[0]) - 1); rt->ch[1] = o.first; rt->Pushup(); o.first = rt; } return o;}Node *st[4000005];Node *build(int m){ //memset(st, 0, sizeof(st)); Node *x, *last; int p = 0; int a; for (int i = 1; i <= m; i++) { scanf("%d", &a); x = new Node(a); last = NULL; while (p && st[p]->key > x->key) { st[p]->Pushup(); last = st[p]; st[p--] = NULL; } if (p) st[p]->ch[1] = x; x->ch[0] = last; st[++p] = x; } while (p) st[p--]->Pushup(); return st[1];}Node *kth(int k){ DNode x = Split(root, k - 1); DNode y = Split(x.second, 1); Node *ans = y.first; root = Merge(Merge(x.first, ans), y.second); return ans;}int Rank(Node *rt, int x){ if (!rt) return 0; return x <= rt->v ? Rank(rt->ch[0], x) : Rank(rt->ch[1], x) + size(rt->ch[0]) + 1;}void Insert(int x){ int k = Rank(root, x); DNode y = Split(root, k); Node *n = new Node(x); root = Merge(Merge(y.first, n), y.second);}void remove(int x){ int k = Rank(root, x); DNode a = Split(root, k); DNode b = Split(a.second, 1); root = Merge(a.first, b.second);}void flip(int i, int m){ DNode x = Split(root, i - 1); DNode y = Split(x.second, m); y.first->reverse(); root = Merge(x.first, Merge(y.first, y.second));}void dfs(Node *rt){ if (rt) { rt->Pushdown(); dfs(rt->ch[0]); printf("%d ", rt->v); dfs(rt->ch[1]); }}void Insert(int i, int tot){ Node *x = build(tot); DNode y = Split(root, i); root = Merge(y.first, Merge(x, y.second));}void rmdfs(Node *rt){ if (rt) { rmdfs(rt->ch[0]); rmdfs(rt->ch[1]); } delete rt;}void remove(int i, int tot){ DNode x = Split(root, i - 1); DNode y = Split(x.second, tot); rmdfs(y.first); root = Merge(x.first, y.second);}void Update(int i, int tot, int c){ DNode x = Split(root, i - 1); DNode y = Split(x.second, tot); y.first->change = c; y.first->Update(); //Node *m = build(tot, c); //rmdfs(y.first); root = Merge(x.first, Merge(y.first, y.second));}int get_sum(int i, int tot){ DNode x = Split(root, i - 1); DNode y = Split(x.second, tot); int ans = sum(y.first); root = Merge(x.first, Merge(y.first, y.second)); return ans;}int Max_Sum(){ return Max(root);}int main(){ //freopen("seq2005.in", "r", stdin); //freopen("seq2005.out", "w", stdout); int n, m; scanf("%d%d", &n, &m); root = build(n); //dfs(root); //printf("----------------------\n"); int l, r, c; char s[16]; for (int i = 1; i <= m; i++) { scanf("%s", s); switch (s[0]) { case 'G': scanf("%d%d", &l, &r); printf("%d\n", get_sum(l, r)); break; case 'D': scanf("%d%d", &l, &r); remove(l, r); break; case 'I': scanf("%d%d", &l, &r); Insert(l, r); break; case 'R': scanf("%d%d", &l, &r); flip(l, r); break; case 'M': if (s[2] == 'K') { scanf("%d%d%d", &l, &r, &c); Update(l, r, c); } else { printf("%d\n", Max_Sum()); } } //printf("--------------------------------\n"); //dfs(root); //printf("\n-----------DONE-----------------\n"); } //while (1) ;}