【BZOJ3506】【Cqoi2014】排序机械臂

传送门（因为BZOJ上没有题面...所以放的是luogu的）

题意:你需要维护一个序列，支持区间翻转与查询区间最小。

解题思路：由于区间最小实际上每一次就是对应的整个数列的第k小，因此可以直接预处理解决，接下来考虑如何找到这个点，可以直接用一个指针解决，然后就是简单的无旋treap操作：

给定一个平衡树上节点，求它在当前序列中的下标，首先我们先将这个点到平衡树根节点的标记下传，使用递归解决，然后就直接根据BST的性质查找即可。

其余的就是按照题意进行区间rotate，这是无旋treap的简单操作之一，不多赘述。

代码中还有很多东西是可以优化的，例如不需要存储val，可以舍弃已经有序的区间等，如果你能做到的话，应该是轻松Rank1的节奏？

#include <stdio.h>

#include <algorithm>

#define r register

#define MN 100005

#define getchar() (S==TT&&(TT=(S=BB)+fread(BB,1,1<<15,stdin),TT==S)?EOF:*S++)

char BB[<<],*S=BB,*TT=BB;

inline int in(){

    r int x=; r bool f=; r char c;

    for (;(c=getchar())<''||c>'';f=c=='-');

    for (x=c-'';(c=getchar())>=''&&c<='';x=(x<<)+(x<<)+c-'');

    return f?-x:x;

}

namespace Treap{

    inline int Rand(){

        static int x=;

        return x^=x<<,x^=x>>,x^=x<<;

    }

    struct node{

        node *ls,*rs,*fa;

        int val,sz,pri;bool rev;

        inline void reverse(){std::swap(ls,rs);if (ls) ls->rev^=;if (rs) rs->rev^=;rev=;}

        inline void pushdown(){if (rev) reverse();}

        inline void combine(){

            sz=;if (ls) sz+=ls->sz,ls->fa=this;

            if (rs) sz+=rs->sz,rs->fa=this;

        }

        node(int val):val(val){sz=,pri=Rand(),rev=,fa=ls=rs=NULL;}

    }*root,*pos[MN];

    struct Droot{node *a,*b;};

    inline int Size(node *x){return x?x->sz:;}

    node *merge(node *a,node *b){

        if (!a) return b;if (!b) return a;

        if (a->pri<b->pri){

            a->pushdown();

            a->rs=merge(a->rs,b);

            a->combine();return a;

        }else{

            b->pushdown();

            b->ls=merge(a,b->ls);

            b->combine();return b;

        }

    }

    Droot split(node *x,int k){

        if (!x) return (Droot){NULL,NULL};

        r Droot y;x->pushdown();

        if (k<=Size(x->ls)){

            y=split(x->ls,k);

            x->ls=y.b;x->combine();y.b=x;

        }else{

            y=split(x->rs,k-Size(x->ls)-);

            x->rs=y.a;x->combine();y.a=x;

        }return y;

    }

    inline void Rotate(node *x){if (!x) return;Rotate(x->fa);x->pushdown();}

    inline int getpos(node *x){

        Rotate(x);r int res=Size(x->ls)+;

        while (x->fa!=NULL){

            if (x->fa->rs==x) res+=Size(x->fa->ls)+;x=x->fa;

        }return res;

    }

    inline int Get_Ans(int k){

        r int ord=getpos(pos[k]);

        Droot x=split(root,ord);

        Droot y=split(x.a,k-);

        y.b->rev^=;root=merge(merge(y.a,y.b),x.b);

        return ord;

    }

}using namespace Treap;

struct things{

    int ord,val;

    inline bool operator <(const things &b)const{

        return val<b.val||(val==b.val&&ord<b.ord);

    }

}a[MN];int n,val[MN],rnk[MN];

void init(){

    n=in();

    for (int i=; i<=n; ++i) val[i]=in(),a[i].ord=i,a[i].val=val[i];

    std::sort(a+,a+n+);for (r int i=; i<=n; ++i) rnk[a[i].ord]=i;

    for (r int i=; i<=n; ++i){

        pos[rnk[i]]=new node(val[i]);

        root=merge(root,pos[rnk[i]]);

    }

}

void solve(){for (r int i=; i<=n; ++i) printf("%d ",Get_Ans(i));}

int main(){init();solve();return ;}

巴特西

【BZOJ3506】【Cqoi2014】排序机械臂

最新文章

热门文章