树套bitset

#include<bits/stdc++.h>

#define endl '\\n'

#define pb push\_back

#define pp pop\_back

#define debug1(x) cout << #x << " = " << (x) << '\\n'

#define debug2(x) cout << #x << " = " << (x) << ' '

//#define x first

//#define y second

using namespace std;

typedef long long ll;

typedef pair<int, int> PII;

const int N = 1e4+5, M = 1e6+5;

const int MOD = 998244353, INF = 0x3f3f3f3f;

int n, m, w[N];

vector<int> v;

int get(int x) {

	return lower\_bound(v.begin(), v.end(), x) - v.begin();

}

struct Node {

	int l, r;

	bitset<11000> t;

} tr[N << 2];

void build(int u, int l, int r) {

	tr[u] = {l, r};

	if(l == r) return ;

	int mid = l + r >> 1;

	build(u << 1, l, mid);

	build(u << 1 | 1, mid + 1, r);

}

void pushup(int u, int x) {

	tr[u].t[x] = tr[u << 1].t[x] | tr[u << 1 | 1].t[x];

}

void modify(int u, int p, int x, int op) {

	if(tr[u].l == tr[u].r) {

		if(op == 0) tr[u].t[x] = 1;

		else tr[u].t[x] = 0;

		return ;

	}

	int mid = tr[u].l + tr[u].r >> 1;

	if(p <= mid) modify(u << 1, p, x, op);

	else modify(u << 1 | 1, p, x, op);

	pushup(u, x);

}

bitset<11000> query(int u, int l, int r) {

	if(l <= tr[u].l && tr[u].r <= r) return tr[u].t;

	int mid = tr[u].l + tr[u].r >> 1;

	bitset<11000> ans;

	if(l <= mid) ans |= query(u << 1, l, r);

	if(r > mid) ans |= query(u << 1 | 1, l, r);

	return ans;

}

struct Query {

	char opt;

	int x, y;

} Q[N];

void solve() {

	cin >> n >> m;

	for(int i = 1; i <= n; i ++) {

		cin >> w[i];

		v.push\_back(w[i]);

	}

	for(int i = 1; i <= m; i ++) {

		cin >> Q[i].opt >> Q[i].x >> Q[i].y;

		if(Q[i].opt == 'R') v.push\_back(Q[i].y);

	}


	sort(v.begin(), v.end());

	v.erase(unique(v.begin(), v.end()), v.end());

	build(1, 1, n);

	for(int i = 1; i <= n; i ++) modify(1, i, get(w[i]), 0);

	for(int i = 1; i <= m; i ++) {

		if(Q[i].opt == 'Q') cout << query(1, Q[i].x, Q[i].y).count() << endl;

		else if(Q[i].opt == 'R') {

			modify(1, Q[i].x, get(w[Q[i].x]), 1);

			w[Q[i].x] = Q[i].y;

			modify(1, Q[i].x, get(w[Q[i].x]), 0);

		}

	}

}



int main() {

	ios::sync\_with\_stdio(false);

	cin.tie(nullptr), cout.tie(nullptr);

	int t = 1;

	//cin >> t;

	while(t --) solve();


	return 0;

}