P4146 序列终结者

Captain_Paul

2018-03-30 10:27:30

Solution

作为一个平衡树萌新,能AC这道题也是很不容易 思路主要参考了P2042维护数列题解中I_AM_HelloWord大佬的讲解 建立哨兵节点1和n+2,将操作序列整体后移一位 之后建树,在建树中预处理平衡树各个节点的val和maxn 接下来分析题目中的三种操作 对一个区间进行操作,可以看成从左端点L开始连续处理R-L+1的点 于是我们用一个split操作找到在平衡树中序遍历中实际需要操作的区间 然后在reverse,change和getmax操作中直接调用即可 对于每一种操作分别维护反转标记,加法标记,区间最大值 由于每一次操作都要用到find 所以直接在find函数中下传标记就可以了 ps:maxn[0]要初始化为-inf,inf一定要开极大值 ~~(否则就会像我一样WA)~~ 丑陋的代码: ```cpp #include<cstdio> #include<cstring> #include<cctype> #include<algorithm> #define ls ch[now][0] #define rs ch[now][1] using namespace std; const int N=1e5+5,inf=2147483640; int n,m,cnt,root,a[N],tag[N],maxn[N],ch[N][2],val[N],f[N],size[N],id[N]; bool rev[N]; inline int read() { int x=0,w=1; char c=getchar(); while (!isdigit(c)&&c!='-') c=getchar(); if (c=='-') c=getchar(),w=-1; while (isdigit(c)) { x=(x<<1)+(x<<3)+c-'0'; c=getchar(); } return x*w; } inline bool get(int x) { return ch[f[x]][1]==x; } inline void update(int now) { size[now]=size[ls]+size[rs]+1; maxn[now]=max(val[now],max(maxn[ls],maxn[rs])); } inline void pushdown(int now) { if (rev[now]) { if (ls) rev[ls]^=1,swap(ch[ls][0],ch[ls][1]); if (rs) rev[rs]^=1,swap(ch[rs][0],ch[rs][1]); rev[now]=0; } if (tag[now]) { if (ls) tag[ls]+=tag[now],maxn[ls]+=tag[now],val[ls]+=tag[now]; if (rs) tag[rs]+=tag[now],maxn[rs]+=tag[now],val[rs]+=tag[now]; tag[now]=0; } } void build(int l,int r,int p) { int mid=(l+r)>>1,now=mid,pre=p; if (l==r) { maxn[now]=a[l]; size[now]=1; rev[now]=0; } if (l<mid) build(l,mid-1,mid); if (mid<r) build(mid+1,r,mid); val[now]=a[mid]; f[now]=pre; update(now); ch[pre][mid>=p]=now; } inline void rotate(int x,int &k) { int y=f[x],z=f[y],t=get(x),w=ch[x][t^1]; if (y==k) k=x; else ch[z][ch[z][1]==y]=x; ch[y][t]=w; if (w) f[w]=y; ch[x][t^1]=y; f[y]=x; f[x]=z; update(y); update(x); } inline void splay(int x,int &k) { while (x!=k) { int y=f[x],z=f[y]; if (y!=k) rotate(get(y)==get(x)?y:x,k); rotate(x,k); } } int find(int now,int k) { pushdown(now); if (size[ls]==k-1) return now; if (size[ls]>=k) return find(ls,k); return find(rs,k-size[ls]-1); } inline int split(int x,int tot) { int l=find(root,x),r=find(root,tot+2); splay(l,root); splay(r,ch[root][1]);//找到[x+1,x+tot] return ch[r][0]; } inline void reverse(int x,int y) { int now=split(x,y),z=f[now]; rev[now]^=1; swap(ls,rs); update(z); update(f[z]); } inline void change(int x,int y,int v) { int now=split(x,y),z=f[now]; val[now]+=v; tag[now]+=v; maxn[now]+=v; update(z); update(f[z]); } inline int getmax(int x,int y) { return maxn[split(x,y)]; } int main() { n=read(),m=read(); maxn[0]=a[1]=a[n+2]=-inf; root=(n+3)>>1; build(1,n+2,0); while (m--) { int opt=read(),x=read(),y=read(); if (opt==1) change(x,y,read()); if (opt==2) reverse(x,y); if (opt==3) printf("%d\n",getmax(x,y)); } return 0; } ```