rt, 20pts, 记录

#include <cstdio>

using namespace std;

#define in __inline__
typedef long long ll;
in void swap(int &x, int &y) {x ^= y ^= x ^= y;}
#define rei register int
#define FOR(i, l, r) for(rei i = l; i <= r; ++i)
const int N = 1e5 + 15;
in int read() {
	int res = 0; register char ch = getchar(); bool f = true;
	for(; ch < '0' || ch > '9'; ch = getchar()) {
		if(ch == '-') f = false;
		if('a' <= ch && ch <= 'z' || 'A' <= ch && ch <= 'Z') return ch;
	}
	for(; ch >= '0' && ch <= '9'; ch = getchar())
		res = res * 10 + (ch ^ 48);
	return f ? res : -res;
}

unsigned long long seed = 1;
int fa[N], ch[N][2], tp[N], r[N], t[N], s[N], siz, rt, n;
char v[N];
bool alive[N];

in void upd(int p) {
	s[p] = s[ch[p][0]] + s[ch[p][1]] + 1;
	tp[p] = tp[ch[p][0]] | tp[ch[p][1]] | (1 << v[p] - 97);
	if(ch[p][0]) fa[ch[p][0]] = p;
	if(ch[p][1]) fa[ch[p][1]] = p;
}
in int New(char val) {
	r[++siz] = int(seed *= 20070509); v[siz] = val; s[siz] = 1;
	upd(siz); return siz;
}
in void push(int p) {
	if(!t[p]) return;
	swap(ch[p][0], ch[p][1]);
	t[ch[p][0]] ^= 1;
	t[ch[p][1]] ^= 1;
	t[p] = 0;
}
void push_rt_p(int p) {
	if(p ^ rt) push_rt_p(fa[p]);
	push(p);
}

int merge(int x, int y) {
	if(!x || !y) return x | y;
	return r[x] < r[y] ? (push(x), ch[x][1] = merge(ch[x][1], y), upd(x), x) :
		(push(y), ch[y][0] = merge(x, ch[y][0]), upd(y), y);
}
void split(int p, int sss, int& x, int& y) {
	if(!p) {x = y = 0; return;}
	push(p);
	sss > s[ch[p][0]] ? (x = p, split(ch[p][1], sss - s[ch[p][0]] - 1, ch[p][1], y)) :
		(y = p, split(ch[p][0], sss, x, ch[p][0]));
	fa[x] = fa[y] = 0;
	upd(p);
}

in void ins(int l, char val) {
	int x, y;
	split(rt, l, x, y);
	rt = merge(merge(x, New(val)), y);
}
in void erase(int l) {
	int x, y, z;
	split(rt, l, y, z);
	split(y, l - 1, x, y);
	alive[y] = true;
	rt = merge(x, z);
}
in void rev(int l, int r) {
	int x, y, z;
	split(rt, r, y, z);
	split(y, l - 1, x, y);
	t[y] ^= 1;
	rt = merge(merge(x, y), z);
}
in int pos(int p) {
	if(alive[p]) return 0;
	int res = s[ch[p][0]];
	push_rt_p(p);
	for(; fa[p]; p = fa[p]) if(ch[fa[p]][1] == p) res += s[ch[fa[p]][0]] + 1;
	return res + 1;
}
in char lth(int l) {
	int x, y, z;
	split(rt, l, y, z);
	split(y, l - 1, x, y);
	char res = v[y];
	rt = merge(merge(x, y), z);
	return res;
}
in int kind(int l, int r) {
	int x, y, z, k, res = 0;
	split(rt, r, y, z);
	split(y, l - 1, x, y);
	k = tp[y];
	rt = merge(merge(x, y), z);
	for(; k; k >>= 1) if(k & 1) ++res;
	return res;
}
void debug(int p) {
	push(p);
	if(ch[p][0]) debug(ch[p][0]);
	//putchar(v[p]);
	if(ch[p][1]) debug(ch[p][1]);
}

signed main() {
	char opt, c; int l, r, q;
	n = read(); q = read();
	FOR(i, 1, n) rt = merge(rt, New(read()));
	for(; q; --q) {
		opt = read();
		l = read();
		if(opt == 'I') {
			c = read();
			ins(l, c);
		} else if(opt == 'D') erase(l);
		else if(opt == 'R') {
			r = read();
			rev(l, r);
		} else if(opt == 'P') printf("%d\n", pos(l));
		else if(opt == 'T') printf("%c\n", lth(l));
		else if(opt == 'Q') {
			r = read();
			printf("%d\n", kind(l, r));
		}
		//debug(rt);
	}
	return 0;
}

和题解对了半天也找不出问题/kk