CF38G Queue解题报告

解题报告

CF38G Queue解题报告：

题意：给定$n$个点，每个点有一个权值$a_i$与一个约束值$c_i$，我们需要按顺序插入这$n$个数，每次插入一个点后，如果这个点的权值比上一个点的权值大，则需要与上一个点交换位置，一个点最多能与$c_i$个点交换位置，求最后的序列。

刚看到这道题，想维护小于一个值的一个数组，但是没搞出来，于是写了个Splay。

这道题所使用的Splay是类似【模板】文艺平衡树的Splay，叫做区间Splay，它就是以一个点的位置为权值来维护Splay的方法。

我们先定义一个数组$maxx_i$，代表以$i$为根节点的子树中最大值存在的位置，可以很容易写出它的$pushup$方式：

maxx[now]=val[now];
if(a[maxx[chd[now][0]]]>a[maxx[now]])
    maxx[now]=maxx[chd[now][0]];
if(a[maxx[chd[now][1]]]>a[maxx[now]])
    maxx[now]=maxx[chd[now][1]];

然后我们再考虑一个点的插入，当位置为$v$，权值为$a_v$的结点插入到$x$位置后，可以发现如果$a_v$大于$x$位置的权值和$x$的右子树的$maxx$的权值的话，这个结点就可以插入到$x$的左子树，否则就可以插入到右子树。

接下来，我们开始实现解决问题的核心操作$work$函数（$p$代表位置，$c$代表约束值），我们可以分两种情况讨论一下：
1. 如果当前位置可以和前面的任意多个节点换（只要满足条件），那我们就可以直接从根插入这个节点。
2. 否则，你需要用循环（或递归）找出编号$p-c-1$的节点，并将其设为根，因为这是一颗区间Splay，所以当前节点可以和这个$p-c-1$的右子树中任意一个节点交换（只要满足条件），就可以从根的右儿子节点插入。

void work(int p,int c){
    if(p-c>1){
        splay(getnum(p-c-1),0);
        insert(chd[root][1],root,p);
    }
    else insert(root,0,p);
    splay(cnt,0);
}

最后输出用中序遍历，应该大家都会吧。

时间复杂度：$O(n\log n)$（$n$次操作，每次操作用区间Splay可以达到$\log n$的复杂度（可以用势能分析））

代码：

#include<stdio.h>
#define inf 1000000000
const int maxn=100005;
int i,j,k,m,n;
int a[maxn];
inline int max(int a,int b){
    return a>b? a:b;
}
struct SPLAY{
    int cnt,root;
    int val[maxn],chd[maxn][2],f[maxn],size[maxn],maxx[maxn];
    inline void init(){
        cnt=root=0;
    }
    inline int newnode(int x,int fth){
        size[++cnt]=1,chd[cnt][0]=0,chd[cnt][1]=0,val[cnt]=x,f[cnt]=fth;
        return cnt;
    }
    inline void pushup(int now){
        size[now]=size[chd[now][0]]+size[chd[now][1]]+1;
        maxx[now]=val[now];
        if(a[maxx[chd[now][0]]]>a[maxx[now]])
            maxx[now]=maxx[chd[now][0]];
        if(a[maxx[chd[now][1]]]>a[maxx[now]])
            maxx[now]=maxx[chd[now][1]];
    }
    inline int check(int now){
        return chd[f[now]][0]==now? 0:1;
    }
    inline void connect(int now,int son,int dir){
        f[son]=now,chd[now][dir]=son;
    }
    inline void rotate(int now){
        int fth=f[now],gfth=f[fth],frlt=check(now),grlt=check(fth);
        connect(gfth,now,grlt),connect(fth,chd[now][frlt^1],frlt),connect(now,fth,frlt^1);
        pushup(fth),pushup(now);
    }
    void splay(int now,int aim){
        while(f[now]!=aim){
            int fth=f[now],gfth=f[fth],frlt=check(now),grlt=check(fth);
            if(gfth!=aim)
                rotate(frlt^grlt? now:fth);
            rotate(now);
        }
        if(aim==0)  
            root=now;
    }
    int getnum(int x){
        int now=root;
        while(now){
            if(x==size[chd[now][0]]+1)
                return now;
            if(x<=size[chd[now][0]])
                now=chd[now][0];
            else x-=size[chd[now][0]]+1,now=chd[now][1];
        }
        return now;
    }
    void insert(int &x,int lst,int v){
        if(x==0){
            x=newnode(v,lst);
            return ;
        }
        if(a[v]>a[val[x]]&&a[v]>a[maxx[chd[x][1]]])
            insert(chd[x][0],x,v);
        else insert(chd[x][1],x,v);
        pushup(x);
    }
    void work(int p,int c){
        if(p-c>1){
            splay(getnum(p-c-1),0);
            insert(chd[root][1],root,p);
        }
        else insert(root,0,p);
        splay(cnt,0);
    }
    void out(int x){
        if(chd[x][0])
            out(chd[x][0]);
        printf("%d ",val[x]);
        if(chd[x][1])
            out(chd[x][1]);
    }
    void write(){
        out(root);
    }
}Splay;
int main(){
    scanf("%d",&n);
    Splay.init();
    for(i=1;i<=n;i++){
        int c;
        scanf("%d%d",&a[i],&c);
        Splay.work(i,c);
    }
    Splay.write();
    return 0;
}