题面
题目描述
为了把工厂中高低不等的物品按从低到高排好序，工程师发明了一种排序机械臂。它遵循一个简单的排序规则，第一次操作找到摄低的物品的位置P1,并把左起第一个至P1间的物品反序；第二次找到第二低的物品的位置P2,并把左起第二个至P2间的物品反序...最终所有的物品都会被排好序。
你的任务便是编写一个程序，确定一个操作序列，即每次操作前第i低的物品所在位置Pi,以便机械臂工作。需要注意的是，如果有高度相同的物品，必须保证排序后它们的相对位置关系与初始时相同。
输入输出格式
输入格式：
第一行包含正整数n,表示需要排序的物品数星。
第二行包含n个空格分隔的整数ai,表示每个物品的高度。
输出格式：
输出一行包含n个空格分隔的整数Pi。
输入输出样例
输入样例#1：
6
3 4 5 1 6 2
输出样例#1：
4 6 4 5 6 6
说明
N<=100000 ai<=10^7
Sol
每次要排序的数首先是知道的，每次就把这个位置splay一下
区间翻转就不说了
# include <bits/stdc++.h>
# define RG register
# define IL inline
# define Fill(a, b) memset(a, b, sizeof(a))
using namespace std;
typedef long long ll;
const int _(1e5 + 10);
IL ll Read(){
char c = '%'; ll x = 0, z = 1;
for(; c > '9' || c < '0'; c = getchar()) if(c == '-') z = -1;
for(; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - '0';
return x * z;
}
int fa[_], ch[2][_], sz[_], rev[_], rt, len, n;
struct Zsy{
int id, v;
IL bool operator <(Zsy Orz) const{ return v != Orz.v ? v < Orz.v : id < Orz.id; }
} a[_];
IL bool Son(RG int x){ return ch[1][fa[x]] == x; }
IL void Update(RG int x){ sz[x] = sz[ch[0][x]] + sz[ch[1][x]] + 1; }
IL void Reverse(RG int x){ rev[x] ^= 1; swap(ch[1][x], ch[0][x]); }
IL void Pushdown(RG int x){ if(!rev[x]) return; Reverse(ch[0][x]); Reverse(ch[1][x]); rev[x] ^= 1; }
IL void Rotate(RG int x){
RG int y = fa[x], z = fa[y], c = Son(x);
Pushdown(y); Pushdown(x);
ch[Son(y)][z] = x; fa[x] = z;
ch[c][y] = ch[!c][x]; fa[ch[c][y]] = y;
ch[!c][x] = y; fa[y] = x; Update(y);
}
IL void Splay(RG int x, RG int rrt){
for(RG int y = fa[x]; y != rrt; Rotate(x), y = fa[x])
if(fa[y] != rrt) Son(x) ^ Son(y) ? Rotate(x) : Rotate(y);
Update(x); if(!rrt) rt = x;
}
IL void Build(RG int ff, RG int &x, RG int l, RG int r){
if(l > r) return;
RG int mid = (l + r) >> 1;
x = mid; fa[x] = ff; sz[x] = 1;
Build(x, ch[0][x], l, mid - 1); Build(x, ch[1][x], mid + 1, r);
Update(x);
}
IL int Kth(RG int k){
RG int x = rt;
while(233){
Pushdown(x);
if(k == sz[ch[0][x]] + 1) return x;
else if(k <= sz[ch[0][x]]) x = ch[0][x];
else k -= sz[ch[0][x]] + 1, x = ch[1][x];
}
}
IL void Split(RG int l, RG int r){
RG int x = Kth(l - 1); Splay(x, 0);
RG int y = Kth(r + 1); Splay(y, rt);
Reverse(ch[0][y]);
}
int main(RG int argc, RG char *argv[]){
n = Read(); a[1].v = -2e9; a[n + 2].v = 2e9; a[1].id = 1; a[n + 2].id = n + 2;
for(RG int i = 2; i <= n + 1; ++i) a[i].id = i, a[i].v = Read();
sort(a + 1, a + n + 3); Build(0, rt, 1, n + 2);
for(RG int i = 2; i <= n + 1; ++i){
Splay(a[i].id, 0);
printf("%d", sz[ch[0][rt]]);
if(i != n + 1) putchar(' ');
Split(i, sz[ch[0][rt]] + 1);
}
return 0;
}