维护数列
【问题描述】
请写一个程序，要求维护一个数列，支持以下 6 种操作：（请注意，格式栏 中的下划线‘ _ ’表示实际输入文件中的空格）
操作编号 输入文件中的格式
说明
1. 插入
INSERT_posi_tot_c1_c2_…_ctot
在当前数列的第 posi 个数字后插入 tot
个数字：c1, c2, …, ctot；若在数列首插
入，则 posi 为 0
2. 删除
DELETE_posi_tot
从当前数列的第 posi 个数字开始连续
删除 tot 个数字
3. 修改
MAKE-SAME_posi_tot_c
将当前数列的第 posi 个数字开始的连
续 tot 个数字统一修改为 c
4. 翻转
REVERSE_posi_tot
取出从当前数列的第 posi 个数字开始
的 tot 个数字，翻转后放入原来的位置
5. 求和
GET-SUM_posi_tot
计算从当前数列开始的第 posi 个数字
开始的 tot 个数字的和并输出
6. 求和最
大的子列
MAX-SUM
求出当前数列中和最大的一段子列，
并输出最大和
【输入格式】
输入文件的第 1 行包含两个数 N 和 M，N 表示初始时数列中数的个数，M表示要进行的操作数目。
第 2 行包含 N 个数字，描述初始时的数列。
以下 M 行，每行一条命令，格式参见问题描述中的表格。
【输出格式】
对于输入数据中的 GET-SUM 和 MAX-SUM 操作，向输出文件依次打印结果，每个答案（数字）占一行。
【输入样例】
9 82 -6 3 5 1 -5 -3 6 3GET-SUM 5 4MAX-SUM INSERT 8 3 -5 7 2DELETE 12 1MAKE-SAME 3 3 2REVERSE 3 6GET-SUM 5 4MAX-SUM
【输出样例】
-110110
【样例说明】
初始时，我们拥有数列 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
【评分方法】
本题设有部分分，对于每一个测试点：
- 如果你的程序能在输出文件正确的位置上打印 GET-SUM 操作的答案，你可以得到该测试点 60%的分数；
- 如果你的程序能在输出文件正确的位置上打印 MAX-SUM 操作的答案，你可以得到该测试点 40%的分数；
- 以上两条的分数可以叠加，即如果你的程序正确输出所有 GET-SUM 和MAX-SUM 操作的答案，你可以得到该测试点 100%的分数。
请注意：如果你的程序只能正确处理某一种操作，请确定在输出文件正确的位置上打印结果，即必须为另一种操作留下对应的行，否则我们不保证可以正确评分。
【数据规模和约定】
- 你可以认为在任何时刻，数列中至少有 1 个数。
- 输入数据一定是正确的，即指定位置的数在数列中一定存在。
- 50%的数据中，任何时刻数列中最多含有 30 000 个数；
- 100%的数据中，任何时刻数列中最多含有 500 000 个数。
- 100%的数据中，任何时刻数列中任何一个数字均在[-1 000, 1 000]内。
- 100%的数据中，M ≤20 000，插入的数字总数不超过 4 000 000 个，输入文件大小不超过 20MBytes。
【题目大意】
给定一个数列，有插入数列，删除区间，区间修改为同一个值，区间翻转，求区间和，求整个数列的最大子段和这几个操作。
【算法分析】
号称历年NOI最BT的数据结构题。
利用Splay，把要操作的区间的前驱和后继分别Splay到根和根的右结点，然后中间的部分就会聚集在根的右结点的左子树下。这样就可以进行想要的操作了。。。
然后剩下的各种操作的维护的话，你可以把这棵平衡树当成线段树来处理，不过多了一个当前结点，复杂了很多。。。
【其它】
开始在SBT上搞了个类似Splay的操作。。。但是老WA，后来想想还是直接Splay吧。。。
这题做了一整天…速度和beyondvoid的差不多，= =也许是因为我基本上模仿他的吧~
不过那个pushdown确实精妙。。。update的话，我是把维护父亲这一项都搞进去了。。。管他是不是都update一下。另外要注意的，pushdown以后的ml，mr，ms才是可用的。否则可能是虚假的。。。所以我在update里加了pushdown。另外比较猥琐的是第二个数据的话，有一个时刻数列中的数权<0，这样那个ms就要注意一下不能取null里的0值了，注意一下就成。
【CODE】
#include #include using namespace std;
const int inf=500000000;
int a[500001];
struct Splaytype{
struct Node{
Node *l,*r,*fa;
int s,ms,ml,mr,sum,sn,key; // sn for samenum mx for max_x
bool same,rev;
};
Node *root,*null,sp[4000111];
int tot;
void update(Node *x){
if (x==null) return;
bool l=false,r=false;
if (x->l!=null) {l=true; x->l->fa=x; pushdown(x->l);}
if (x->r!=null) {r=true; x->r->fa=x; pushdown(x->r);}
x->s=x->l->s+x->r->s+1;
x->sum=x->l->sum+x->r->sum+x->key;
x->ms=x->key;
if (l) x->ms=max(x->ms,x->l->ms);
if (r) x->ms=max(x->ms,x->r->ms);
if (l) x->ms=max(x->ms,x->l->mr+x->key);
if (r) x->ms=max(x->ms,x->r->ml+x->key);
if (l && r) x->ms=max(x->ms,x->l->mr+x->r->ml+x->key);
x->ml=x->l->sum+x->key;
if (l) x->ml=max(x->ml,x->l->ml);
if (r) x->ml=max(x->ml,x->l->sum+x->key+x->r->ml);
x->mr=x->r->sum+x->key;
if (r) x->mr=max(x->mr,x->r->mr);
x->mr=max(x->mr,x->r->sum+x->key+x->l->mr);
}
void pushdown(Node *x){
if (x==null) return;
if (x->rev){
x->rev=false;
swap(x->l,x->r);
if (x->l!=null) x->l->rev=!x->l->rev;
if (x->r!=null) x->r->rev=!x->r->rev;
swap(x->ml,x->mr);
}
if (x->same){
x->same=false;
if (x->l!=null) {x->l->same=true; x->l->sn=x->sn;}
if (x->r!=null) {x->r->same=true; x->r->sn=x->sn;}
x->key=x->sn;
x->sum=x->s*x->key;
x->ms=x->ml=x->mr=max(x->sum,x->key);
}
}
void rotate(Node *x,char op){
Node *y=x->fa;
if (op==’l’){y->r=x->l; x->l=y;}
else{y->l=x->r; x->r=y;}
if (y->fa->l==y) y->fa->l=x;
else y->fa->r=x;
x->fa=y->fa;
update(y);
update(x);
}
Node* newnode(int key){
Node *p=&sp[++tot];
p->l=null; p->r=null; p->fa=null;
p->s=1; p->ms=p->ml=p->mr=p->sum=p->key=key;
p->sn=0; p->same=false; p->rev=false;
return p;
}
void init(){
Node *p,*q;
tot=0;
null=&sp[0];
null->l=null; null->r=null; null->fa=null;
null->s=null->ms=null->ml=null->mr=null->sum=null->sn=0;
null->same=null->rev=false; null->key=0;
root=newnode(-inf);
p=newnode(-inf);
q=newnode(-inf);
root->l=q;
q->l=p;
update(q);
update(root);
}
void Splay(Node *x,Node *pos){
if (x==null || x==pos) return;
pushdown(x);
Node *y,*z;
while (x->fa!=pos){
y=x->fa; z=y->fa;
if (z==pos)
if (y->l==x) rotate(x,’r’);
else rotate(x,’l’);
else if (z->l==y)
if (y->l==x) {rotate(y,’r’); rotate(x,’r’);}
else {rotate(x,’l’); rotate(x,’r’);}
else
if (y->r==x) {rotate(y,’l’); rotate(x,’l’);}
else {rotate(x,’r’); rotate(x,’l’);}
}
}
Node* findpos(int pos){
int done=0;
Node *p=root;
for (;;){
pushdown(p);
if (done+p->l->s+1==pos) return p;
if (done+p->l->s+1 else p=p->l;
}
}
void ins(int st,int n){
st=min(st,root->s-2);
Node *p=findpos(st),*q=findpos(st+1),*tmp;
Splay(p,root);
Splay(q,p);
for (int i=1;i<=n;i++){
tmp=newnode(a[i]);
if (i }
for (int i=1;i tmp=&sp[tot-i];
update(tmp);
}
q->l=tmp;
update(q);
update(p);
update(root);
}
void del(int l,int r){
r=min(r,root->s-2);
Node *p=findpos(l-1),*q=findpos(r+1);
Splay(p,root);
Splay(q,p);
q->l=null;
update(q);
update(p);
update(root);
}
void makesame(int l,int r,int C){
r=min(r,root->s-2);
Node *p=findpos(l-1),*q=findpos(r+1);
Splay(p,root);
Splay(q,p);
q->l->same=true;
q->l->sn=C;
update(q);
update(p);
update(root);
}
void reverse(int l,int r){
r=min(r,root->s-2);
Node *p=findpos(l-1),*q=findpos(r+1);
Splay(p,root);
Splay(q,p);
q->l->rev=true;
update(q);
update(p);
update(root);
}
int getsum(int l,int r){
r=min(r,root->s-2);
Node *p=findpos(l-1),*q=findpos(r+1);
Splay(p,root);
Splay(q,p);
pushdown(q->l);
return q->l->sum;
}
}Splay;
int main(){
freopen("sequence.in","r",stdin);
freopen("sequence.out","w",stdout);
Splay.init();
char op[100]; int n,m,pos;
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++) scanf("%d",&a[i]);
Splay.ins(1,n);
for (int i=1;i<=m;i++){
scanf("%s",&op);
switch (op[0]){
case ‘I’:
scanf("%d%d",&pos,&n);
for (int i=1;i<=n;i++) scanf("%d",&a[i]);
Splay.ins(pos+1,n);
break;
case ‘D’:
scanf("%d%d",&pos,&n);
Splay.del(pos+1,pos+n);
break;
case ‘M’:
if (op[2]==’K’){
int C;
scanf("%d%d%d",&pos,&n,&C);
Splay.makesame(pos+1,pos+n,C);
}
else{
Splay.pushdown(Splay.root);
printf("%dn",Splay.root->ms);
}
break;
case ‘R’:
scanf("%d%d",&pos,&n);
Splay.reverse(pos+1,pos+n);
break;
case ‘G’:
scanf("%d%d",&pos,&n);
printf("%dn",Splay.getsum(pos+1,pos+n));
break;
}
}
}