题解：P5217 贫穷

· · 题解

注意到只有小写字母，可以开一个 26 \times N 的数组记一下出现次数，查询的时候遍历 26 次即可。

唯一难点其实就是 4 操作，不难发现实际求的就是编号为 x 在现在树上的排名是多少，然后变成文艺平衡树上求排名。

FHQ 上只需要记一个父亲，一直往上跳。如果跳到了一条从左连到右的边，也就是当前节点为父亲的右子节点，就统计父亲左子树大小。这个很显然，中序遍历中肯定先走左边，统计的就是要走多少次走到 x，复杂度为深度，期望 O(\log n)。

::::info[Code]

#include <bits/stdc++.h>
using namespace std;

bool st;

const int N = 5e5 + 5;

mt19937 rnd;
int n, m;

int tot, rt, fa[N], ch[N][2], siz[N], rnk[N], sum[N][27], val[N], tag[N];
bool vis[N];
int addNode (int value) {
    ++tot;
    siz[tot] = 1;
    sum[tot][value] = 1;
    val[tot] = value;
    tag[tot] = 0;
    rnk[tot] = rnd ();
    return tot;
}
void pushup (int node) {
    siz[node] = siz[ch[node][0]] + siz[ch[node][1]] + 1;
    for (int i = 1; i <= 26; ++i) sum[node][i] = sum[ch[node][0]][i] + sum[ch[node][1]][i] + (val[node] == i);
    if (ch[node][0]) fa[ch[node][0]] = node;
    if (ch[node][1]) fa[ch[node][1]] = node;
}
void pushdown (int node) {
    if (tag[node]) {
        swap (ch[node][0], ch[node][1]);
        tag[ch[node][0]] ^= 1; tag[ch[node][1]] ^= 1;
        tag[node] = 0;
    }
}
void split (int node, int v, int &x, int &y) {
    if (!node) {
        x = y = 0;
        return ;
    }
    pushdown (node);
    if (siz[ch[node][0]] + 1 <= v) {
        x = node;
        split (ch[node][1], v - siz[ch[node][0]] - 1, ch[node][1], y);
    } else {
        y = node;
        split (ch[node][0], v, x, ch[node][0]);
    }
    pushup (node);
}
int merge (int x, int y) {
    if (!x || !y) return x | y;
    pushdown (x), pushdown (y);
    if (rnk[x] < rnk[y]) {
        ch[x][1] = merge (ch[x][1], y);
        pushup (x);
        return x;
    } else {
        ch[y][0] = merge (x, ch[y][0]);
        pushup (y);
        return y;
    }
}
void Insert (int pos, int value) {
    int x, y;
    split (rt, pos, x, y);
    rt = merge (merge (x, addNode (value)), y);
}
void Remove (int pos) {
    int x, y, z;
    split (rt, pos, x, z);
    split (x, pos - 1, x, y);
    vis[y] = true;
    y = merge (ch[y][0], ch[y][1]);
    rt = merge (merge (x, y), z);
}
void Reverse (int l, int r) {
    int x, y, z;
    split (rt, r, x, z);
    split (x, l - 1, x, y);
    tag[y] ^= 1;
    rt = merge (merge (x, y), z);
}
int kth (int k) {
    int x, y, z, ret;
    split (rt, k, x, z);
    split (x, k - 1, x, y);
    ret = val[y];
    rt = merge (merge (x, y), z);
    return ret;
}
int Query (int l, int r) {
    int x, y, z, ret = 0;
    split (rt, r, x, z);
    split (x, l - 1, x, y);
    for (int i = 1; i <= 26; ++i) if (sum[y][i]) ret++; // 暴力带个 26 的常数
    rt = merge (merge (x, y), z);
    return ret;
} 
void Pushdown (int node) {
    if (fa[node]) Pushdown (fa[node]);
    pushdown (node);
}
int Rnk (int node) {
    Pushdown (node); // 记得先传标记
    int ans = siz[ch[node][0]] + 1;
    while (fa[node]) {
        if (ch[fa[node]][1] == node) ans += siz[ch[fa[node]][0]] + 1;
        node = fa[node];
    }
    return ans;
}

bool ed;

int main () {

    ios::sync_with_stdio (false);
    cin.tie (0); cout.tie (0);

    cerr << "[Memory] " << (&st - &ed) / 1024 / 1024 << " MB\n";

    srand (time (0));
    rnd.seed (rand () ^ time (0));

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        char ch1; cin >> ch1;
        int num = ch1 - 'a' + 1;
        rt = merge (rt, addNode (num));
    }

    while (m--) {
        char ch1;
        cin >> ch1;
        if (ch1 == 'I') {
            int x; char c;
            cin >> x >> c;
            Insert (x, c - 'a' + 1);
        } else if (ch1 == 'D') {
            int x; cin >> x;
            Remove (x);
        } else if (ch1 == 'R') {
            int x, y; cin >> x >> y;
            Reverse (x, y);
        } else if (ch1 == 'P') {
            int x; cin >> x;
            if (vis[x]) cout << 0 << '\n';
            else cout << Rnk (x) << '\n';
        } else if (ch1 == 'T') {
            int x; cin >> x;
            cout << (char)(kth (x) + 'a' - 1) << '\n';
        } else {
            int x, y; cin >> x >> y;
            cout << Query (x, y) << '\n';
        }
    }

    return 0;
}

::::