题解 SP4487 【GSS6 - Can you answer these queries VI】
xukuan
2020-05-03 16:28:12
本题解是[这一篇题解](https://www.luogu.com.cn/blog/xukuan/solution-p2042)的弱化版，采用相同的风格叙述
本题共有6种操作：单点插入，单点删除，单点修改，区间最大子段和
考虑fhqtreap或splay解法，本题解使用fhqtreap
**operation 1 单点插入**
以pos位置为界分裂成x,y两段，然后新建一颗树并合并回去
伪代码：
```cpp
split(root,pos,x,y)
init(a)
root=merge(x,merge(New(a)),y)
```
**operation 2 单点删除**
以pos-1和pos为界分裂成x,y,z三段，然后把x,z合并回去
伪代码：
```cpp
split(root,pos-1,x,y)
split(y,1,y,z)
root=merge(x,z)
```
**operation 3 单点修改**
删了再加回去
伪代码：
```cpp
split(root,pos-1,x,y)
split(y,1,y,z)
init(a)
cover(y,a)
root=merge(x,y),z)
```
**operation 4 区间最大子序列**
以l-1和r为界分裂成x,y,z三段，给区间y算最大子序列（不会的去做SPOJ GSS3），然后把x,y,z合并回去
伪代码：
```cpp
split(root,l-1,x,y)
split(y,r-l+1,y,z)
write(tree[y].sum)
root=merge(x,merge(y,z))
```
看split和merge两个操作，我们现在要处理pushup和pushdown，另外还有cover和reverse要处理
**关于pushup：**
pushup需要传这几个量：
子树大小和维护区间最大子段和所需的四个量。
**关于建树**
仿照线段树的二分建树即可
代码：
```cpp
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
const ll N=500010;
ll n,m,root,cnt,a[N],top,st[N];
struct fhqtreap{
ll lson,rson,rev,cov,size,val,sum,Lmax,Rmax,Mmax,tag,rnd;
}tree[N];
inline ll read(){
ll x=0,tmp=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') tmp=-1;
ch=getchar();
}
while(isdigit(ch)){
x=(x<<3)+(x<<1)+(ch^48);
ch=getchar();
}
return tmp*x;
}
inline void write(ll x){
if(x<0){
putchar('-');
x=-x;
}
ll y=10,len=1;
while(y<=x){
y=(y<<3)+(y<<1);
len++;
}
while(len--){
y/=10;
putchar(x/y+48);
x%=y;
}
}
inline ll New(ll val){
ll p=st[top--];
tree[p].rnd=rand();
tree[p].lson=tree[p].rson=tree[p].rev=tree[p].cov=0;
tree[p].size=1;
tree[p].val=tree[p].sum=tree[p].Mmax=val;
tree[p].Lmax=tree[p].Rmax=max(0ll,val);
return p;
}
inline void pushup(ll p){
tree[p].size=tree[tree[p].lson].size+tree[tree[p].rson].size+1;
tree[p].sum=tree[tree[p].lson].sum+tree[tree[p].rson].sum+tree[p].val;
tree[p].Lmax=max(max(tree[tree[p].lson].Lmax,tree[tree[p].lson].sum+tree[p].val+tree[tree[p].rson].Lmax),0ll);
tree[p].Rmax=max(max(tree[tree[p].rson].Rmax,tree[tree[p].rson].sum+tree[p].val+tree[tree[p].lson].Rmax),0ll);
tree[p].Mmax=max(tree[p].val,tree[tree[p].lson].Rmax+tree[p].val+tree[tree[p].rson].Lmax);
if(tree[p].lson) tree[p].Mmax=max(tree[p].Mmax,tree[tree[p].lson].Mmax);
if(tree[p].rson) tree[p].Mmax=max(tree[p].Mmax,tree[tree[p].rson].Mmax);
}
inline void reverse(ll p){
swap(tree[p].lson,tree[p].rson);
swap(tree[p].Lmax,tree[p].Rmax);
tree[p].rev^=1;
}
inline void cover(ll p,ll val){
tree[p].val=tree[p].cov=val;
tree[p].sum=tree[p].size*val;
tree[p].Lmax=tree[p].Rmax=max(0ll,tree[p].sum);
tree[p].Mmax=max(val,tree[p].sum);
tree[p].tag=1;
}
inline void pushdown(ll p){
if(tree[p].rev){
if(tree[p].lson) reverse(tree[p].lson);
if(tree[p].rson) reverse(tree[p].rson);
tree[p].rev=0;
}
if(tree[p].tag){
if(tree[p].lson) cover(tree[p].lson,tree[p].cov);
if(tree[p].rson) cover(tree[p].rson,tree[p].cov);
tree[p].cov=tree[p].tag=0;
}
}
void split(ll p,ll k,ll &x,ll &y){
if(!p){
x=y=0;
return;
}
pushdown(p);
if(tree[tree[p].lson].size+1<=k){
x=p;
split(tree[p].rson,k-tree[tree[p].lson].size-1,tree[p].rson,y);
}
else{
y=p;
split(tree[p].lson,k,x,tree[p].lson);
}
pushup(p);
}
ll merge(ll x,ll y){
if(!x||!y) return x|y;
if(tree[x].rnd<tree[y].rnd){
pushdown(x);
tree[x].rson=merge(tree[x].rson,y);
pushup(x);
return x;
}
else{
pushdown(y);
tree[y].lson=merge(x,tree[y].lson);
pushup(y);
return y;
}
}
inline ll build(ll l,ll r){
if(l==r) return New(a[l]);
ll mid=(l+r)>>1;
return merge(build(l,mid),build(mid+1,r));
}
void erase(ll p){
st[++top]=p;
if(tree[p].lson) erase(tree[p].lson);
if(tree[p].rson) erase(tree[p].rson);
}
int main(){
for(ll i=1; i<=N-10; i++) st[++top]=i;
srand(time(NULL));
n=read();
for(ll i=1; i<=n; i++) a[i]=read();
root=build(1,n);
m=read();
while(m--){
char op[10]; scanf("%s",op);
ll x,y,z;
switch(op[0]){
case 'I':{
ll pos=read(),val=read();
split(root,pos-1,x,y);
root=merge(merge(x,New(val)),y);
break;
}
case 'D':{
ll pos=read();
split(root,pos-1,x,y);
split(y,1,y,z);
erase(y);
root=merge(x,z);
break;
}
case 'R':{
ll pos=read(),val=read();
split(root,pos-1,x,y);
split(y,1,y,z);
cover(y,val);
root=merge(x,merge(y,z));
break;
}
case 'Q':{
ll l=read(),r=read();
split(root,l-1,x,y);
split(y,r-l+1,y,z);
write(tree[y].Mmax); putchar('\n');
root=merge(x,merge(y,z));
break;
}
default:{
printf("FUCK %s\n",op);
break;
}
}
}
return 0;
}
```