排序机械臂

Description

Data Constraint

1$1$<=n$n$<=105$10^5$ ,1$1$<=ai$a_i$<=2∗109$2*10^9$

Solution

由于本蒟蒻实在是过于过于蒟蒻，前几天才学会Splay$Splay$，于是便找了道题来练练手。 由于每个物品被排好后就不会影响到后面机械臂工作，所以我们每次排好一个物品后就把它删除。 首先排序求得物品被删除的先后顺序，假设当前要删除物品i$i$，则先将i$i$旋转至root$root$，然后再将i$i$右边的物品j$j$（在序列上的）旋转至root$root$，此时i$i$为j$j$的左儿子，i$i$没有右儿子，易知这时i$i$的左儿子对应的子树即为需要翻转的那一段序列，给i$i$的左儿子打上个翻转tag$tag$，再将i$i$从树中删除即可，如此循环做n$n$遍即可求出答案。