P4146 序列终结者

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)

丑陋的代码:

#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;
}