先给自己立一个flag
我希望上午能写完
再立一个flag
我希望下午能写完。
再立一个flag
我希望晚上能写完。。。
我终于A了。。。
6700+ms…(6728)
我成功地立了3个flag。。。
// It is made by XZZ
#include<cstdio>
#include<algorithm>
#include<ctime>
#include<cstdlib>
using namespace std;
#define rep(a,b,c) for(rg int a=b;a<=c;a++)
#define drep(a,b,c) for(rg int a=b;a>=c;a--)
#define erep(a,b) for(rg int a=fir[b];a;a=nxt[a])
#define il inline
#define rg register
#define vd void
#define mp make_pair
typedef long long ll;
typedef pair<int,int> pr;
il int gi(){
rg int x=,f=;rg char ch=getchar();
while(ch<''||ch>'')f=ch=='-'?-:f,ch=getchar();
while(ch>=''&&ch<='')x=x*+ch-'',ch=getchar();
return x*f;
}
#define Now t[now]
struct node{
int ls,rs,rand,size;
int data,sum,lmax,rmax,maxx;
bool rev,set;
int setnum;
il vd setdata(){data=setnum,sum=setnum*size,lmax=rmax=maxx=data>?sum:data,set=;}
}t[];
int stack[],top;
int root;
il int newnode(int data){
int now=stack[top];
Now.setnum=data,Now.setdata();
Now.rev=Now.set=;
Now.ls=Now.rs=;
Now.size=;
return stack[top--];
}
il vd down(int now){
if(Now.rev){
swap(Now.ls,Now.rs),swap(Now.lmax,Now.rmax);
t[Now.ls].rev^=,t[Now.rs].rev^=,Now.rev=;
}
if(Now.set){
Now.setdata();
t[Now.ls].set=,t[Now.ls].setnum=Now.setnum;
t[Now.rs].set=,t[Now.rs].setnum=Now.setnum;
}
}
il vd reset(int now){
if(Now.ls)down(Now.ls);
if(Now.rs)down(Now.rs);
Now.size=t[Now.ls].size+t[Now.rs].size+;
Now.sum=t[Now.ls].sum+t[Now.rs].sum+Now.data;
Now.lmax=t[Now.ls].sum+Now.data+max(t[Now.rs].lmax,);
Now.rmax=t[Now.rs].sum+Now.data+max(t[Now.ls].rmax,);
if(Now.ls)Now.lmax=max(Now.lmax,t[Now.ls].lmax);
if(Now.rs)Now.rmax=max(Now.rmax,t[Now.rs].rmax);
Now.maxx=max(t[Now.ls].rmax,)+max(t[Now.rs].lmax,)+Now.data;
if(Now.ls)Now.maxx=max(t[Now.ls].maxx,Now.maxx);
if(Now.rs)Now.maxx=max(Now.maxx,t[Now.rs].maxx);
}
il int merge(int a,int b){
if(!a||!b)return a|b;
if(t[a].rand<t[b].rand){down(a),t[a].rs=merge(t[a].rs,b),reset(a);return a;}
else {down(b),t[b].ls=merge(a,t[b].ls),reset(b);return b;}
}
il pr split(int now,int num){
if(!now)return mp(,);
down(now);
int ls=Now.ls,rs=Now.rs;
if(num==t[Now.ls].size){Now.ls=,reset(now);return mp(ls,now);}
if(num==t[Now.ls].size+){Now.rs=,reset(now);return mp(now,rs);}
if(num<t[Now.ls].size){
pr T=split(Now.ls,num);
Now.ls=T.second,reset(now);
return mp(T.first,now);
}else{
pr T=split(Now.rs,num-t[Now.ls].size-);
Now.rs=T.first,reset(now);
return mp(now,T.second);
}
}
il int build(int n){
int last;
int stk[n],tp=;
rep(i,,n){
int now=newnode(gi());last=;
while(tp&&t[stk[tp]].rand>Now.rand)reset(stk[tp]),last=stk[tp--];
if(tp)t[stk[tp]].rs=now;
Now.ls=last;
stk[++tp]=now;
}
while(tp)reset(stk[tp--]);
return stk[];
}
il vd rec(int now){
if(!now)return;
rec(Now.ls),rec(Now.rs),stack[++top]=now;
}
int main(){
int n=gi(),m=gi();char opt[];
rep(i,,)stack[-i+]=i;
top=;
srand();
rep(i,,)t[i].rand=i;
rep(i,,)swap(t[rand()%+].rand,t[rand()%+].rand);
root=build(n);
rep(i,,m){
scanf("%s",opt);
if(opt[]=='X')printf("%d\n",t[root].maxx);
else if(opt[]=='S'){
pr T=split(root,gi());
root=merge(merge(T.first,build(gi())),T.second);
}else{
pr T=split(root,gi()-),TT=split(T.second,gi());
if(opt[]=='K')t[TT.first].set=,t[TT.first].setnum=gi();
else if(opt[]=='V')t[TT.first].rev^=;
else if(opt[]=='T')printf("%d\n",t[TT.first].sum);
if(opt[]!='L')root=merge(T.first,merge(TT.first,TT.second));
else root=merge(T.first,TT.second),rec(TT.first);
}
}
return ;
}
/*
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
*/
解题报告请看这里
