P4146 序列终结者
Captain_Paul
2018-03-30 10:27:30
作为一个平衡树萌新,能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;
}
```