| 记录编号 |
90969 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
[NOI 2005]维护数列 |
最终得分 |
100 |
| 用户昵称 |
 cstdio |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
3.486 s |
| 提交时间 |
2014-03-11 13:19:07 |
内存使用 |
11.76 MiB |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int SIZEN=3000010,INF=0x7fffffff/2;
class SPLAYTREE{
public:
class NODE{
public:
int key,sum,smx,lmx,rmx,size;
bool rev,same;//是否翻转,是否全一样
NODE *lc,*rc,*f;//两个儿子和父亲
NODE(int k){key=sum=smx=lmx=rmx=k,size=1,rev=same=0;}
NODE(){NODE(0);}
}*Nil,*left,*right,*Root;
NODE* newNODE(int key){
NODE *T=new NODE(key);
T->lc=T->rc=T->f=Nil;
return T;
}
SPLAYTREE(){
Nil=new NODE(-INF);
Nil->lc=Nil->rc=Nil->f=Nil;
Nil->sum=Nil->size=0;//建立虚拟空节点
left=new NODE(-INF),right=new NODE(-INF);
left->lc=left->rc=left->f=Nil;
right->lc=right->rc=right->f=Nil;
left->sum=right->sum=0;
left->rc=right,right->f=left;
(left->size)++;Root=left;//建立边界节点
}
void pushdown(NODE *T){
if(T->rev){
swap(T->lc,T->rc);
swap(T->lmx,T->rmx);
T->lc->rev^=1,T->rc->rev^=1;
T->rev=0;
}
if(T->same){
T->same=0;T->lc->same=T->rc->same=1;
T->lc->key=T->rc->key=T->key;
T->lmx=T->rmx=T->sum=T->smx=T->key*T->size;
if(T->key<0) T->lmx=T->rmx=T->smx=T->key;//此时的最大值是只取一项
}
}
void update(NODE *T){
T->size=T->lc->size+T->rc->size+1;
T->sum=T->lc->sum+T->rc->sum+T->key;
T->lmx=max(T->lc->lmx,T->lc->sum+T->key+max(0,T->rc->lmx));
T->rmx=max(T->rc->rmx,T->rc->sum+T->key+max(0,T->lc->rmx));
T->smx=max(T->lc->smx,T->rc->smx);//情况①:在左右子树中
T->smx=max(T->smx,T->key+max(T->lc->rmx,0)+max(T->rc->lmx,0));//情况②:这个点向左右延伸或不延伸
}
void zig(NODE *T){//右旋
NODE *P=T->f,*rson=T->rc;
pushdown(P->rc);pushdown(T->lc);pushdown(T->rc);//旋转之前先下压标记
if(Root==P) Root=T;//修改在更前的父结点处的悬挂方式
else (P->f->lc==P)?(P->f->lc=T):(P->f->rc=T);
T->f=P->f;P->f=T;P->lc=rson;T->rc=rson->f=P;//修改三个子节点的悬挂方式
update(P);
}
void zag(NODE *T){//左旋
NODE *P=T->f,*lson=T->lc;
pushdown(P->lc);pushdown(T->lc);pushdown(T->rc);
if(Root==P) Root=T;
else (P->f->lc==P)?(P->f->lc=T):(P->f->rc=T);
T->f=P->f;P->f=T;P->rc=lson;T->lc=lson->f=P;
update(P);
}
void splay(NODE *ANC,NODE *t){//把t旋转到ANC
pushdown(t);//因为后面要改悬挂点,因此在这里push下去
if(t==ANC){
update(t);
return;
}
bool reach=false;
while(!reach){
NODE *P=t->f;
if(P==ANC) (P->lc==t)?zig(t):zag(t),reach=true;
else{
if(P->f==ANC) reach=true;
if(P->f->lc==P) (P->lc==t)?zig(P):zag(t),zig(t);
else (P->rc==t)?zag(P):zig(t),zag(t);
}
}
update(t);
}
void select(NODE *ANC,int k){//将ANC子树中的第k项提到ANC的位置
NODE *t=ANC;
while(true){
pushdown(t);
if(k==t->lc->size+1){
splay(ANC,t);
return;
}
if(k<=t->lc->size) t=t->lc;
else k-=t->lc->size+1,t=t->rc;
}
}
void Insert(int pos,int a[],int k){//在pos后插入a[1]~a[k]
select(Root,pos+1);select(Root->rc,1);
NODE *t=newNODE(a[1]),*p=t,*q=t;
for(int i=2;i<=k;i++) t=newNODE(a[i]),t->f=p,p->rc=t,p=t;
Root->rc->lc=q;q->f=Root->rc;
splay(Root,p);
}
void Delete(int pos,int tot){
select(Root,pos),select(Root->rc,tot+1);
Root->rc->lc=Nil;
splay(Root,Root->rc);
}
void Reverse(int pos,int tot){
select(Root,pos),select(Root->rc,tot+1);
Root->rc->lc->rev^=1;splay(Root,Root->rc->lc);
}
void Makesame(int pos,int tot,int key){
select(Root,pos);select(Root->rc,tot+1);
Root->rc->lc->key=key;Root->rc->lc->same=true;
splay(Root,Root->rc->lc);
}
int Getsum(int pos,int tot){
select(Root,pos);select(Root->rc,tot+1);
return Root->rc->lc->sum;
}
int Maxsum(void){return Root->smx;}
};
SPLAYTREE tree;
int N,M;
int a[SIZEN]={0};
void init(void){
scanf("%d%d",&N,&M);
for(int i=1;i<=N;i++) scanf("%d",&a[i]);
tree.Insert(0,a,N);
}
void work(void){
string cmd;
int pos,tot,x;
while(M--){
cin>>cmd;
if(cmd=="MAX-SUM"){
printf("%d\n",tree.Maxsum());
continue;
}
scanf("%d%d",&pos,&tot);
if(cmd=="INSERT"){
for(int i=1;i<=tot;i++) scanf("%d",&a[i]);
tree.Insert(pos,a,tot);
}
else if(cmd=="DELETE") tree.Delete(pos,tot);
else if(cmd=="MAKE-SAME"){
scanf("%d",&x);
tree.Makesame(pos,tot,x);
}
else if(cmd=="REVERSE") tree.Reverse(pos,tot);
else if(cmd=="GET-SUM") printf("%d\n",tree.Getsum(pos,tot));
}
}
int main(){
freopen("seq2005.in","r",stdin);
freopen("seq2005.out","w",stdout);
init();
work();
return 0;
}