题解 P3165 【[CQOI2014]排序机械臂】

· · 题解

还是我的Logo >_<

看别的题解好长好难理解

那我们写个短的

首先 这是一个平衡树

这个题要求是 查询第 k 小并反转某个区间

所以呢

fhq Treap 啊

我们权值为输入的下标， 建一个fhq Treap

然后以该点的权值作为优先级，使之成为小根堆

这样当前 Treap 的堆顶就是当前最小值

于是我们就直接取堆顶， 然后删除

至于旋转， 我们在删除之前

在堆顶的左子树中打上 lazy 标记就好了

然后删掉堆顶

因为我们是按照位置为权值，那么左子树的所有点都在当序列中前节点的左侧

即需要翻转的地方

所以我们就写一个甚至只需要 merge 的 fhq Treap 就好了

棒棒哒

#include <bits/stdc++.h>
#define II long long
#define IL inline
#define R register
#define I 123456
#define PI 100000
using namespace std;

IL void of(R II &a) {
    R char c=getchar(); R II w=1, p=0;
    while (c<'0' || c>'9') { if(c=='-') w=-1; c=getchar(); }
    while (c>='0' && c<='9') { p=p*10+c-'0'; c=getchar(); }
    a=w*p;
}

/* -------------------- Peipei -------------------- */

II n,root;

struct owo { II l,r,w,ra,siz,lazy; } Tr[I];
IL void up(R II o) { Tr[o].siz=Tr[Tr[o].l].siz+Tr[Tr[o].r].siz+1; }
IL void updata(R II o) {
    if(Tr[o].lazy) {
        R II l=Tr[o].l, r=Tr[o].r;
        swap(Tr[o].l,Tr[o].r);
        if(l) Tr[l].lazy^=1;
        if(r) Tr[r].lazy^=1;
        Tr[o].lazy=0;
    }
}

IL II merge(R II l,R II r) {
    if(l*r==0) return l+r;
    if(Tr[l].ra<Tr[r].ra) {
        updata(l);
        Tr[l].r=merge(Tr[l].r,r);
        up(l); return l;
    } else {
        updata(r);
        Tr[r].l=merge(l,Tr[r].l);
        up(r); return r;
    }
}

int main()
{
//    freopen("1.in","r",stdin);

    of(n);
    for(R II i=1,x;i<=n;i++) {
        of(x); x=x*PI+i;
        Tr[i]=(owo) {0,0,i,x,1,0};
        root=merge(root,i);
    }    

    for(R II i=1,l,r;i<=n;i++)
    {
        updata(root);
        printf("%lld ",Tr[Tr[root].l].siz+i);
        l=Tr[root].l; r=Tr[root].r;
        Tr[root].l=Tr[root].r=0;
        Tr[l].lazy^=1;
        root=merge(l,r);
    }
    exit(0);
}

是不是特别短？？！

【滑稽】