题解 SP4487 【GSS6 - Can you answer these queries VI】
Jμdge
2019-10-23 16:15:06
nan
首先 FHQ 维护动态数组就是了...
剩下的就只是对付询问了...（貌似 GSS8 的思路同上？）
然后咱 FHQ 里面每个节点类似线段树上玩静态数组一样去维护节点就好了，多记录了四个值： $sum , lmax , rmax , mmax$
# Code
不知道简易写法（注释掉的）为什么 挂掉了 ，死活就是过不去. （艹）
可能是 sm 尽管多重考虑之后还是莫名锅了？？？（强行解释）
&& 没有压行，手动滑稽，这关键部分的代码不都没压嘛 【雾
顺便提一句，不用开 long long ，以及 FHQ 大小 2e5 就够了
```
//by Judge
#include<iostream>
#include<cstdio>
using namespace std;
const int M=2e5+23;
#ifndef Judge
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
#endif
char buf[1<<21],*p1=buf,*p2=buf;
inline int Max(int x,int y){return x>y?x:y;}
inline int read(){ int x=0,f=1; char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f;
} inline char cread(){ char c=getchar();
while(!isalpha(c)) c=getchar(); return c;
} char sr[1<<21],z[20];int C=-1,Z;
inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}
inline void print(int x){
if(C>1<<20)Ot();if(x<0)sr[++C]=45,x=-x;
while(z[++Z]=x%10+48,x/=10);
while(sr[++C]=z[Z],--Z);sr[++C]='\n';
} int n,m;
namespace FHQTreap{ int root,cnt;
#define ls t[now].ch[0]
#define rs t[now].ch[1]
struct Node { int val,key,sz,lm,rm,mm,sm,ch[2]; Node(){}
Node(int x,int r,int a,int b){ key=r,sz=1,lm=rm=Max(val=sm=mm=x,0),ch[0]=a,ch[1]=b; }
} t[M];
inline int Rand() { static signed seed=703; return seed=signed(seed*48271LL%(~0u>>1)); }
inline int newnode(int x){ return t[++cnt]=Node(x,Rand(),0,0),cnt; }
inline void update(int now){ t[now]=Node(t[now].val,t[now].key,ls,rs);
if(ls&&rs){
t[now].sm+=t[ls].sm+t[rs].sm,t[now].sz+=t[ls].sz+t[rs].sz;
t[now].lm=Max(t[ls].lm,Max(t[ls].sm+t[now].lm,t[ls].sm+t[now].val+t[rs].lm));
t[now].rm=Max(t[rs].rm,Max(t[rs].sm+t[now].rm,t[rs].sm+t[now].val+t[ls].rm));
t[now].mm=Max(Max(t[ls].mm,t[rs].mm),t[ls].rm+t[now].val+t[rs].lm);
} else if(ls){
t[now].sm+=t[ls].sm,t[now].sz+=t[ls].sz;
t[now].lm=Max(t[ls].lm,t[ls].sm+t[now].lm);
t[now].rm=Max(t[now].rm,t[now].val+t[ls].rm);
t[now].mm=Max(t[ls].mm,t[now].val+t[ls].rm);
} else if(rs){
t[now].sm+=t[rs].sm,t[now].sz+=t[rs].sz;
t[now].rm=Max(t[rs].rm,t[rs].sm+t[now].rm);
t[now].lm=Max(t[now].lm,t[now].val+t[rs].lm);
t[now].mm=Max(t[rs].mm,t[now].val+t[rs].lm);
}
/*
if(ls){
t[now].mm=Max(Max(t[ls].mm,t[now].mm),t[now].lm+t[ls].rm),
t[now].lm=Max(t[ls].lm,t[ls].sm+t[now].lm),
t[now].rm=Max(t[now].rm,t[now].sm+t[ls].rm),t[now].sm+=t[ls].sm;
}
if(rs){
t[now].mm=Max(Max(t[rs].mm,t[now].mm),t[rs].lm+t[now].rm),
t[now].lm=Max(t[now].lm,t[now].sm+t[rs].lm),
t[now].rm=Max(t[rs].rm,t[rs].sm+t[now].rm),t[now].sm+=t[rs].sm;
}
*/
}
int merge(int u,int v) { if(!u || !v) return u|v;
if(t[u].key<t[v].key) { t[u].ch[1]=merge(t[u].ch[1],v),update(u); return u; }
else { t[v].ch[0]=merge(u,t[v].ch[0]),update(v); return v; }
}
void split(int now,int k,int& x,int& y) { if(!now) return (void)(x=y=0);
if(t[t[now].ch[0]].sz>=k) split(t[y=now].ch[0],k,x,t[now].ch[0]);
else split(t[x=now].ch[1],k-t[t[now].ch[0]].sz-1,t[now].ch[1],y); update(now);
}
inline void ins(int p,int x) { int a,b; split(root,p-1,a,b),root=merge(merge(a,newnode(x)),b); }
inline void del(int p) { int a,b,c; split(root,p-1,a,b),split(b,1,b,c),root=merge(a,c); }
inline void rep(int p,int x) { int a,b,c; split(root,p-1,a,b),split(b,1,b,c),b=newnode(x),root=merge(a,merge(b,c)); }
inline int qry(int x,int y) { int a,b,c,s; return split(root,y,b,c),split(b,x-1,a,b),s=t[b].mm,root=merge(a,merge(b,c)),s; }
} using namespace FHQTreap;
signed main(){ n=read(); int opt,p,x;
while(n--) x=read(),root=merge(root,newnode(x));
m=read(); while(m--){ opt=cread();
switch(opt){
case 'I': p=read(),x=read(),ins(p,x); break;
case 'D': p=read(),del(p); break;
case 'R': p=read(),x=read(),rep(p,x); break;
case 'Q': p=read(),x=read(),print(qry(p,x)); break;
}
} return Ot(),0;
}
```
GSS 剩余一题...