[题解] luogu P2042 [NOI2005]维护数列 Splay

神奇的题目。

网上说什么做了这道题 $Splay$ 就差不多了,嗯对窝也这么觉得。于是终于码掉了。

主要涉及的操作还是提取区间,我们组需要将 $l-1$ 提取至 $root$ , 然后将 $r+1$ 提取至 $l-1$ 的下方,最终 $l,r$ 区间的 $Splay$ 就是 $r+1$ 的左孩子。

这个时候该输出的就输出,该打标记的就打标记就好了。

至于插入的话我们可以先将所有需要插入的结点 $build$ 成一棵树,然后直接挂到 $r+1$ 的左孩子即可。

但是毒瘤出题人卡空间,于是我们需要将删除的结点全部重新应用,就像垃圾回收那样,搞个栈就行了。

最后因为怕 $l-1$ 和 $r+1$ 出界我们还需要新增两个"哨兵结点",这样子的话需要提取的结点都加上了 $1$ ,提取区间变动的两个节点就变成 $l$ 和 $r+2$ 了。

Code:

#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N=5.5e5+7;
const int inf=1e8;

template <typename _Tp> inline void IN(_Tp&x) {
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    if(flag) x=-x;
}

struct Splay {
    int root,cnt;
    int ch[N][2],sz[N],fa[N],val[N],tag[N],rev[N];
    int sum[N],lmax[N],rmax[N],smax[N];
    int date[N],trash[N],top;

    Splay(){root=cnt=top=0;}
    bool chk(int x) {return ch[fa[x]][1]==x;}
    void clear(int node) {
        ch[node][0]=ch[node][0]=sz[node]=fa[node]=val[node]=0,
        rev[node]=sum[node]=lmax[node]=rmax[node]=smax[node]=0;
        tag[node]=inf;
    }
    int MKN() {
        int node;
        node=top?trash[top--]:++cnt;
        clear(node);return node;
    }
    void pushup(int x) {
        int l=ch[x][0],r=ch[x][1];
        sz[x]=sz[l]+sz[r]+1;
        sum[x]=sum[l]+sum[r]+val[x];
        lmax[x]=max(lmax[l],sum[l]+val[x]+lmax[r]);
        rmax[x]=max(rmax[r],sum[r]+val[x]+rmax[l]);
        smax[x]=max(rmax[l]+lmax[r]+val[x],max(smax[l],smax[r]));
    }
    void pushdown(int x) {
        int l=ch[x][0],r=ch[x][1];
        if(tag[x]!=inf) {
            if(l) val[l]=tag[l]=tag[x],sum[l]=tag[x]*sz[l];
            if(r) val[r]=tag[r]=tag[x],sum[r]=tag[x]*sz[r];
            if(tag[x]>=0) {
                if(l) lmax[l]=rmax[l]=smax[l]=sum[l];
                if(r) lmax[r]=rmax[r]=smax[r]=sum[r];
            } else if(tag[x]<0) {
                if(l) lmax[l]=rmax[l]=0,smax[l]=tag[x];
                if(r) lmax[r]=rmax[r]=0,smax[r]=tag[x];
            }
            tag[x]=inf;
        }
        if(rev[x]) {
            if(l) swap(ch[l][0],ch[l][1]),swap(lmax[l],rmax[l]),rev[l]^=1;
            if(r) swap(ch[r][0],ch[r][1]),swap(lmax[r],rmax[r]),rev[r]^=1;
            rev[x]=0;
        }
    }
    void rotate(int x) {
        int y=fa[x],z=fa[y];
        pushdown(y),pushdown(x);
        int k=chk(x),v=ch[x][k^1];
        ch[z][chk(y)]=x,fa[x]=z,ch[y][k]=v,fa[v]=y,
        ch[x][k^1]=y,fa[y]=x;pushup(y),pushup(x);
    }
    void splay(int x,int gola=0) {
        while(fa[x]!=gola) {
            if(fa[fa[x]]!=gola)
                rotate(chk(x)^chk(fa[x])?x:fa[x]);
            rotate(x);
        }if(!gola) root=x;
    }
    int kth(int x) {
        int pos=root;
        while(pos) {
            pushdown(pos);
            if(x<=sz[ch[pos][0]]) pos=ch[pos][0];
            else {
                x-=sz[ch[pos][0]]+1;
                if(!x) return pos;
                pos=ch[pos][1];
            }
        }return 0;
    }
    int build(int l,int r,int f) {
        if(l>r) return 0;
        int x=MKN(),mid=(l+r)>>1;
        ch[x][0]=build(l,mid-1,x),ch[x][1]=build(mid+1,r,x);
        val[x]=date[mid],fa[x]=f,pushup(x);
        return x;  
    }
    void trashcan_node(int x) {
        if(!x) return;
        trash[++top]=x,trashcan_node(ch[x][0]),trashcan_node(ch[x][1]);
    }
    int split(int&l,int&r,int pos,int tot) {
        l=kth(pos),r=kth(pos+tot+1);splay(l),splay(r,l);
    }
    void work_insert() {
        int pos,tot,l,r;
        IN(pos),IN(tot);
        for(int i=1;i<=tot;++i) IN(date[i]);
        split(l,r,pos+1,0);
        ch[r][0]=build(1,tot,r),pushup(r),pushup(root);
    }
    void work_delete() {
        int pos,tot,l,r;
        IN(pos),IN(tot),split(l,r,pos,tot);
        trashcan_node(ch[r][0]),ch[r][0]=0,pushup(r),pushup(root);
    }
    void work_same() {
        int pos,tot,c,l,r;
        IN(pos),IN(tot),IN(c),split(l,r,pos,tot);
        int p=ch[r][0];
        if(p) {
            val[p]=tag[p]=c,sum[p]=c*sz[p];
            if(c>=0) lmax[p]=rmax[p]=smax[p]=sum[p];
            else if(c<0) lmax[p]=rmax[p]=0,smax[p]=c;
        }pushup(r),pushup(root);
    }
    void work_rev() {
        int pos,tot,l,r;
        IN(pos),IN(tot),split(l,r,pos,tot);
        if(ch[r][0]) {
            swap(ch[ch[r][0]][0],ch[ch[r][0]][1]);
            swap(lmax[ch[r][0]],rmax[ch[r][0]]);
            rev[ch[r][0]]^=1;
        }pushup(r),pushup(root);
    }
    void work_sum() {
        int pos,tot,l,r;
        IN(pos),IN(tot),split(l,r,pos,tot);
        printf("%d\n",sum[ch[r][0]]);
    }
    void work_max() {
        int l=kth(1),r=kth(sz[root]);splay(l),splay(r,l);
        printf("%d\n",smax[ch[r][0]]);
    }
}T;

int n,m;
char op[25];

int main() {
    // freopen("testdata.in","r",stdin);
    // freopen("myout.out","w",stdout);
    IN(n),IN(m);
    for(int i=1;i<=n;++i) IN(T.date[i+1]);
    T.smax[0]=T.date[1]=-inf,T.date[n+2]=inf;
    T.root=T.build(1,n+2,0);
    while(m--) {
        scanf("%s",op);
        if(op[0]=='M') {
            if(op[3]=='E') T.work_same();
            else T.work_max();
        } 
        else if(op[0]=='I') T.work_insert();
        else if(op[0]=='D') T.work_delete();
        else if(op[0]=='R') T.work_rev();
        else if(op[0]=='G') T.work_sum();
    }
    return 0;
}
Last modification:April 2nd, 2019 at 07:03 pm

Leave a Comment