这不是我们 [SCOI2014] 方伯伯的 OJ 的梗吗？

几乎就是双倍经验，用一个 Treap 维护每一个连续值域段代表什么，然后树的中序遍历即为这些连续段的前后位置。同时再用一个 map 记录每个连续段的左端点对应 Treap 当中的哪个节点，插入和修改的时候同理修改映射即可。

每次我们只需要找一个值所在的区间在是平衡树的哪个节点，利用中序遍历计算这个连续段的最后一个点是实际的哪一个位置就行了。修改位置时就是将这个值域段分裂然后重新插入即可。

AcWing 卡常，但是直接开火车头可过。

#include <stdio.h>
#include <chrono>
#include <random>
#include <array>
#include <map>
#include <algorithm>
typedef long long i64;
std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());
std::uniform_int_distribution<int> gen_pri(1, 1145141919);
inline i64 rd()
{
    i64 k = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') f = (c == '-') ? 0 : f, c = getchar();
    while (c >= '0' && c <= '9') k = (k << 1) + (k << 3) + (c ^ '0'), c = getchar();
    return f ? k : -k;
}
inline char rd_op()
{
    char c = getchar();
    while (c < 'A' || c > 'Z') c = getchar();
    return c;
}
inline void wr(int x)
{
    if (x < 0) x = -x, putchar('-');
    if (x > 9) wr(x / 10);
    putchar((x % 10) ^ '0');
}
int n, m;
int op, x, last_ans;
inline int len(const std::pair<int, int>& in) { return in.second - in.first + 1; }
// first = interval.l second = node-id in treap
std::map<int, int> mp;
namespace treap // save interval
{
    const int N = 200010;
    struct node
    {
        std::pair<int, int> val; // interval
        int lc, rc, fa, pri, sz;
    } tr[N];
    int cnt, rt;
    int rec[N], top; // update mp here.
    inline void recycle(int u) { mp.erase(mp.find(tr[u].val.first)), rec[++top] = u; }
    inline void recycle_full(int u)
    {
        if (!u) return;
        recycle_full(tr[u].lc), recycle_full(tr[u].rc), recycle(u);
    }
    inline void clr() { recycle_full(rt), rt = 0; }
    // debug
    void print(int u)
    {
        if (!u) return;
        print(tr[u].lc);
        printf("node %d : (%d %d) sz %d lc %d rc %d\n", u, tr[u].val.first, tr[u].val.second, tr[u].sz, tr[u].lc, tr[u].rc);
        print(tr[u].rc);
    }
    void print_all()
    {
        puts("treap : ");
        print(rt), putchar('\n');
        printf("mp : ");
        for (auto& x : mp) printf("(%d %d) ", x.first, x.second);
        putchar('\n');
    }
    inline void pushup(int u) 
    { 
        tr[tr[u].lc].fa = tr[tr[u].rc].fa = u;
        tr[u].sz = tr[tr[u].lc].sz + tr[tr[u].rc].sz + len(tr[u].val); 
    }
    inline int newnode(const std::pair<int, int>& v)
    {
        int ret = top ? rec[top--] : ++cnt; // update mp here.
        return tr[ret] = {v, 0, 0, 0, gen_pri(rng), len(v)}, mp[v.first] = ret, ret;
    }
    inline int merge(int u, int v)
    {
        if (!u || !v) return u | v;
        if (tr[u].pri < tr[v].pri) return tr[u].rc = merge(tr[u].rc, v), pushup(u), u;
        else return tr[v].lc = merge(u, tr[v].lc), pushup(v), v;
    }
    inline std::array<int, 2> split_pos(int u, int pos)
    {
        std::array<int, 2> tmp = {0, 0};
        if (!u) return tmp;
        if (tr[tr[u].lc].sz >= pos)
        {
            tmp = split_pos(tr[u].lc, pos), tr[u].lc = tmp[1], tr[tmp[1]].fa = u, pushup(u);
            return {tmp[0], u};
        }
        else
        {
            tmp = split_pos(tr[u].rc, pos - tr[tr[u].lc].sz - len(tr[u].val));
            tr[u].rc = tmp[0], tr[tmp[0]].fa = u, pushup(u);
            return {u, tmp[1]};
        }
    }
    // after insert val, val at pos.
    inline void insert(int pos, const std::pair<int, int>& val) 
    {
        std::array<int, 2> tmp = split_pos(rt, pos - 1);
        int u = newnode(val);
        rt = merge(merge(tmp[0], u), tmp[1]);
    }
    inline void remove(const std::pair<int, int>& pos)
    {
        std::array<int, 2> tmp = split_pos(rt, pos.second);
        std::array<int, 2> sub = split_pos(tmp[0], pos.first - 1);
        rt = merge(sub[0], tmp[1]), recycle_full(sub[1]);
    }
    inline int kth(int u, int pos)
    {
        if (pos <= tr[tr[u].lc].sz) return kth(tr[u].lc, pos);
        pos -= tr[tr[u].lc].sz;
        if (pos <= len(tr[u].val)) return tr[u].val.first + pos - 1;
        else return kth(tr[u].rc, pos - len(tr[u].val));
    }
    // get counter that position <= node-id u (real pos of tr[u].val.second)
    inline int get_sum(int u)
    {
        int ret = tr[u].sz - tr[tr[u].rc].sz;
        if (u == rt) return ret;
        while (u ^ rt)
        {
            int f = tr[u].fa;
            if (!f) break;
            if (u == tr[f].rc) ret += tr[f].sz - tr[u].sz;
            u = f;
        }
        return ret;
    }
}
inline void init() { treap::insert(1, std::make_pair(1, n)); }
inline void make_top(int x)
{
    int l = (--mp.lower_bound(x + 1))->first, id = mp[l];
    int r = treap::tr[id].val.second;
    int pos = treap::get_sum(id) - (r - x); // query finish

    treap::remove(std::make_pair(pos - x + l, pos - x + r));
    if (x > l) treap::insert(pos - x + l, std::make_pair(l, x - 1));
    if (x < r) treap::insert(pos, std::make_pair(x + 1, r));
    treap::insert(1, std::make_pair(x, x));
}
inline int find_pos_by_num(int x)
{
    int l = (--mp.lower_bound(x + 1))->first, id = mp[l];
    int r = treap::tr[id].val.second;
    return treap::get_sum(id) - (r - x); // query finish
}
inline int find_num_by_pos(int x) { return treap::kth(treap::rt, x); }
inline void solve(int t)
{
    printf("Case %d:\n", t);
    n = rd(), m = rd(), init();
    while (m--)
    {
        op = rd_op(), x = rd();
        switch (op)
        {
        case 'T': make_top(x); break;
        case 'Q': wr(find_pos_by_num(x)), putchar('\n'); break;
        case 'R': wr(find_num_by_pos(x)), putchar('\n'); break;
        }
    }
}
int main()
{
    int T = rd();
    for (int t = 1; t <= T; ++t) treap::clr(), solve(t);
}