思路：搞搞平衡树。

#include
     
      #define LL long long#define fi first#define se second#define mk make_pair#define PII pair
      
       #define y1 skldjfskldjg#define y2 skldfjsklejgusing namespace std;const int N = 4e5 + 7;const int M = 5e5 + 7;const int inf = 0x3f3f3f3f;const LL INF = 0x3f3f3f3f3f3f3f3f;const int mod = 45989;const int B = 1e5;int val[N], hs[N], n, m;char s[10];struct node {    node* ch[2];    int key, fix, sz, cnt;    void update() {        sz = ch[0]->sz + ch[1]->sz + cnt;    }};typedef node* P_node;struct Treap {    node base[N], nil;    P_node root, null, len;    Treap() {        root = null = &nil;        null->key = null->fix = 1e9;        null->sz = null->cnt = 0;        null->ch[0] = null->ch[1] = null;        len = base;    }    P_node newnode(int tkey) {        len->key = tkey;        len->fix = rand();        len->ch[0] = len->ch[1] = null;        len->sz = len->cnt = 1;        return len++;    }    void rot(P_node &p, int d) {        P_node k = p->ch[d ^ 1];        p->ch[d ^ 1] = k->ch[d];        k->ch[d] = p;        p->update();        k->update();        p = k;    }    void _Insert(P_node &p, int tkey) {        if(p == null) {            p = newnode(tkey);        } else if(p->key == tkey) {            p->cnt++;        } else {            int d = tkey > p->key;            _Insert(p->ch[d], tkey);            if(p->ch[d]->fix > p->fix) {                rot(p, d ^ 1);            }        }        p->update();    }    void _Delete(P_node &p, int tkey) {        if(p == null) return;        if(p->key == tkey) {            if(p->cnt > 1) p->cnt--;            else if(p->ch[0] == null) p = p->ch[1];            else if(p->ch[1] == null) p = p->ch[0];            else {                int d = p->ch[0]->fix > p->ch[1]->fix;                rot(p, d);                _Delete(p->ch[d], tkey);            }        } else {            _Delete(p->ch[tkey > p->key], tkey);        }        p->update();    }    int _Kth(P_node p, int k) {        if(p == null || k < 1 || k > p->sz) return 0;        if(k < p->ch[0]->sz + 1) return _Kth(p->ch[0], k);        if(k > p->ch[0]->sz + p->cnt) return _Kth(p->ch[1], k - p->ch[0]->sz - p->cnt);        return p->key;    }    int _Rank(P_node p, int tkey, int res) {        if(p == null) return -1;        if(p->key == tkey) return p->ch[0]->sz + res + 1;        if(tkey < p->key) return _Rank(p->ch[0], tkey, res);        return _Rank(p->ch[1], tkey, res + p->ch[0]->sz + p->cnt);    }    int _Pred(P_node p, int tkey){        if(p == null) return -1e9;        if(tkey <= p->key) return _Pred(p->ch[0], tkey);        return max(p->key, _Pred(p->ch[1], tkey));    }    int _Succ(P_node p, int tkey){        if(p == null) return 1e9;        if(tkey >= p->key) return _Succ(p->ch[1], tkey);        return min(p->key, _Succ(p->ch[0], tkey));    }    void Insert(int tkey){ _Insert(root,tkey); }    void Delete(int tkey){ _Delete(root,tkey); }    int Kth(int k){ return _Kth(root,k); }    int Rank(int tkey){ return _Rank(root,tkey,0); }    int Pred(int tkey){ return _Pred(root,tkey); }    int Succ(int tkey){ return _Succ(root,tkey); }}tp;int main() {    scanf("%d%d", &n, &m);    int mx = n + B, mn = 1 + B;    for(int i = 1; i <= n; i++) {        int x; scanf("%d", &x);        val[x] = i + B;        hs[i + B] = x;        tp.Insert(i + B);    }    while(m--) {        int id, t;        scanf("%s", s);        if(s[0] == 'T') {            scanf("%d", &id);            tp.Delete(val[id]);            val[id] = --mn;            hs[mn] = id;            tp.Insert(val[id]);        } else if(s[0] == 'B') {            scanf("%d", &id);            tp.Delete(val[id]);            val[id] = ++mx;            hs[mx] = id;            tp.Insert(val[id]);        } else if(s[0] == 'I') {            scanf("%d%d", &id, &t);            if(t == 1) {                int z = tp.Succ(val[id]);                if(z < -100000000 || z > 100000000) continue;                int id2 = hs[z], v = val[id];                swap(val[id], val[id2]);                swap(hs[v], hs[z]);            } else if(t == -1) {                int z = tp.Pred(val[id]);                if(z < -100000000 || z > 100000000) continue;                int id2 = hs[z], v = val[id];                swap(val[id], val[id2]);                swap(hs[v], hs[z]);            }        } else if(s[0] == 'A'){            scanf("%d", &id);            printf("%d\n", tp.Rank(val[id]) - 1);        } else {            scanf("%d", &id);            printf("%d\n", hs[tp.Kth(id)]);        }    }    return 0;}