反正是道平衡树，就拿 fhq_Treap 写了写...
这道题思路基本是围绕“用 Treap 维护中序遍历” 和 中序遍历的性质 来进行的操作
所以就可以类比线段树进行一些操作
1. 建树 & 插入
这题也要用到笛卡尔树的建树方式，假的 O(n) 真是相当快啊
inline int build(int r) {
top = 0;
register int tmp = newnode(a[1]);
stk[++top] = tmp;
for(int i = 2; i <= r; ++i) {
int last = 0, cur = newnode(a[i]);
while(top and t[stk[top]].prio > t[cur].prio) {
pushup(stk[top]);
last = stk[top];
stk[top--] = 0;
}
t[cur].ch[0] = last;
pushup(cur);
if(top) {
t[stk[top]].ch[1] = cur;
pushup(stk[top]);
}
stk[++top] = cur;
}
while(top) pushup(stk[top--]);
return stk[1];
}在本题中呢，由于插入的值不是一个一个给出的而是给出序列，故应先建出一棵小 Treap 再合并过去
在这里也要用到上面提到的方式来建这棵小树
inline void Insert(int pos, int tot) {
int newrt = build(tot);
pair<int, int> x = Split(Root, pos);
Root = Merge(Merge(x.first, newrt), x.second);
return;
}
2.删除
此题的删除也是删除一段序列，直接 Split 出来即可
不过这里注意到任何时刻数列中最多含有 5e5 个数，多写一个内存回收就好了
inline int Malloc(){
register int x;
return (!delpool.empty()) ? (t[x = delpool.front()].clear(), delpool.pop(), x) : (++poolcur);
}
inline int newnode(int val) {
register int cur = Malloc();
t[cur].val = t[cur].sum = t[cur].prtmx = val;
t[cur].lmx = t[cur].rmx = max(0, val);
t[cur].prio = rand();
t[cur].siz = 1;
return cur;
}
void Recycle(int cur) {
if(!cur) return;
if(lson) Recycle(lson);
delpool.push(cur);
if(rson) Recycle(rson);
return;
}
inline void Remove(int pos, int tot) {
pair<int, int> x = Split(Root, pos + tot - 1);
pair<int, int> y = Split(x.first, pos - 1);
Recycle(y.second);
Root = Merge(y.first, x.second);
return;
}觉得递归不优美的可以手写栈模拟
3.区间修改
打标记
inline void cover(int pos, int tot, int val) {
pair<int, int> x = Split(Root, pos + tot - 1);
pair<int, int> y = Split(x.first, pos - 1);
t[y.second].val = t[y.second].cvr = val;
t[y.second].sum = val * t[y.second].siz;
t[y.second].lmx = t[y.second].rmx = max(0, t[y.second].sum);
t[y.second].prtmx = max(t[y.second].val, t[y.second].sum);
t[y.second].rvrs = false;
Root = Merge(Merge(y.first, y.second), x.second);
return;
}
4.翻转区间
比较基础的操作
inline void Reverse(int pos, int tot) {
pair<int, int> x = Split(Root, pos + tot - 1);
pair<int, int> y = Split(x.first, pos - 1);
t[y.second].rvrs ^= 1;
swap(t[y.second].lmx, t[y.second].rmx);
swap(t[y.second].ch[0], t[y.second].ch[1]);
Root = Merge(Merge(y.first, y.second), x.second);
return;
}
5.求和 & 最大子段和
这里一开始不敢这么写，其实是可以的
在提取一个区间的过程中，是在不断 pushup 和 pushdown 的，故提取/合并后并不会出什么差错
像线段树一样维护，一些维护的的值在 Reverse 后注意更新
inline void rvrs(int cur) {
swap(lson, rson);
swap(t[cur].lmx, t[cur].rmx);
t[cur].rvrs ^= 1;
return;
}
inline void cvr(int cur, int val) {
t[cur].cvr = t[cur].val = val;
t[cur].sum = t[cur].siz * val;
t[cur].prtmx = max(t[cur].val, t[cur].sum);
t[cur].lmx = t[cur].rmx = max(0, t[cur].sum);
return;
}
inline void pushup(int cur) {
t[cur].siz = t[lson].siz + t[rson].siz + 1;
t[cur].sum = t[cur].val + t[lson].sum + t[rson].sum;
t[cur].lmx = max(0, max(t[lson].lmx, t[lson].sum + t[rson].lmx + t[cur].val));
t[cur].rmx = max(0, max(t[rson].rmx, t[rson].sum + t[lson].rmx + t[cur].val));
t[cur].prtmx = max(t[cur].val, t[lson].rmx + t[rson].lmx + t[cur].val);
if(lson) t[cur].prtmx = max(t[cur].prtmx, t[lson].prtmx);
if(rson) t[cur].prtmx = max(t[cur].prtmx, t[rson].prtmx);
return;
}
inline void pushdown(int cur) {
if(t[cur].rvrs) {
if(lson) rvrs(lson);
if(rson) rvrs(rson);
}
if(t[cur].cvr != inf) {
if(lson) cvr(lson, t[cur].cvr);
if(rson) cvr(rson, t[cur].cvr);
}
t[cur].rvrs = false;
t[cur].cvr = inf;
return;
}
完整的代码
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<cstdio>
#include<cmath>
#include<queue>
#include<ctime>
#define lson t[cur].ch[0]
#define rson t[cur].ch[1]
using namespace std; const int MAXN = 500010, inf = 2333; struct Node{
int ch[2], siz, val, prio, lmx, rmx, sum, prtmx;
int cvr;
bool rvrs;
Node(){ch[0] = ch[1] = siz = val = sum = 0; cvr = inf; rvrs = false;}
void clear(){
ch[0] = ch[1] = siz = val = sum = 0;
cvr = inf;
rvrs = false;
return;
}
}t[MAXN];
int n, m, poolcur, Root;
int a[MAXN], stk[MAXN], top;
queue<int> delpool;
char que[20]; inline int Malloc(){
register int x;
return (!delpool.empty()) ? (t[x = delpool.front()].clear(), delpool.pop(), x) : (++poolcur);
}
inline int newnode(int val) {
register int cur = Malloc();
t[cur].val = t[cur].sum = t[cur].prtmx = val;
t[cur].lmx = t[cur].rmx = max(0, val);
t[cur].prio = rand();
t[cur].siz = 1;
return cur;
}
inline void pushup(int cur) {
t[cur].siz = t[lson].siz + t[rson].siz + 1;
t[cur].sum = t[cur].val + t[lson].sum + t[rson].sum;
t[cur].lmx = max(0, max(t[lson].lmx, t[lson].sum + t[rson].lmx + t[cur].val));
t[cur].rmx = max(0, max(t[rson].rmx, t[rson].sum + t[lson].rmx + t[cur].val));
t[cur].prtmx = max(t[cur].val, t[lson].rmx + t[rson].lmx + t[cur].val);
if(lson) t[cur].prtmx = max(t[cur].prtmx, t[lson].prtmx);
if(rson) t[cur].prtmx = max(t[cur].prtmx, t[rson].prtmx);
return;
}
inline void rvrs(int cur) {
swap(lson, rson);
swap(t[cur].lmx, t[cur].rmx);
t[cur].rvrs ^= 1;
return;
}
inline void cvr(int cur, int val) {
t[cur].cvr = t[cur].val = val;
t[cur].sum = t[cur].siz * val;
t[cur].prtmx = max(t[cur].val, t[cur].sum);
t[cur].lmx = t[cur].rmx = max(0, t[cur].sum);
return;
}
inline void pushdown(int cur) {
if(t[cur].rvrs) {
if(lson) rvrs(lson);
if(rson) rvrs(rson);
}
if(t[cur].cvr != inf) {
if(lson) cvr(lson, t[cur].cvr);
if(rson) cvr(rson, t[cur].cvr);
}
t[cur].rvrs = false;
t[cur].cvr = inf;
return;
}
inline int build(int r) {
top = 0;
register int tmp = newnode(a[1]);
stk[++top] = tmp;
for(int i = 2; i <= r; ++i) {
int last = 0, cur = newnode(a[i]);
while(top and t[stk[top]].prio > t[cur].prio) {
pushup(stk[top]);
last = stk[top];
stk[top--] = 0;
}
t[cur].ch[0] = last;
pushup(cur);
if(top) {
t[stk[top]].ch[1] = cur;
pushup(stk[top]);
}
stk[++top] = cur;
}
while(top) pushup(stk[top--]);
return stk[1];
}
pair<int, int> Split(int cur, int k) {
if(!cur or !k) return make_pair(0, cur);
pushdown(cur);
pair<int, int> res;
if(t[lson].siz >= k) {
res = Split(lson, k);
lson = res.second;
pushup(cur);
res.second = cur;
} else {
res = Split(rson, k - t[lson].siz - 1);
rson = res.first;
pushup(cur);
res.first = cur;
}
return res;
}
int Merge(int x, int y) {
if(x) pushdown(x); if(y) pushdown(y);
if(!x) return y; if(!y) return x;
if(t[x].prio < t[y].prio) {
t[x].ch[1] = Merge(t[x].ch[1], y);
pushup(x);
return x;
} else {
t[y].ch[0] = Merge(x, t[y].ch[0]);
pushup(y);
return y;
}
}
void Recycle(int cur) {
if(!cur) return;
if(lson) Recycle(lson);
delpool.push(cur);
if(rson) Recycle(rson);
return;
}
inline void Insert(int pos, int tot) {
int newrt = build(tot);
pair<int, int> x = Split(Root, pos);
Root = Merge(Merge(x.first, newrt), x.second);
return;
}
inline void Remove(int pos, int tot) {
pair<int, int> x = Split(Root, pos + tot - 1);
pair<int, int> y = Split(x.first, pos - 1);
Recycle(y.second);
Root = Merge(y.first, x.second);
return;
}
inline void Reverse(int pos, int tot) {
pair<int, int> x = Split(Root, pos + tot - 1);
pair<int, int> y = Split(x.first, pos - 1);
t[y.second].rvrs ^= 1;
swap(t[y.second].lmx, t[y.second].rmx);
swap(t[y.second].ch[0], t[y.second].ch[1]);
Root = Merge(Merge(y.first, y.second), x.second);
return;
}
inline void cover(int pos, int tot, int val) {
pair<int, int> x = Split(Root, pos + tot - 1);
pair<int, int> y = Split(x.first, pos - 1);
t[y.second].val = t[y.second].cvr = val;
t[y.second].sum = val * t[y.second].siz;
t[y.second].lmx = t[y.second].rmx = max(0, t[y.second].sum);
t[y.second].prtmx = max(t[y.second].val, t[y.second].sum);
t[y.second].rvrs = false;
Root = Merge(Merge(y.first, y.second), x.second);
return;
}
inline int getsum(int pos, int tot) {
pair<int, int> x = Split(Root, pos + tot - 1);
pair<int, int> y = Split(x.first, pos - 1);
int ans = t[y.second].sum;
Root = Merge(Merge(y.first, y.second), x.second);
return ans;
}
void rdstr(char s[]) {
register int sz = 0;
register char c = getchar();
while(!isalpha(c) and c != '-') c = getchar();
while(isalpha(c) || (c == '-')) {
s[sz++] = c;
c = getchar();
}
return;
}
inline int rd() {
register int x = 0;
register char c = getchar();
register bool f = false;
while(!isdigit(c)) {
if(c == '-') f = true;
c = getchar();
}
while(isdigit(c)) {
x = x * 10 + (c ^ 48);
c = getchar();
}
return f ? -x : x;
} int main() {
srand(time(NULL));
n = rd(); m = rd();
for(int i = 1; i <= n; ++i) a[i] = rd();
Root = build(n);
int pos, tot, val;
while(m--) {
rdstr(que);
switch(que[0]) {
case 'I':{
pos = rd(); tot = rd();
for(int i = 1; i <= tot; ++i) a[i] = rd();
Insert(pos, tot);
break;
}
case 'D':{
pos = rd(); tot = rd();
Remove(pos, tot);
break;
}
case 'R':{
pos = rd(); tot = rd();
Reverse(pos, tot);
break;
}
case 'G':{
pos = rd(); tot = rd();
printf("%d\n", getsum(pos, tot));
break;
}
case 'M':{
if(que[2] == 'K') {
pos = rd(); tot = rd(); val = rd();
cover(pos, tot, val);
} else {
printf("%d\n", t[Root].prtmx);
}
break;
}
}
}
return 0;
}