link。
题意
对序列进行 \(n\) 次 reverse 操作，第 \(i\) 次操作的左端点为 \(i\)，问如果最终要使序列有序，每次操作选择的右端点是什么。
解法
由于每次左端点为 \(i\)，很容易想到右端点为第 \(i\) 小的数当前的下标。
但由于要 reverse 多次，还要快速求出指定数的下标，我们选择使用平衡树。
我们先对输入进来的序列排序，求出每个数应该去哪个位置。
对于 reverse 操作，我们使用 tag 作为懒标记。如果当前节点的懒标记为 true，那就交换左右儿子，并下传懒标记。
但是，我们在执行完 \(1 \sim i - 1\) 的操作后，不能保证第 \(i\) 小的数代表的节点以及它的祖先懒标记已经全部传下去了，所以我们从根节点到第 \(i\) 小的数代表的节点依次传递懒标记。
传递完之后，第 \(i\) 小的数代表的节点在树中的位置就确定了，这时，我们求出它的排名，这个排名就是对应在序列中的下标。
至于求每个数对应的节点，我们一边输入，一边往平衡树里塞点，那么在排序之前的下标就是在平衡树中的节点编号。
注意：由于传递懒标记是从上到下，所以我们需要记录每个点在平衡树中的父节点，对于一个需要被传递的节点 \(u\)，我们把它和它的父节点压到栈里，再按出栈顺序 push_down（因为栈是后进先出），这样就保证了 push_down 的顺序正确。
code
#include <cstdio>
#include <cstdlib>
#include <utility>
#include <algorithm>
#include <ctime>
#include <stack>
using namespace std;
const int N = 1e5 + 5;
struct Treap {
int tot, root;
struct node {
int l, r, key, rank, siz, f;
bool tag;
} a[N];
stack<int> st;
inline int New(int val) {
a[++tot].rank = rand(), a[tot].key = val;
a[tot].siz = 1;
return tot;
}
inline void update(int rt) { a[rt].siz = a[a[rt].l].siz + a[a[rt].r].siz + 1; a[a[rt].l].f = a[a[rt].r].f = rt; }
inline void change(int rt) { swap(a[rt].l, a[rt].r), a[rt].tag ^= 1; }
inline void push_down(int rt) {
if (a[rt].tag) {
change(a[rt].l);
change(a[rt].r);
a[rt].tag = false;
}
}
inline int merge(int rt1, int rt2) {
if (!rt1)
return rt2;
if (!rt2)
return rt1;
if (a[rt1].rank < a[rt2].rank) {
push_down(rt1);
a[rt1].r = merge(a[rt1].r, rt2);
update(rt1);
return rt1;
} else {
push_down(rt2);
a[rt2].l = merge(rt1, a[rt2].l);
update(rt2);
return rt2;
}
}
inline pair<int, int> split(int rt, int val) {
if (!rt)
return make_pair(0, 0);
push_down(rt);
if (a[a[rt].l].siz + 1 <= val) {
pair<int, int> ans = split(a[rt].r, val - a[a[rt].l].siz - 1);
a[rt].r = ans.first;
update(rt);
return make_pair(rt, ans.second);
} else {
pair<int, int> ans = split(a[rt].l, val);
a[rt].l = ans.second;
update(rt);
return make_pair(ans.first, rt);
}
}
inline int get_rank(int rt) {
for (int i = rt; i; i = a[i].f) //传递懒标记
st.push(i);
while (!st.empty())
push_down(st.top()), st.pop();
int res = 0;
for (int i = rt; i; i = a[i].f) //求排名
if (i == a[a[i].f].r) //如果当前点是它的父节点的右儿子，那么它的父节点和父节点的左子树一定比要求的点小
res += a[a[a[i].f].l].siz + 1;
return res + a[a[rt].l].siz + 1;
}
} BST;
int n, m, l, r;
struct node {
int x, id;
inline bool operator<(node X) const { return x != X.x ? x < X.x : id < X.id; }
} a[N];
int main() {
srand(time(0));
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i].x), a[i].id = i;
BST.root = BST.merge(BST.root, BST.New(i));
}
stable_sort(a + 1, a + n + 1);
for (int i = 1; i <= n; i++) {
int rank = BST.get_rank(a[i].id);
printf("%d ", rank, a[i].x);
l = i, r = rank; //将l~r翻转
pair<int, int> ans1 = BST.split(BST.root, r);
pair<int, int> ans2 = BST.split(ans1.first, l - 1);
BST.change(ans2.second);
BST.root = BST.merge(BST.merge(ans2.first, ans2.second), ans1.second);
}
return 0;
}