前言
这篇博客是 ( m FHQ Treap)。
说句闲话，研究平衡树的最好方法是：A了这道题，祝你们成功（滑稽
题目
讲解
没什么好说的，只是过了这道题很爽，想水一下博客庆祝庆祝。
所有操作都是模板，确实没什么好讲的，就讲几个细节吧。
-
记得回收空间。
-
Reverse操作的时候除了交换左右儿子，还要记得交换左右最大子段和。 -
最大子段和不能为空集。
-
更新最大子段和的时候很有可能会用到 (0) 号点，所以要把 (0) 号点与最大子段和相关的东西赋值为 (-infty)。
-
插入的时候先把插入的点建成一棵很平衡的树再插入，这样不开 (O2) 才能过。
代码
大常数代码
//12252024832524
#include <cstdio>
#include <cstring>
#include <algorithm>
#define TT template<typename T>
using namespace std;
typedef long long LL;
const int MAXN = 500005;
const int MOD = 1e9 + 7;
int n,m;
char opt[10];
LL Read()
{
LL x = 0,f = 1;char c = getchar();
while(c > '9' || c < '0'){if(c == '-')f = -1;c = getchar();}
while(c >= '0' && c <= '9'){x = (x*10) + (c^48);c = getchar();}
return x * f;
}
TT void Put1(T x)
{
if(x > 9) Put1(x/10);
putchar(x%10^48);
}
TT void Put(T x,char c = -1)
{
if(x < 0) putchar('-'),x = -x;
Put1(x); if(c >= 0) putchar(c);
}
TT T Max(T x,T y){return x > y ? x : y;}
TT T Min(T x,T y){return x < y ? x : y;}
TT T Abs(T x){return x < 0 ? -x : x;}
int rt;
struct FHQ_Treap
{
int l,r,val,siz,s,rd;//左右儿子、权值、siz、区间和、om value
int lz1;//区间赋值标记
int lz2;//翻转标记
int lm,rm,ms;//左右及全局最大子段和
}t[MAXN];
int q[MAXN],tl = 500000;
unsigned long long lst = 233;
int Rand()
{
lst *= 20050525;
lst += 520123;
return (int)(lst % MOD);
}
int newnode(int val)
{
int ret = q[tl--];
if(t[ret].l) q[++tl] = t[ret].l;
if(t[ret].r) q[++tl] = t[ret].r;
t[ret].lz1 = MOD;
t[ret].lz2 = t[ret].l = t[ret].r = 0;
t[ret].siz = 1;
t[ret].lm = t[ret].rm = t[ret].ms = t[ret].s = t[ret].val = val;
t[ret].rd = Rand();
return ret;
}
void rev(int x)
{
if(!x) return;
t[x].lz2 ^= 1;
swap(t[x].l,t[x].r);
swap(t[x].lm,t[x].rm);
}
void fuzhi(int x,int val)
{
if(!x) return;
t[x].lz1 = val;
t[x].s = t[x].siz * val;
t[x].val = val;
t[x].lm = t[x].rm = t[x].ms = Max(val,t[x].s);
}
void down(int x)
{
if(t[x].lz1^MOD) fuzhi(t[x].l,t[x].lz1),fuzhi(t[x].r,t[x].lz1),t[x].lz1 = MOD;
if(t[x].lz2) rev(t[x].l),rev(t[x].r),t[x].lz2 = 0;
}
void up(int x)
{
t[x].siz = t[t[x].l].siz + t[t[x].r].siz + 1;
t[x].s = t[t[x].l].s + t[t[x].r].s + t[x].val;
t[x].lm = t[t[x].l].lm; t[x].lm = Max(t[x].lm,t[t[x].l].s + t[x].val + Max(0,t[t[x].r].lm));
t[x].rm = t[t[x].r].rm; t[x].rm = Max(t[x].rm,t[t[x].r].s + t[x].val + Max(0,t[t[x].l].rm));
t[x].ms = Max(t[t[x].l].ms,t[t[x].r].ms);
t[x].ms = Max(t[x].ms,Max(t[x].lm,t[x].rm));
t[x].ms = Max(t[x].ms,t[x].val+Max(0,t[t[x].l].rm)+Max(0,t[t[x].r].lm));
}
void split(int now,int val,int &x,int &y)
{
if(!now) {x = y = 0;return;}
down(now);
if(t[t[now].l].siz+1 <= val)
{
x = now;
split(t[now].r,val-t[t[now].l].siz-1,t[now].r,y);
}
else
{
y = now;
split(t[now].l,val,x,t[now].l);
}
up(now);
}
int mge(int x,int y)
{
if(!x || !y) return x|y;
if(t[x].rd < t[y].rd)
{
down(x);
t[x].r = mge(t[x].r,y); up(x);
return x;
}
else
{
down(y);
t[y].l = mge(x,t[y].l); up(y);
return y;
}
}
void recycle(int x){q[++tl] = x;}
int a[MAXN];
int Build(int l,int r)
{
if(l > r) return 0;
int mid = (l+r) >> 1;
int now = newnode(a[mid]);
t[now].l = Build(l,mid-1);
t[now].r = Build(mid+1,r);
up(now);
return now;
}
int main()
{
// freopen("P2042_2.in","r",stdin);
// freopen("mine.out","w",stdout);
t[0].lm = t[0].rm = t[0].ms = -MOD;
for(int i = 1;i <= tl;++ i) q[i] = i;
n = Read(); m = Read();
for(int i = 1;i <= n;++ i) rt = mge(rt,newnode(Read()));
int x,y,z;
while(m --> 0)
{
scanf("%s",opt);
if(opt[0] == 'I')
{
int pos = Read(),len = Read();
split(rt,pos,x,y);
for(int i = 1;i <= len;++ i) a[i] = Read();
rt = mge(mge(x,Build(1,len)),y);
}
else if(opt[0] == 'D')
{
int pos = Read(),len = Read();
split(rt,pos-1,x,y);
split(y,len,y,z);
rt = mge(x,z);
recycle(y);
}
else if(opt[2] == 'K')
{
int pos = Read(),len = Read();
split(rt,pos-1,x,y);
split(y,len,y,z);
fuzhi(y,Read());
rt = mge(mge(x,y),z);
}
else if(opt[0] == 'R')
{
int pos = Read(),len = Read();
split(rt,pos-1,x,y);
split(y,len,y,z);
rev(y);
rt = mge(mge(x,y),z);
}
else if(opt[0] == 'G')
{
int pos = Read(),len = Read();
split(rt,pos-1,x,y);
split(y,len,y,z);
Put(t[y].s,'
');
rt = mge(mge(x,y),z);
}
else if(opt[2] == 'X') Put(t[rt].ms,'
');
}
return 0;
}