M_sea

洛谷3165 [CQOI2014]排序机械臂
LuoguBZOJ分析考虑用平衡树维护这个序列,需要支持区间查询最小值的位置、区间翻转。可以把原序列离散化一下,然...
扫描右侧二维码阅读全文
17
2019/03

洛谷3165 [CQOI2014]排序机械臂

Luogu

BZOJ

分析

考虑用平衡树维护这个序列,需要支持区间查询最小值的位置、区间翻转。

可以把原序列离散化一下,然后记一下每个数原来的位置,把所有操作放到一个 $1\sim n$ 的序列上去做。

手玩一下发现,就是找到原来操作位置的排名,然后再翻转。

至于怎么查排名,可以不断的往上跳,累加 $\mathrm{size}$ 。

具体实现及细节见代码。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

struct fhq_treap {
    int ch[N][2],rnd[N],sz[N],rev[N],fa[N];
    int sta[N],top;
    int cnt,root;

    fhq_treap() { this->cnt=this->root=0; }
    inline int newnode(int x) { sz[++cnt]=1,rnd[cnt]=rand(); return cnt; }

#define ls ch[o][0]
#define rs ch[o][1]

    inline void R(int o) { swap(ls,rs),rev[o]^=1; }
    inline void pushup(int o) { sz[o]=sz[ls]+sz[rs]+1,fa[ls]=fa[rs]=o; }
    inline void pushdown(int o) {
        if (rev[o]) R(ls),R(rs),rev[o]=0;
    }

    inline void split(int o,int k,int& x,int& y) {
        if (!o) { x=y=0; return; }
        pushdown(o);
        if (sz[ls]<k) x=o,split(rs,k-sz[ls]-1,rs,y);
        else y=o,split(ls,k,x,ls);
        pushup(o);
    }
    inline int merge(int A,int B) {
        if (!A||!B) return A+B;
        if (rnd[A]<rnd[B]) {
            pushdown(A),ch[A][1]=merge(ch[A][1],B),pushup(A);
            return A;
        } else {
            pushdown(B),ch[B][0]=merge(A,ch[B][0]),pushup(B);
            return B;
        }
    }
    
#undef ls
#undef rs
    
    inline void insert(int k) {
        int x,y; split(root,k,x,y);
        root=merge(merge(x,newnode(k)),y);
    }
    inline void reverse(int l,int r) {
        int x,y,z; split(root,l-1,x,y),split(y,r-l+1,y,z);
        R(y),root=merge(merge(x,y),z);
    }
    inline int getrank(int o) {
        sta[top=1]=o;
        for (re int i=o;fa[i];i=fa[i]) sta[++top]=fa[i];
        while (top) pushdown(sta[top--]);
        int res=sz[ch[o][0]];
        while (o) {
            if (o==ch[fa[o]][1]) res+=sz[ch[fa[o]][0]]+1;
            o=fa[o];
        }
        return res+1;
    }
} T;

int n;
struct node { int h,id; } a[N];
bool operator <(node a,node b) { return a.h==b.h?a.id<b.id:a.h<b.h; }

int main() {
    n=read();
    for (re int i=1;i<=n;++i) a[i].h=read(),a[i].id=i;
    sort(a+1,a+n+1);
    for (re int i=1;i<=n;++i) T.insert(i);
    for (re int i=1;i<=n;++i) {
        int p=T.getrank(a[i].id);
        T.reverse(i,p);
        printf("%d ",p);
    }
    return 0;
}
最后修改:2019 年 05 月 26 日 09 : 14 PM

发表评论