模板题
之前还写了点铺垫题
bzoj3223 教你如何reverse
bzoj1507 教你如何维护序列
bzoj1269 教你如何维护序列&reverse
然后再做这个题就好多啦
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define N 500005
using namespace std;
inline int read(){
int ret=0;char ch=getchar();
bool flag=0;
while (ch<'0' || ch>'9'){
flag=ch=='-';
ch=getchar();
}
while ('0'<=ch && ch<='9'){
ret=ret*10-48+ch;
ch=getchar();
}
return flag?-ret:ret;
}
struct Splay{
#define ls(a) (t[a].c[0])
#define rs(a) (t[a].c[1])
int root;
int q[4000006],qh,qt;
struct SPLAYnode{
int c[2],fa,size;
int data,sum,lsum,rsum,maxsum;
bool rev,tag;int num;
} t[N];
int newnode(){
int ret=q[++qh];
t[ret].fa=ls(ret)=rs(ret)=t[ret].rev=t[ret].tag=0;
t[ret].size=1;
return ret;
}
void load(){
qh=qt=0;
ls(0)=rs(0)=t[0].rev=t[0].tag=t[0].sum=t[0].lsum=t[0].rsum=t[0].maxsum=0;
t[1].data=-1001;
for (int i=1;i<=500000;++i) q[++qt]=i;
t[root=newnode()].size=1;
}
void renew(int x){
t[x].size=t[ls(x)].size+t[rs(x)].size+1;
t[x].sum=t[ls(x)].sum+t[rs(x)].sum+t[x].data;
t[x].lsum=t[ls(x)].sum+t[x].data+max(t[rs(x)].lsum,0);
if (ls(x)) t[x].lsum=max(t[x].lsum,t[ls(x)].lsum);
t[x].rsum=t[rs(x)].sum+t[x].data+max(t[ls(x)].rsum,0);
if (rs(x)) t[x].rsum=max(t[x].rsum,t[rs(x)].rsum);
t[x].maxsum=t[x].data+max(t[ls(x)].rsum,0)+max(t[rs(x)].lsum,0);
if (ls(x)) t[x].maxsum=max(t[x].maxsum,t[ls(x)].maxsum);
if (rs(x)) t[x].maxsum=max(t[x].maxsum,t[rs(x)].maxsum);
}
int f(int x){return (ls(t[x].fa)!=x)*(1-2*(rs(t[x].fa)!=x));}
void fill(int x,int value){
t[x].tag=1;t[x].num=value;
t[x].data=value;
t[x].sum=value*t[x].size;
t[x].lsum=t[x].rsum=t[x].maxsum=max(t[x].sum,value);
}
void rever(int x){
t[x].rev^=1;
swap(ls(x),rs(x));
swap(t[x].lsum,t[x].rsum);
}
void PushDown(int x){
if (t[x].rev){
t[x].rev^=1;
rever(ls(x));
rever(rs(x));
}
if (t[x].tag){
if (ls(x)) fill(ls(x),t[x].num);
if (rs(x)) fill(rs(x),t[x].num);
t[x].tag=0;
}
}
void rotate(int x){
int y=t[x].fa,z=t[y].fa,k=f(x),fz=f(y);
if (fz>=0) t[z].c[fz]=x;
t[y].c[k]=t[x].c[k^1];t[x].c[k^1]=y;
t[t[y].c[k]].fa=y;t[x].fa=z;t[y].fa=x;
renew(y);renew(x);
}
int stack[N],top;
void splay(int x){
top=0;stack[top++]=x;
for (int i=x;f(i)>=0;i=t[i].fa) stack[top++]=t[i].fa;
while (top) PushDown(stack[--top]);
for (root=x;f(x)>=0;rotate(x))
if (f(t[x].fa)==f(x)) rotate(t[x].fa);
else if (f(t[x].fa)>=0) rotate(x);
}
int findk(int k){
int x=root;
for (PushDown(x);t[ls(x)].size+1!=k;PushDown(x))
if (t[ls(x)].size+1<k){
k-=t[ls(x)].size+1;
x=rs(x);
}
else x=ls(x);
return x;
}
void reverse(int l,int r){
l=findk(l);r=findk(r);
splay(l);int tmpl=ls(l);ls(l)=0;renew(l);
splay(r);int tmpr=rs(r);rs(r)=0;renew(r);
rever(r);
splay(l);t[rs(l)=tmpr].fa=l;renew(l);
splay(r);t[ls(r)=tmpl].fa=r;renew(r);
}
void ins(int cnt){
int now=0;
while (cnt--){
int tmp=newnode();
t[now].fa=tmp;
t[tmp].data=read();
ls(tmp)=now;
renew(now=tmp);
}
PushDown(root);
int tmp=rs(root);
PushDown(tmp);
rs(now)=tmp;t[tmp].fa=now;renew(now);
rs(root)=now;t[now].fa=root;renew(root);
}
void release(int x){
if (!x) return;
q[++qt]=x;
release(ls(x));
release(rs(x));
}
void del(int l,int r){
l=findk(l);r=findk(r);
splay(r);int tmp=rs(r);rs(r)=0;renew(r);
splay(l);swap(rs(l),tmp);t[rs(l)].fa=l;renew(l);
release(tmp);
}
void update(int l,int r){
l=findk(l);r=findk(r);
splay(l);int tmpl=ls(l);ls(l)=0;renew(l);
splay(r);int tmpr=rs(r);rs(r)=0;renew(r);
fill(r,read());
splay(l);t[ls(l)=tmpl].fa=l;renew(l);
splay(r);t[rs(r)=tmpr].fa=r;renew(r);
}
void getsum(int l,int r){
if (l>r){puts("0");return;}
l=findk(l);r=findk(r);
splay(l);int tmpl=ls(l);ls(l)=0;renew(l);
splay(r);int tmpr=rs(r);rs(r)=0;renew(r);
printf("%d
",t[r].sum);
splay(l);t[ls(l)=tmpl].fa=l;renew(l);
splay(r);t[rs(r)=tmpr].fa=r;renew(r);
}
} s;
int main(){
s.load();int now=1,tmp=read(),Q=read();
s.ins(tmp);
while (Q--){
char op=getchar();
while (!isalpha(op)) op=getchar();
char op2=getchar();op2=getchar();
if (op=='M'&&op2=='X'){
printf("%d
",s.t[s.root].maxsum);
for (int i=0;i<4;++i) getchar();
continue;
}
s.splay(s.findk(now=read()+1));
if (op=='M') s.update(now,now+read()-1);
else if (op=='R') s.reverse(now,now+read()-1);
else if (op=='I') s.ins(read());
else if (op=='D') s.del(now-1,now+read()-1);
else if (op=='G') s.getsum(now,now+read()-1);
}
return 0;
}
到现在刚学splay，还是太弱了TAT