1500: [NOI2005]维修数列
Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 3087 Solved: 920
[Submit][Status][Discuss]
Description
Input
输入文件的第1行包含两个数N和M，N表示初始时数列中数的个数，M表示要进行的操作数目。 第2行包含N个数字，描述初始时的数列。 以下M行，每行一条命令，格式参见问题描述中的表格。
Output
对于输入数据中的GET-SUM和MAX-SUM操作，向输出文件依次打印结果，每个答案（数字）占一行。
Sample Input
9 8
2 -6 3 5 1 -5 -3 6 3
GET-SUM 5 4
MAX-SUM
INSERT 8 3 -5 7 2
DELETE 12 1
MAKE-SAME 3 3 2
REVERSE 3 6
GET-SUM 5 4
MAX-SUM
Sample Output
-1
10
1
10
HINT
Splay解决数列维护。
推荐：用伸展树解决数列维护问题
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<functional>
#include<iostream>
#include<cstdlib>
#include<cmath>
using namespace std;
#define MAXN (500000+10)
#define MAXM (20000+10)
#define INF (0xfffffff)
struct node
{
int value,MaxL,MaxR,MaxM,sum,size;
bool rev,same;
node *ch[2],*pre;
node(node *f,int _value,int _MaxL,int _MaxR,int _MaxM,int _sum,int _size):value(_value),MaxL(_MaxL),MaxR(_MaxR),MaxM(_MaxM),sum(_sum),size(_size){rev=same=0,pre=f,ch[0]=ch[1]=NULL;}
node(){rev=same=0;}
int l_siz(){if (ch[0]) return ch[0]->size;else return 0;}
// int r_siz(){return (ch[1])?ch[1]->size:0;}
friend void pushdown(node *x)
{
if (x)
{
if (x->rev)
{
x->rev=0;
if (x->ch[0]) x->ch[0]->rev^=1;
if (x->ch[1]) x->ch[1]->rev^=1;
swap(x->ch[0],x->ch[1]);
swap(x->MaxL,x->MaxR);
}
if (x->same)
{
x->same=0;
if (x->ch[0]) {x->ch[0]->same=1;x->ch[0]->value=x->value;x->ch[0]->sum=x->value*x->ch[0]->size;x->ch[0]->MaxL=x->ch[0]->MaxR=x->ch[0]->MaxM=max(x->value,x->ch[0]->sum);}
if (x->ch[1]) {x->ch[1]->same=1;x->ch[1]->value=x->value;x->ch[1]->sum=x->value*x->ch[1]->size;x->ch[1]->MaxL=x->ch[1]->MaxR=x->ch[1]->MaxM=max(x->value,x->ch[1]->sum);}
}
}
}
friend void update(node *x)
{
if (x)
{
pushdown(x->ch[0]);pushdown(x->ch[1]); //由于有坑爹的rev操作，必须先down.
x->size=((x->ch[0])?x->ch[0]->size:0)+((x->ch[1])?x->ch[1]->size:0)+1;
x->sum=((x->ch[0])?x->ch[0]->sum:0)+((x->ch[1])?x->ch[1]->sum:0)+x->value;
x->MaxL=max(((x->ch[0])?x->ch[0]->MaxL:x->value),((x->ch[0])?x->ch[0]->sum:0)+x->value+max(0,((x->ch[1])?x->ch[1]->MaxL:0)));
x->MaxR=max(((x->ch[1])?x->ch[1]->MaxR:x->value),((x->ch[1])?x->ch[1]->sum:0)+x->value+max(0,((x->ch[0])?x->ch[0]->MaxR:0)));
// cout<<((x->ch[1])?x->ch[1]->MaxR:x->value)<<' '<<+max(0,(((x->ch[0])?x->ch[0]->MaxR:0)))<<endl;
x->MaxM=max(max(((x->ch[0])?x->ch[0]->MaxM:x->value),((x->ch[1])?x->ch[1]->MaxM:x->value)),((x->ch[0])?max(x->ch[0]->MaxR,0):0)+((x->ch[1])?max(x->ch[1]->MaxL,0):0)+x->value);
}
}
};
node *q[MAXN];
int q_siz=0;
int n,m,a[MAXN];
node* newnode(node *f,int value,int MaxL,int MaxR,int MaxM,int sum,int size)
{
if (q_siz)
{
q[q_siz]->value=value;
q[q_siz]->MaxL=MaxL;
q[q_siz]->MaxR=MaxR;
q[q_siz]->MaxM=MaxM;
q[q_siz]->sum=sum;
q[q_siz]->size=size;
q[q_siz]->rev=q[q_siz]->same=0;q[q_siz]->pre=f;q[q_siz]->ch[0]=q[q_siz]->ch[1]=NULL;
return q[q_siz--];
}
node *x=new node(f,value,MaxL,MaxR,MaxM,sum,size);
return x;
}
node* newnode()
{
if (q_siz) return q[q_siz--];
node *x=new node();
return x;
}
void addnode(node *x)
{
q[++q_siz]=x;
*x=node();
}
struct Splay
{
node *root;
Splay()
{
root=newnode(NULL,-INF,-INF,-INF,-INF,0,2);
root->ch[0]=newnode(root,-INF,-INF,-INF,-INF,0,1);
}
void Print(node *x)
{
if (x->ch[0]) {cout<<"(",Print(x->ch[0]),cout<<")-";}
cout<<x->same;
if (x->ch[1]) cout<<"-(",Print(x->ch[1]),cout<<")";
}
void rotate(node *x,int c) //0左旋 1右旋
{
node *y=x->pre;
pushdown(y),pushdown(x);
y->ch[!c]=x->ch[c];
if (x->ch[c]!=NULL) x->ch[c]->pre=y;
x->pre=y->pre;
if (y->pre!=NULL)
{
if (y->pre->ch[0]==y) y->pre->ch[0]=x;
else y->pre->ch[1]=x;
}
x->ch[c]=y;y->pre=x;
if (y==root) root=x;
update(y);
}
void splay(node *x,node *f)
{
for(pushdown(x);x->pre!=f;)
{
if (x->pre->pre==f)
{
if (x->pre->ch[0]==x) rotate(x,1);
else rotate(x,0);
}
else
{
node *y=x->pre,*z=y->pre;
pushdown(z);pushdown(y);pushdown(x); //rev改变树结构
if (y->ch[0]==x&&z->ch[0]==y) rotate(y,1),rotate(x,1);
else if (y->ch[1]==x&&z->ch[1]==y) rotate(y,0),rotate(x,0);
else if (y->ch[0]==x&&z->ch[1]==y) rotate(x,1),rotate(x,0);
else if (y->ch[1]==x&&z->ch[0]==y) rotate(x,0),rotate(x,1);
}
update(x);
//Print(root);cout<<endl;
}
}
node* find_kth(node *x,int k)
{
pushdown(x); //确保x正确
if (x->l_siz()>=k) return find_kth(x->ch[0],k);
if (x->l_siz()+1==k) return x;
else return find_kth(x->ch[1],k-x->l_siz()-1);
}
void build(node *f,node *x,int l,int r)
{
if (l>r) return;
int m=(l+r)>>1;
*x=node(f,a[m],a[l],a[r],a[m],a[m],1);
if (l<m) build(x,x->ch[0]=newnode(),l,m-1);
if (m<r) build(x,x->ch[1]=newnode(),m+1,r);
if (l<r) update(x);
}
void del(node *x)
{
if (x->ch[0]) del(x->ch[0]);
if (x->ch[1]) del(x->ch[1]);
addnode(x);
}
void insert(int pos,int tot)
{
splay(find_kth(root,pos+1),NULL);
splay(find_kth(root,pos+2),root);
root->ch[1]->ch[0]=newnode();
build(root->ch[1],root->ch[1]->ch[0],1,tot);
update(root->ch[1]);update(root);
}
void delet(int pos,int tot)
{
splay(find_kth(root,pos),NULL);
splay(find_kth(root,pos+1+tot),root);
//Print(root);
del(root->ch[1]->ch[0]);
root->ch[1]->ch[0]=NULL;
update(root->ch[1]);update(root);
}
void reverse(int pos,int tot)
{
splay(find_kth(root,pos),NULL);
splay(find_kth(root,pos+1+tot),root);
root->ch[1]->ch[0]->rev^=1;
update(root->ch[1]);update(root);
}
void make_same(int pos,int tot,int c)
{
splay(find_kth(root,pos),NULL);
splay(find_kth(root,pos+1+tot),root);
node *x=root->ch[1]->ch[0];
x->same=1;
x->value=c;
x->sum=c*x->size;
x->MaxL=x->MaxR=x->MaxM=max(x->value,x->sum);
update(root->ch[1]);update(root);
}
void get_sum(int pos,int tot)
{
if (tot==0)
{
printf("0n");
return;
}
splay(find_kth(root,pos),NULL);
//Print(root);cout<<endl;
splay(find_kth(root,pos+1+tot),root);
//Print(root);cout<<endl;
node *x=root->ch[1]->ch[0];
printf("%dn",x->sum);
}
void max_sum()
{
splay(find_kth(root,1),NULL);
splay(find_kth(root,root->size),root);
printf("%dn",root->ch[1]->ch[0]->MaxM);
}
}S;
int main()
{
// freopen("bzoj1500.in","r",stdin);
cin>>n>>m;
for (int i=1;i<=n;i++) cin>>a[i];
S.insert(0,n);
//S.Print(S.root);cout<<endl;
for (int i=1;i<=m;i++)
{
// cout<<i<<':';
char s[10];
scanf("%s",s);
switch (s[2])
{
case'S':
{
int pos,tot;
scanf("%d%d",&pos,&tot);
for (int i=1;i<=tot;i++) scanf("%d",&a[i]);
S.insert(pos,tot);
break;
}
case'L':
{
int pos,tot;
scanf("%d%d",&pos,&tot);
S.delet(pos,tot);
break;
}
case'K':
{
int pos,tot,c;
scanf("%d%d%d",&pos,&tot,&c);
S.make_same(pos,tot,c);
break;
}
case'V':
{
int pos,tot;
scanf("%d%d",&pos,&tot);
S.reverse(pos,tot);
break;
}
case'T':
{
int pos,tot;
scanf("%d%d",&pos,&tot);
S.get_sum(pos,tot);
break;
}
case'X':
{
S.max_sum();
break;
}
}
//S.Print(S.root);cout<<endl;
}
return 0;
}
第XXXX届NOI期间，为了加强各省选手之间的交流，组委会决定组织一场省际电子竞技大赛，每一个省的代表队由n名选手组成，比赛的项目是老少咸宜的网络游戏泡泡堂。每一场比赛前，对阵双方的教练向组委会提交一份参赛选手的名单，决定了选手上场的顺序，一经确定，不得修改。比赛中，双方的一号选手，二号选手……，n号选手捉对厮杀，共进行n场比赛。每胜一场比赛得2分，平一场得1分，输一场不得分。最终将双方的单场得分相加得出总分，总分高的队伍晋级(总分相同抽签决定)。