思路
超级恶心的pushdown
昏天黑地的调
让我想起了我那前几个月的线段树2
错误
这恶心的一道题终于过了
太多错误，简直说不过来
pushup
pushdown
主要就是这俩不太清晰，乱pushdown
其他的写的还没啥毛病(能看出来)
代码
#include <iostream>
#include <cstdio>
#include <stack>
#include <cstring>
#include <algorithm>
#define FOR(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
const int maxn=5e5+7;
const int inf=0x3f3f3f3f;
typedef long long ll;
int read() {
int x=0,f=1;char s=getchar();
for(; s>'9'||s<'0'; s=getchar()) if(s=='-') f=-1;
for(; s>='0'&&s<='9'; s=getchar()) x=x*10+s-'0';
return x*f;
}
int n,m,rt,cnt;
int init[maxn];
stack<int> q;//回收废弃数组
struct node
{
int ch[2],val,pri,size;
int sum,ma,lma,rma;
int lazy_fanzhuan,lazy_chenzhen;
void clear()
{
ch[1]=ch[2]=val=pri=size=sum=lazy_fanzhuan=lma=rma=0;
ma=-inf;
lazy_chenzhen=inf;
}
void iit(int x)
{
ma=sum=val=init[x];
lma=rma=max(init[x],0);
size=1;
pri=x;
}
}e[maxn];
void pushup(int a)
{
int ls=e[a].ch[0],rs=e[a].ch[1];
//sum
e[a].sum=e[ls].sum+e[rs].sum+e[a].val;
//size
e[a].size=e[ls].size+e[rs].size+1;
//ma
e[a].ma=max(max(e[ls].ma,e[rs].ma),e[ls].rma+e[a].val+e[rs].lma);
//lma
e[a].lma=max(e[ls].lma,e[ls].sum+e[a].val+e[rs].lma);
//rma
e[a].rma=max(e[rs].rma,e[rs].sum+e[a].val+e[ls].rma);
}
void down_1(int a,int ad)
{
//@修改自身
e[a].lazy_chenzhen=ad;
e[a].val=e[a].lazy_chenzhen;
e[a].sum=e[a].size*e[a].val;
e[a].ma=max(e[a].sum , e[a].val);
e[a].lma=e[a].rma=max(e[a].sum , 0);
}
void down_2(int a)
{
//sum和ma是不变的
swap(e[a].lma,e[a].rma);
swap(e[a].ch[0],e[a].ch[1]);
e[a].lazy_fanzhuan^=1;
}
void pushdown(int a)
{
if(!a) return;
int ls=e[a].ch[0],rs=e[a].ch[1];
if(e[a].lazy_fanzhuan)
{
//sum和ma是不变的
if(ls) down_2(ls);
if(rs) down_2(rs);
}
if(e[a].lazy_chenzhen!=inf)
{
if(ls) down_1(ls,e[a].lazy_chenzhen);
if(rs) down_1(rs,e[a].lazy_chenzhen);
}
e[a].lazy_chenzhen=inf;
e[a].lazy_fanzhuan=0;
}
int merge(int x,int y)
{
pushdown(x),pushdown(y);
if(!x || !y) return x+y;
if(e[x].pri<e[y].pri)
{
e[x].ch[1]=merge(e[x].ch[1],y);
pushup(x);return x;
} else
{
e[y].ch[0]=merge(x,e[y].ch[0]);
pushup(y);return y;
}
}
void split(int now,int k,int &x,int &y)
{
if(!now) x=y=0,e[now].clear();
else
{
pushdown(now);
if(e[e[now].ch[0]].size+1<=k)
x=now,split(e[now].ch[1],k-e[e[now].ch[0]].size-1,e[x].ch[1],y);
else
y=now,split(e[now].ch[0],k,x,e[y].ch[0]);
pushup(now);
}
}
int GET()
{
if(!q.empty())
{
int tmp=q.top();
q.pop();
return tmp;
} else
return ++cnt;
}
int build(int l,int r)
{
if(l>r) return 0;
int mid=(l+r)>>1,p=GET();
e[p].clear();
e[p].iit(mid);
e[p].ch[0]=build(l,mid-1);
e[p].ch[1]=build(mid+1,r);
pushup(p);
return p;
}
void dfs(int now)
{
if(!now) return;
dfs(e[now].ch[0]);
q.push(now);
dfs(e[now].ch[1]);
}
int main()
{
// freopen("a.in","r",stdin);
// freopen("a.out","w",stdout);
n=read(),m=read();
FOR(i,1,n) init[i]=read();
rt=build(1,n);
FOR(i,1,m)
{
string s;
cin>>s;
if(s=="INSERT")
{ // 插入
int id=read(),gs=read(),x,y,z;
FOR(j,1,gs) init[j]=read();
y=build(1,gs);
split(rt,id,x,z);
rt=merge(merge(x,y),z);
} else
if(s=="DELETE")
{
int id=read()-1,gs=read(),x,y,z;
split(rt,id,x,z);
split(z,gs,y,z);
dfs(y);
rt=merge(x,z);
} else
if(s=="MAKE-SAME")
{
int id=read()-1,gs=read(),ad=read(),x,y,z;
split(rt,id,x,z);
split(z,gs,y,z);
down_1(y,ad);
rt=merge(merge(x,y),z);
} else
if(s=="REVERSE")
{
int id=read()-1,gs=read(),x,y,z;
split(rt,id,x,z);
split(z,gs,y,z);
down_2(y);
rt=merge(merge(x,y),z);
} else
if(s=="GET-SUM")
{
int id=read()-1,gs=read(),x,y,z;
split(rt,id,x,z);
split(z,gs,y,z);
cout<<e[y].sum<<"
";
rt=merge(merge(x,y),z);
} else
if(s=="MAX-SUM")
{ //询问
cout<<e[rt].ma<<"
";
}
}
return 0;
}