BZOJ 4864 [BeiJing 2017 WC]神秘物质

题目大意

给你一个序列，请你维护他们，要求支持：将两个元素合并为一个新的，权值可能完全不同的元素放回原位；末尾插入一个新元素；求一段区间的所有子区间里面极差最大/最小。

这道题一看维护序列蛇皮性质啥的就写Splay呗……

维护每个元素的权值，该子树的最大值和最小值，该子树的极差最小值。极差维护方法：首先假设最小极差是两个相邻的数的差，如果还有一个数加入，那么如果比两者中小的还小那么极差会变大，如果比两者中大的还大那么极差也会变大，如果在里面不影响极差，所以只需要找相邻两个数的差最小就好了。之后记录一下子树区间的左右端点之后大力Pushup就可以了。

这题不需要Pushdown，取而代之的是恶心的Pushup操作，稍有不慎就打出GG.

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,no,val[200010],ln[200010],rn[200010],maxn[200010],minn[200010],delta[200010],son[200010][2],fa[200010],siz[200010],inx,iny,root;
char mode[200010];
void pushup(int pos)
{
    int tl=son[pos][0],tr=son[pos][1];
    ln[pos]=val[pos],rn[pos]=val[pos],delta[pos]=0x3f3f3f3f;
    siz[pos]=siz[tl]+siz[tr]+1;
    maxn[pos]=val[pos];
    minn[pos]=val[pos];
    if(tl&&tl!=1&&tl!=no)
    {
        maxn[pos]=max(maxn[pos],maxn[tl]);
        minn[pos]=min(minn[pos],minn[tl]);
        delta[pos]=min(delta[pos],delta[tl]);
        delta[pos]=min(delta[pos],abs(val[pos]-rn[tl]));
    }
    if(tr&&tr!=1&&tr!=no)
    {
        maxn[pos]=max(maxn[pos],maxn[tr]);
        minn[pos]=min(minn[pos],minn[tr]);
        delta[pos]=min(delta[pos],delta[tr]);
        delta[pos]=min(delta[pos],abs(val[pos]-ln[tr]));
    }
    if(tl) ln[pos]=ln[tl];
    if(tr) rn[pos]=rn[tr];
}
int build(int l,int r)
{
    if(l>r) return 0;
    int mid=(l+r)>>1;
    son[mid][0]=build(l,mid-1),son[mid][1]=build(mid+1,r);
    fa[son[mid][0]]=fa[son[mid][1]]=mid;
    pushup(mid);
    return mid;
}
void rotate(int &k,int x)
{
    int y=fa[x],z=fa[y],l=(son[y][1]==x),r=l^1;
    if(y==k) k=x;
    else son[z][son[z][1]==y]=x;
    fa[x]=z,fa[y]=x,fa[son[x][r]]=y,son[y][l]=son[x][r],son[x][r]=y;
    pushup(y),pushup(x);
}
void splay(int &k,int x)
{
    while(x!=k)
    {
        int y=fa[x],z=fa[y];
        if(y!=k)
        {
            if((son[y][0]==x)^(son[z][0]==y)) rotate(k,x);
            else rotate(k,y);
        }
        rotate(k,x);
    }
}
int lookfor(int pos,int tx)
{
    if(tx<=siz[son[pos][0]]) return lookfor(son[pos][0],tx);
    if(tx>siz[son[pos][0]]+1) return lookfor(son[pos][1],tx-siz[son[pos][0]]-1);
    return pos;
}
int split(int tx,int ty)
{
    splay(root,lookfor(root,tx)),splay(son[root][1],lookfor(root,ty+2));
    return son[son[root][1]][0];
}
int main()
{
    memset(delta,0x3f,sizeof delta);
    memset(minn,0x3f,sizeof minn);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i) scanf("%d",val+i+1);
    for(int i=2;i<=n+1;++i) ln[i]=rn[i]=val[i];
    root=build(1,n+2);
    n+=2;
    no=n;
    while(m--)
    {
        scanf("%s%d%d",mode,&inx,&iny);
        switch(mode[1])
        {
            case 'e':
            {
                split(inx,inx+1);
                int tmp=son[son[root][1]][0];
                val[tmp]=ln[tmp]=rn[tmp]=iny;
                son[tmp][0]=son[tmp][1]=0;
                pushup(tmp);
                pushup(son[root][1]);
                pushup(root);
                break;
            }
            case 'n':
            {
                split(inx+1,inx);
                son[son[root][1]][0]=++n;
                fa[n]=son[root][1];
                val[n]=iny;
                pushup(n);
                pushup(son[root][1]);
                pushup(root);
                break;
            }
            case 'a':
            {
                int tmp=split(inx,iny);
                printf("%d\n",maxn[tmp]-minn[tmp]);
                break;
            }
            case 'i':
            {
                printf("%d\n",delta[split(inx,iny)]);
                break;
            }
        }
    }
    return 0;
}