题目大意不多说了
貌似每个苦逼的acmer都要做一下这个splay树的模版题目吧
还是有很多操作的，估计够以后当模版了。。。。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath> using namespace std;
const int N = ;
const int INF = 0x3f3f3f3f;
#define ls ch[x][0]
#define rs ch[x][1] struct SplayTree{
int ch[N][] , pre[N];
int ml[N] , mr[N] , mm[N]; //区间最大
int val[N] , sz[N] , sum[N] , size , rt;
int rev[N] , to[N]; // lazy标记
int del[N] , top; //内部保存删除的数的位置，然后可以从其中提取位置给新进入的元素
int a[N]; void push_up(int x)
{
sz[x] = sz[ls]+sz[rs]+;
sum[x] = sum[ls]+sum[rs]+val[x];
/*********************/
ml[x] = max(ml[ls] , sum[ls]+val[x]+max(ml[rs] , ));
mr[x] = max(mr[rs] , sum[rs]+val[x]+max(mr[ls] , ));
mm[x] = max(mm[ls] , max(mm[rs] , max(ml[rs],)+max(mr[ls],)+val[x]));
/*********************/
} void push_down(int x)
{
if(rev[x]){
if(ls){
rev[ls]^= ;
swap(ml[ls] , mr[ls]);
}
if(rs){
rev[rs]^= ;
swap(ml[rs] , mr[rs]);
}
swap(ls , rs);
rev[x] = ;
}
/**to[x]的初始化要注意**/
if(to[x]!=-INF){
if(ls){
sum[ls] = sz[ls]*to[x];
ml[ls] = mr[ls] = mm[ls] = max(sum[ls] , to[x]);
val[ls] = to[ls] = to[x];
}
if(rs){
sum[rs] = sz[rs]*to[x];
ml[rs] = mr[rs] = mm[rs] = max(sum[rs] , to[x]);
val[rs] = to[rs] = to[x];
}
to[x] = -INF;
}
} void newNode(int &x , int fa , int v)
{
if(top != -)
x = del[top--];
else x = ++size;
ch[x][] = ch[x][] = ;
pre[x] = fa;
val[x] = v , sz[x] = ;
sum[x] = ml[x] = mr[x] = mm[x] = val[x];
rev[x] = , to[x] = -INF;
} void build(int &x , int l , int r , int fa)
{
if(l>r) return;
int m=(l+r)>>;
newNode(x , fa , a[m]);
build(ls , l , m- , x);
build(rs , m+ , r , x);
push_up(x);
} void init(int n)
{
/*****因为所有点的最终叶子节点都下标设为了0，所以0上的数据要不影响整棵树*****/
sz[] = sum[] = ch[][] = ch[][] = val[] = pre[] = ;
to[] = ml[] = mr[] = mm[] = -INF;
rev[] = ;
top = - , rt = size = ;
newNode(rt , , -INF);
newNode(ch[rt][] , rt , -INF);
build(ch[ch[rt][]][] , , n , ch[rt][]);
push_up(ch[rt][]);
push_up(rt);
} void Rotate(int x , int f)
{
int y=pre[x] , z=pre[y];
/**y要旋转到下方，下传lazy标记**/
push_down(y);
ch[y][!f] = ch[x][f] , pre[ch[x][f]] = y;
ch[x][f] = y , pre[y] = x;
ch[z][ch[z][]==y] = x , pre[x]=z;
push_up(y);
push_up(x);
} void Splay(int x , int goal)
{
while(pre[x] != goal){
if(pre[pre[x]] == goal) Rotate(x , ch[pre[x]][]==x);
else{
int y = pre[x] , z = pre[y];
int f = ch[z][] == y;
if(ch[y][f] == x) Rotate(x , !f);
else Rotate(y,f);
Rotate(x , f);
}
}
push_up(x);
if(goal == ) rt = x;
} int Select(int pos)
{
int x = rt;
push_down(x);
while(sz[ls]+ != pos){
if(sz[ls]+>pos) x=ls;
else{
pos = pos-sz[ls]-;
x = rs;
}
push_down(x);
}
return x;
}
/***从pos位置之后插入cnt个值***/
void Insert(int pos , int cnt)
{
int x = Select(pos);
Splay(x , );
int y = Select(pos+);
Splay(y , x);
build(ch[y][] , , cnt , y);
/***这里build将a[1~cnt]插入到splay树中，要push_up更新***/
push_up(y);
push_up(x);
}
/***回收被删除的数的位置***/
void Recycle(int x)
{
if(x){
del[++top]=x;
Recycle(ls);
Recycle(rs);
}
} void Delete(int s , int t)
{
int x = Select(s-) , y = Select(t+);
Splay(x , ) , Splay(y , x);
Recycle(ch[y][]);
ch[y][] = ;
/***这里y的左子树删除，明显子树数据改变，所以要重新push_up更新数据***/
push_up(y);
push_up(x);
}
/****将s~t区间内的所有值都修改为v****/
void update(int s , int t , int v)
{
int x = Select(s-) , y = Select(t+);
Splay(x , ) , Splay(y , x);
int ptr = ch[y][];
to[ptr]=v;
val[ptr]=v;
sum[ptr]=v*sz[ptr];
ml[ptr] = mr[ptr] = mm[ptr] = max(sum[ptr] , v);
return ;
} void Reverse(int s , int t)
{
int x = Select(s-) , y = Select(t+);
Splay(x , ) , Splay(y , x);
int ptr = ch[y][];
rev[ptr]^=;
swap(ml[ptr] , mr[ptr]);
} int querySum(int s , int t)
{
int x = Select(s-) , y = Select(t+);
// cout<<"x: "<<x<<" y: "<<y<<endl;
Splay(x , ) , Splay(y , x);
return sum[ch[y][]];
} int queryMax()
{
int x = Select() , y = Select(sz[rt]);
Splay(x , ) , Splay(y , x);
return mm[ch[y][]];
}
}spt;
int main()
{
// freopen("a.in" , "r" , stdin);
int n , m;
char str[] ;
int s , t , v , pos , k;
while(~scanf("%d%d" , &n , &m))
{
for(int i= ; i<=n ; i++) scanf("%d" , &spt.a[i]);
spt.init(n);
/*
for(int i=0 ; i<=spt.size ; i++){
cout<<"i: "<<i<<" sum: "<<spt.sum[i]<<" l: "<<spt.ch[i][0]<<" lv: "<<spt.val[spt.ch[i][0]]<<" r: "<<spt.ch[i][1]<<" rv: "<<spt.val[spt.ch[i][1]]<<endl;
}*/
for(int i= ; i<m ; i++){
scanf("%s" , str);
if(str[] == 'I'){
scanf("%d%d" , &pos , &k);
for(int i= ; i<=k ; i++) scanf("%d" , &spt.a[i]);
spt.Insert(pos+ , k);
}
else if(str[]=='D'){
scanf("%d%d" , &pos , &k);
spt.Delete(pos+ , pos+k);
}
else if(str[] == 'M' && str[] == 'K'){
scanf("%d%d%d" , &pos , &k , &v);
spt.update(pos+ , pos+k , v);
}
else if(str[] == 'R'){
scanf("%d%d" , &pos , &k);
spt.Reverse(pos+ , pos+k);
}
else if(str[] == 'G'){
scanf("%d%d" , &pos , &k);
printf("%d\n" , spt.querySum(pos+ , pos+k));
}
else{
/****这里不能直接用spt.mm[rt]作为答案，因为为了方便查询，
我们增加了两个不包含在本身数组的点，直接spt.mm[rt]会把这两个点也算进来***/
printf("%d\n" , spt.queryMax());
}
}
}
return ;
}