题目描述
请写一个程序，要求维护一个数列，支持以下 6 种操作：（请注意，格式栏 中的下划线‘ _ ’表示实际输入文件中的空格）
输入输出格式
输入格式：
输入文件的第 1 行包含两个数 N 和 M，N 表示初始时数列中数的个数，M 表示要进行的操作数目。 第 2 行包含 N 个数字，描述初始时的数列。 以下 M 行，每行一条命令，格式参见问题描述中的表格
输出格式：
对于输入数据中的 GET-SUM 和 MAX-SUM 操作，向输出文件依次打印结 果，每个答案（数字）占一行。
SOL：
我们发现这是一道fhq_treap的模板题。
我们首先要会fhq_treap。（splay也可以）
我们发现一颗树无论如何旋转（或者split后merge），其中序遍历总是不变的（这是区间操作的基础）
如果我们按照想要的中序遍历建树并且合并，我们一定能得到正确的区间，所以平衡树的区间操作是正确的。
这也是平衡树的两大建立方式之一：按中序遍历建树（另外一种是按权值建树……就是最常见的那种）
这样就涉及到一个没有出现的函数：build（建树）函数。
我们可以暴力建树：（以洛谷p3391 文艺平衡树为例）
Treap* build(int l,int r){
if (l>r) return rr;//我们有#define rr NULL
Treap *now=new Treap();//这里的值是可以改的，就是数组里的真实值
now->son[]=build(l,MID-);//递归处理
now->son[]=build(MID+,r);
now->rub();//更新该节点的信息
return now;
}
我们有2个懒标记 ：flip,mark。
filp 是指指是不是被染成了同一种颜色，而mark标记是是否翻转。我们来看一下如何维护mark标记
void pushdown(Treap* x)
{ if (x && x->mark)
{ x->mark=;
swap(x->son[],x->son[]);
if (x->son[]) x->son[]->mark^=;
if (x->son[]) x->son[]->mark^=;
}
}
我们发现异常的简洁。这样我们就可以轻松的维护mark标记了。
那么我们就只剩最后一个操作了:MAX—SUM，我们便可以维护一个区间的ls，rs，maxsum三个值：
ls是从左边起的极大序列 ，rs从右边起的极大序列 。maxsum是这个区间的最大值。
那么我们合并时，新区间的最大值只有2种情况：
1.最大值是两个子区间的最大值中的一个。
2.最大值是左区间的rs并上当前节点并上右区间的ls
那么我们就做完了。
#include<bits/stdc++.h>
#define N 500007
#define MAXN 4000007
#define inf 0x3f3f3f3f
#define MARICLE __attribute__((optimize("-O2")))
using namespace std;
#define stack rrsb
int n,a[N],point;
#define sight(c) ('0'<=c&&c<='9')
#define Sight(c) ('A'<=c&&c<='Z'||c=='-')
#define abs(x) ((x)>0?(x):(-x))
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define getchar nc
inline char nc() {
static char buf[],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,,,stdin),p1==p2)?EOF:*p1++;
}
MARICLE inline void read(int &x) {
static char c;
static int b;
for (b=,c=getchar(); !sight(c); c=getchar()) if (c=='-') b=-;
for (x=; sight(c); c=getchar()) x=x*+c-;
x*=b;
}
MARICLE inline void reads(char* op) {
static char c;
static int b;
for (b=,c=getchar(); !Sight(c); c=getchar());
for (; Sight(c); c=getchar()) op[b++]=c;
}
struct Treap {
Treap *ch[];
int val,key,size,sum,l,r,m;
bool flip,mark;
MARICLE Treap() {
/*val=l=r=m=-inf;sum=0;size=0;mark=flip=0;key=rand();*/
}
MARICLE void re() {
val=l=r=m=-inf;
sum=;
size=;
mark=flip=;
key=rand();
}
MARICLE inline void update() {
size=ch[]->size+ch[]->size+;
sum=val+ch[]->sum+ch[]->sum;
l=max(ch[]->l,max(ch[]->sum+val,ch[]->sum+val+ch[]->l));
r=max(ch[]->r,max(val+ch[]->sum,ch[]->r+val+ch[]->sum));
m=max(ch[]->m,max(max(,ch[]->r)+val+max(,ch[]->l),ch[]->m));
}
};
Treap *null=new Treap(),*root=null,*stack[N],*x,*last;
MARICLE inline void Maintain_flip(Treap *o) {
if(o==null)return;
o->flip^=;
swap(o->l,o->r);
}
MARICLE inline void Maintain_mark(Treap *o,int c) {
if(o==null)return;
o->val=c;
o->sum=o->size*c;
o->l=o->r=o->m=max(o->size*c,c);
o->mark=;
}
MARICLE inline void pushdown(Treap *o) {
if(o==null)return;
if(o->flip) {
o->flip^=;
Maintain_flip(o->ch[]);
Maintain_flip(o->ch[]);
swap(o->ch[],o->ch[]);
}
if(o->mark) {
Maintain_mark(o->ch[],o->val);
Maintain_mark(o->ch[],o->val);
o->mark=;
}
}
MARICLE inline Treap* newTreap(int val) {
Treap *o=new Treap();
o->ch[]=o->ch[]=null;
o->key=rand();
o->val=o->sum=val;
o->size=;
o->flip=o->mark=;
o->m=o->l=o->r=val;
return o;
}
MARICLE Treap *merge(Treap *a,Treap *b) {
if(a==null)return b;
if(b==null)return a;
pushdown(a);
pushdown(b);
if(a->key < b->key) {
a->ch[]=merge(a->ch[],b);
a->update();
return a;
} else {
b->ch[]=merge(a,b->ch[]);
b->update();
return b;
}
}
MARICLE void split(Treap *now,int k,Treap* &x,Treap* &y) {
if (now==null) {
x=y=null;
return;
}
pushdown(now);
int cmp=now->ch[]?now->ch[]->size+:;
if (k<cmp) y=now,split(y->ch[],k,x,y->ch[]);
else x=now,split(x->ch[],k-cmp,x->ch[],y);
now->update();
}
int pos,c;
MARICLE inline Treap *build() {
int p=;
for(int i=; i<=n; i++) {
read(a[i]);
x=newTreap(a[i]);
last=null;
while(p&&stack[p]->key > x->key) {
stack[p]->update();
last=stack[p];
stack[p--]=null;
}
if(p)stack[p]->ch[]=x;
x->ch[]=last;
stack[++p]=x;
}
while(p)stack[p--]->update();
return stack[];
}
MARICLE void adjust(Treap *o) {
if(o==null)return;
if(o->ch[]!=null)adjust(o->ch[]);
if(o->ch[]!=null)adjust(o->ch[]);
delete o;
}
Treap* XX,*X,*Y,*Z;
MARICLE inline void insert() {
read(pos);
read(n);
Treap *o=build();
split(root,pos,X,Y);
root=merge(merge(X,o),Y);
}
MARICLE inline void erase() {
read(pos);
read(n);
split(root,pos-,X,Y);
split(Y,n,Y,Z);
adjust(Y);
root=merge(X,Z);
}
MARICLE inline void reverse() {
read(pos);
read(n);
split(root,pos-,X,Y);
split(Y,n,Y,Z);
Maintain_flip(Y);
root=merge(merge(X,Y),Z);
}
MARICLE inline void make_same() {
read(pos);
read(n);
read(c);
split(root,pos-,X,Y);
split(Y,n,Y,Z);
Maintain_mark(Y,c);
root=merge(merge(X,Y),Z);
}
MARICLE inline int get_sum() {
read(pos);
read(n);
if(n==)return ;
split(root,pos-,X,Y);
split(Y,n,Y,Z);
int ret=Y->sum;
root=merge(merge(X,Y),Z);
return ret;
}
int m;
MARICLE void write(int x) {
if (x<) {
putchar(''+x);
return;
}
write(x/);
putchar(''+x%);
}
MARICLE inline void writeln(int x) {
if (x<) putchar('-');
write(abs(x));
putchar('\n');
}
MARICLE int main() {
null->re();
read(n);
read(m);
root=build();
char opt[];
while(m--) {
reads(opt);
// scanf("%s",opt);
switch(opt[]) {
case 'I':
insert();
break;
case 'D':
erase();
break;
case 'M':
if (opt[]!='K') writeln(root->m);
else make_same();
break;
case 'G':
writeln(get_sum());
break;
case 'R':
reverse();
break;
}
}
}