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

 还是我的Logo >\_< 看别的题解好长好难理解 那我们写个短的 首先 这是一个平衡树 这个题要求是 查询第 k 小并反转某个区间 所以呢 # **fhq Treap** 啊 我们权值为输入的下标， 建一个fhq Treap 然后以该点的权值作为优先级，使之成为小根堆 这样当前 Treap 的堆顶就是当前最小值 于是我们就直接取堆顶， 然后删除 至于旋转， 我们在删除之前 在堆顶的左子树中打上 lazy 标记就好了 然后删掉堆顶 因为我们是按照位置为权值，那么左子树的所有点都在当序列中前节点的左侧 即需要翻转的地方 所以我们就写一个甚至只需要 merge 的 fhq Treap 就好了 棒棒哒 ```cpp #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); } ``` 是不是特别短？？！ 【滑稽】