splay入门题。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cmath>
#include<algorithm>
#include<iomanip>
#include<queue>
#include<set>
using namespace std;
#define LL long long
#define FILE "dealing"
#define mid ((l+r)>>1)
#define pii pair<int,int>
#define up(i,j,n) for(int i=(j);i<=(n);i++)
LL read(){
LL x=0,f=1,ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return f*x;
}
const int maxn=605000,inf=1000000000;
int n,m;
int a[maxn];
int fa[maxn],c[maxn][2],sum[maxn],lm[maxn],rm[maxn],Max[maxn],rev[maxn],f[maxn],q[maxn],siz[maxn],val[maxn],h[maxn],root,head=1,tail=0;
void updata(int x){//updata sum siz maxse
if(!x)return;
siz[x]=siz[c[x][0]]+siz[c[x][1]]+1;
h[x]=max(h[c[x][0]],h[c[x][1]]);h[x]=max(h[x],val[x]);
sum[x]=sum[c[x][0]]+sum[c[x][1]]+val[x];
lm[x]=max(lm[c[x][0]],sum[c[x][0]]+val[x]+lm[c[x][1]]);
rm[x]=max(rm[c[x][1]],sum[c[x][1]]+val[x]+rm[c[x][0]]);
Max[x]=max(Max[c[x][0]],Max[c[x][1]]);
Max[x]=max(Max[x],rm[c[x][0]]+val[x]+lm[c[x][1]]);
}
inline void add(int x){q[++tail]=x;if(tail==600000)tail=0;}
inline int pop(){if(head==600001)head=1;return q[head++];}
void change(int x,int c){
if(!x)return;
val[x]=f[x]=h[x]=c;
Max[x]=lm[x]=rm[x]=max(0,siz[x]*c);
sum[x]=siz[x]*c;
}
void revv(int x){
if(!x)return;rev[x]^=1;swap(lm[x],rm[x]);swap(c[x][0],c[x][1]);
}
void pushdown(int x){
if(!x)return;
if(rev[x])rev[x]=0,revv(c[x][0]),revv(c[x][1]);
if(f[x]!=inf)change(c[x][0],f[x]),change(c[x][1],f[x]),f[x]=inf;
}
void rotate(int x){
if(!x)return;
int y=fa[x],z=fa[y],d=c[y][1]==x;
fa[y]=x,fa[x]=z;if(c[x][d^1])fa[c[x][d^1]]=y;
c[y][d]=c[x][d^1];c[x][d^1]=y;
if(z)c[z][c[z][1]==y]=x;
updata(y),updata(x);
}
int p[maxn],top=0;
void splay(int x,int S){
if(!x)return;
for(int i=x;i;i=fa[i])p[++top]=i;
while(top)pushdown(p[top--]);
while(fa[x]!=S){
int y=fa[x],z=fa[y];
if(z!=S){
if((c[y][1]==x)^(c[z][1]==y))rotate(x);
else rotate(y);
}
rotate(x);
}
if(!S)root=x;
}
int find(int k){//返回大于k个数的splay节点
int x=root;
pushdown(x);
while(siz[c[x][0]]!=k){
pushdown(x);
if(siz[c[x][0]]>k)x=c[x][0];
else k=k-1-siz[c[x][0]],x=c[x][1];
}
splay(x,0);
return x;
}
int t[4000000];
void build(int& x,int Fa,int l,int r){
if(l>r)return void(x=0);
if(!x)x=pop();
lm[x]=rm[x]=Max[x]=max(0,h[x]=sum[x]=val[x]=t[mid]);
fa[x]=Fa;siz[x]=1;f[x]=inf;
if(l==r)return;
build(c[x][0],x,l,mid-1);
build(c[x][1],x,mid+1,r);
updata(x);
}
void insert(int pos,int cnt){
int x=find(pos),y=find(pos+1);
splay(x,0);splay(y,root);
build(c[y][0],y,1,cnt);
updata(y),updata(x);
}
void Det(int x){
if(!x)return;
Det(c[x][0]);Det(c[x][1]);
fa[x]=c[x][0]=c[x][1]=sum[x]=lm[x]=rm[x]=Max[x]=rev[x]=siz[x]=val[x]=0;
f[x]=inf;h[x]=-inf;
add(x);
}
void delet(int pos,int cnt){
int x=find(pos-1),y=find(pos+cnt);
splay(x,0);splay(y,root);
Det(c[y][0]);c[y][0]=0;
updata(y),updata(x);
}
void Change(int pos,int cnt,int w){
int x=find(pos-1),y=find(pos+cnt);
splay(x,0);splay(y,root);
change(c[y][0],w);
updata(y),updata(x);
}
void reverse(int pos,int cnt){
int x=find(pos-1),y=find(pos+cnt);
splay(x,0);splay(y,root);
revv(c[y][0]);updata(y),updata(x);
}
void getsum(int pos,int cnt){
int x=find(pos-1),y=find(pos+cnt);
splay(x,0);splay(y,root);
printf("%d
",sum[c[y][0]]);
updata(y),updata(x);
}
void maxseg(){
int x=find(0),y=find(siz[root]-1);
splay(x,0);splay(y,root);
printf("%d
",(!Max[c[y][0]])?h[c[y][0]]:Max[c[y][0]]);
}
int main(){
//freopen("dealing.in","r",stdin);
//freopen("dealing.out","w",stdout);
n=read(),m=read();
memset(val,-10,sizeof(val));f[0]=inf;
up(i,1,600000)add(i);
t[1]=-inf,t[2]=inf;
build(root,0,1,2);h[0]=-inf;
up(i,1,n)t[i]=a[i]=read();
insert(0,n);
char s[10];int pos,cnt,w;
up(i,1,m){
scanf("%s",s);
if(s[0]=='I'){
pos=read(),cnt=read();
up(j,1,cnt)t[j]=read();
if(!cnt)continue;
insert(pos,cnt);
}
if(s[0]=='D'){
pos=read(),cnt=read();
if(!cnt)continue;
delet(pos,cnt);
}
if(s[2]=='K'){
pos=read(),cnt=read(),w=read();
if(!cnt)continue;
Change(pos,cnt,w);
}
if(s[0]=='R'){
pos=read(),cnt=read();
if(!cnt)continue;
reverse(pos,cnt);
}
if(s[0]=='G'){
pos=read(),cnt=read();
if(!cnt){printf("0
");continue;}
getsum(pos,cnt);
}
if(s[2]=='X')maxseg();
}
return 0;
}