P3165 [CQOI2014]排序机械臂

题目描述
为了把工厂中高低不等的物品按从低到高排好序，工程师发明了一种排序机械臂。它遵循一个简单的排序规则，第一次操作找到高度最低的物品的位置 P_1P
1
，并把左起第一个物品至 P_1P
1
间的物品 (即区间 [1,P_1][1,P
1
] 间的物品) 反序；第二次找到第二低的物品的位置 P_2P
2
，并把左起第二个至 P_2P
2
间的物品 (即区间 [2,P_2][2,P
2
] 间的物品) 反序……最终所有的物品都会被排好序。

样例说明

上图给出有六个物品的示例，第一次操作前，高度最低的物品在位置 44 ，于是把第一至第四的物品反序；第二次操作前，第二低的物品在位罝六，于是把第二至六的物品反序……

你的任务便是编写一个程序，确定一个操作序列，即每次操作前第 ii 低的物品所在位置 P_iP
i
，以便机械臂工作。需要注意的是，如果有高度相同的物品，必须保证排序后它们的相对位置关系与初始时相同。

输入输出格式
输入格式：
第一行包含正整数n,表示需要排序的物品数星。

第二行包含n个空格分隔的整数 P_iP
i
,表示每个物品的高度。

输出格式：
输出一行包含n个空格分隔的整数Pi。

(Splay)的练手题。 ~~刚开始想拿个Treap查询第(k)大的我就是个弱智。~~ 我们先搞个结构体，存值的大小和值的位置，因为答案与原值无关，所以我们结构体排序一下就得到了第(k)次操作需要动的节点位置

因为刚开始时对于位置来说是有序的，所以我们有序的插入每个节点，因为有序列翻转所以我们要加上哨兵节点（谢谢花）。我们在上一步已经处理好了第(k)步需要操作的点，(Splay)到根，左子树大小即为这个点左边的点，同时也是这个点的(rank)（注意哨兵节点对结果的影响）。得到了(rank)就可以输出了。现在有了左端点已经给出，又有了右端点（就是(rank)嘛），所以序列翻转即可

值得注意的是，这次我们输出前不包括(find)，故不能(pushdown)，所以我们需要在(splay)函数中手动加上(pushdown)。

void splay(int id, int goal){
    while(fa[id] != goal){
        int F = fa[id];
		pushdown(fa[F]),pushdown(F),pushdown(id);//通通下推即可
        if(fa[F] == goal)spin(id);
        else if(lor(id) ^ lor(F))spin(id), spin(id);
        else spin(F), spin(id);
        }
    if(!goal)root = id;
    }

Code

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#include<climits>
typedef long long LL;
using namespace std;
int RD(){
    int out = 0,flag = 1;char c = getchar();
    while(c < '0' || c >'9'){if(c == '-')flag = -1;c = getchar();}
    while(c >= '0' && c <= '9'){out = out * 10 + c - '0';c = getchar();}
    return flag * out;
    }
const int maxn = 100019,INF = 1e9;
int ch[maxn][2];
int val[maxn];
int size[maxn],pos[maxn];//pos用来表示某个值的位置
int lazy[maxn];
int fa[maxn];
int root, tot;
int New(int F, int v){
    fa[++tot] = F;ch[tot][0] = ch[tot][1] = 0;
    val[tot] = v;pos[v] = tot;
    size[tot] = 1;
    return tot;
    }
void pushup(int id){size[id] = size[ch[id][0]] + size[ch[id][1]] + 1;}
void pushdown(int id){
	if(lazy[id]){
		swap(ch[id][0], ch[id][1]);
		lazy[ch[id][0]] ^= 1;
		lazy[ch[id][1]] ^= 1;
		lazy[id] = 0;
		}
	}
bool lor(int id){return ch[fa[id]][0] == id ? 0 : 1;}
void spin(int id){
    int F = fa[id],d = lor(id);
    fa[id] = fa[F];
    if(fa[F])ch[fa[F]][lor(F)] = id;
    fa[F] = id;
    ch[F][d] = ch[id][d ^ 1];
    if(ch[F][d])fa[ch[F][d]] = F;
    ch[id][d ^ 1] = F;
    pushup(F), pushup(id);
    }
void splay(int id, int goal){
    while(fa[id] != goal){
        int F = fa[id];
		pushdown(fa[F]),pushdown(F),pushdown(id);
        if(fa[F] == goal)spin(id);
        else if(lor(id) ^ lor(F))spin(id), spin(id);
        else spin(F), spin(id);
        }
    if(!goal)root = id;
    }
int find(int id, int rank){//寻找rank - 1
	pushdown(id);
    if(size[ch[id][0]] >= rank)return find(ch[id][0], rank);
    else if(size[ch[id][0]] + 1 == rank)return id;
    else return find(ch[id][1], rank - size[ch[id][0]] - 1);
    }
void insert(int v){
    ch[root][1] = New(root, v);
    splay(pos[v], 0);
    }
void Reverse(int l, int r){
	int x = find(root, l - 1), y = find(root, r + 1);
	splay(x, 0), splay(y, root);
	lazy[ch[ch[root][1]][0]] ^= 1;	
	}
int num;
struct Node{
	int val,index;
	}I[maxn];
bool cmp(Node a, Node b){
	if(a.val != b.val)return a.val < b.val;
	return a.index < b.index;
	}
int main(){
	num = RD();
	I[1].val = -INF, I[1].index = 1;
	for(int i = 2;i <= num + 1;i++)I[i].val = RD(),I[i].index = i;
	I[num + 2].val = INF, I[num + 2].index = num + 2;
	sort(I + 1, I + num + 3, cmp);
	root = New(0, 1);
	for(int i = 2;i <= num + 2;i++)insert(i);
	for(int i = 2;i <= num;i++){
		int x = pos[I[i].index];//受死吧，轮到你了！
		splay(x, 0);
		printf("%d ", size[ch[root][0]]);//加一减一我不变
		Reverse(i, size[ch[root][0]] + 1);//后继
		}
	printf("%d
", num);
	return 0;
    }