RT,蒟蒻看了一边讨论区,感觉好像没什么问题,但是就是过不了样例,求助大佬们帮蒟蒻看看到底哪里出错了(
代码如下:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<random>
#include<vector>
using namespace std;
const int N=5e5+10;
const int INF=1e9;
vector<int> q;
int sta[N],cnt,a[N];
struct fhq{
int root,tot=1;
int ch[N][2],val[N],siz[N],sum[N],lms[N],rms[N],mms[N],lare[N],laco[N];
int newnode(int k){
int id=sta[cnt--];
lare[id]=ch[id][0]=ch[id][1]=0;lms[id]=rms[id]=max(0,k);
mms[id]=val[tot]=sum[id]=k;siz[id]=1;laco[id]=-INF;
return id;
}
void pushup(int pos){
siz[pos]=siz[ch[pos][0]]+siz[ch[pos][1]]+1;sum[pos]=sum[ch[pos][0]]+sum[ch[pos][1]];
lms[pos]=max(lms[ch[pos][0]],sum[ch[pos][0]]+lms[ch[pos][1]]);
rms[pos]=max(rms[ch[pos][1]],sum[ch[pos][1]]+rms[ch[pos][0]]);
mms[pos]=max({lms[pos],rms[pos],rms[ch[pos][0]]+lms[ch[pos][1]],mms[ch[pos][0]],mms[ch[pos][1]]});
}
void reverse(int x){
swap(ch[x][0],ch[x][1]);swap(lms[x],rms[x]);lare[x]^=1;
}
void cover(int x,int k){
sum[x]=siz[x]*k;lms[x]=rms[x]=max(0,sum[x]);mms[x]=max(k,sum[x]);laco[x]=k;
}
void pushdown(int x){
if(!x){
return;
}
if(lare[x]){
if(ch[x][0]){
reverse(ch[x][0]);
}
if(ch[x][1]){
reverse(ch[x][1]);
}
lare[x]=false;
}
if(laco[x]!=-INF){
if(ch[x][0]){
cover(ch[x][0],laco[x]);
}
if(ch[x][1]){
cover(ch[x][1],laco[x]);
}
laco[x]=-INF;
}
}
void split(int pos,int k,int &x,int &y){
if(!pos){
x=y=0;
return;
}
pushdown(pos);
if(siz[ch[pos][0]]+1<=k){
x=pos;
split(ch[pos][1],k-siz[ch[pos][0]]-1,ch[x][1],y);
}
else{
y=pos;
split(ch[pos][0],k,x,ch[y][0]);
}
pushup(pos);
}
int merge(int x,int y){
if(!x||!y){
return x+y;
}
if(90000008%(siz[x]+siz[y])<siz[x]){
pushdown(x);
ch[x][1]=merge(ch[x][1],y);
pushup(x);
return x;
}
else{
pushdown(y);
ch[y][0]=merge(x,ch[y][0]);
pushup(y);
return y;
}
}
void era(int x){
if(!x){
return;
}
sta[++cnt]=x;
if(ch[x][0]){
era(ch[x][0]);
}
if(ch[x][1]){
era(ch[x][1]);
}
}
int build(int l,int r){
if(l==r){
return newnode(a[l]);
}
int mid=(l+r)>>1;
return merge(build(l,mid),build(mid+1,r));
}
}tr;
int n,m;
string s;
int main(){
scanf("%d%d",&n,&m);
int x,y,k;
for(int i=1;i<=500001;i++){
sta[++cnt]=i;
}
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
tr.root=tr.merge(tr.root,tr.build(1,n));
while(m--){
cin>>s;
// cout<<"s: "<<s<<endl;
if(s=="INSERT"){
scanf("%d%d",&x,&y);
for(int i=1;i<=y;i++){
scanf("%d",&a[i]);
}
int u,v;
tr.split(tr.root,x,u,v);
u=tr.merge(u,tr.build(1,y));
tr.root=tr.merge(u,v);
}
else if(s=="DELETE"){
scanf("%d%d",&x,&y);
int u,v,w;
tr.split(tr.root,x-1,u,v);
tr.split(v,y,v,w);
tr.era(v);
tr.root=tr.merge(u,w);
}
else if(s=="MAKE-SAME"){
scanf("%d%d%d",&x,&y,&k);
int u,v,w;
tr.split(tr.root,x-1,u,v);
tr.split(v,y,v,w);
tr.cover(v,k);
v=tr.merge(u,v);
tr.root=tr.merge(v,w);
}
else if(s=="REVERSE"){
scanf("%d%d",&x,&y);
int u,v,w;
tr.split(tr.root,x-1,u,v);
tr.split(v,y,v,w);
tr.reverse(v);
v=tr.merge(v,w);
tr.root=tr.merge(u,v);
}
else if(s=="GET-SUM"){
int u,v,w;
scanf("%d%d",&x,&y);
cout<<"CASE 5: "<<endl;
tr.split(tr.root,x-1,u,v);
tr.split(v,y,v,w);
printf("%d\n",tr.sum[v]);
// cout<<"????????????????"<<endl;
v=tr.merge(u,v);
tr.root=tr.merge(v,w);
}
else{
int u,v,w;
cout<<"CASE 6: "<<endl;
printf("%d\n",tr.mms[tr.root]);
}
}
}