阳历已过

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

const int N = 1e5+75;

int n , m , a[N] , lsh[N*6] , lt(0);

struct Query__ {
	char op;
	int ls , rs , kp;
}p[N*2];

int node(0) , root[N*3];	

struct Tree_Node {
	int l , r , pre;
}t[N*60];

int Lb (int x)
{
	return x & (-x);
}

int New (int x = 0)
{
	++ node;
	t[node] = t[x];
	return node;
}

int Update (int x , int l , int r , int k , int val)
{
	if(!x) x = New ();
	t[x].pre += val;
	if(l == r) return x;
	int mid = (l+r)/2;
	if(k <= mid) t[x].l = Update (t[x].l , l , mid , k , val);
	if(mid+1 <= k) t[x].r = Update (t[x].r , mid+1 , r , k , val);
	return x;
}

void Modify (int tp , int val)
{
	int pos = lower_bound (lsh+1 , lsh+1+lt , a[tp]) - lsh;
	for(int i = tp ; i <= lt ; i += Lb (i))
	{
		root[i] = Update (root[i] , 1 , lt , pos , val);
	}
	return;
}

int Query (int x , int l , int r , int k)
{
	if(l == r) return t[x].pre;
	int mid = (l+r)/2;
	if(k <= mid) return Query (t[x].l , l , mid , k);
	else return Query (t[x].r , mid+1 , r , k);
}

int Ask (int rx , int lx , int k)
{
	int ans (0);
	k = lower_bound (lsh+1 , lsh+1+lt , k) - lsh;
	for(int i = lx-1 ; i ; i -= Lb (i))
	{
		ans -= Query (root[i] , 1 , lt , k);
	}
	for(int i = rx ; i ; i -= Lb (i))
	{
		ans += Query (root[i] , 1 , lt , k);
	}
	return ans;
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i = 1 ; i <= n ; i ++)
	{
		scanf("%d",&a[i]);
		lsh[++ lt] = a[i];
	}
	for(int i = 1 ; i <= m ; i ++)
	{
		cin >> p[i].op;
		if(p[i].op == 'C')
		{
			scanf("%d%d",&p[i].ls,&p[i].kp);
			p[i].rs = p[i].ls;
			lsh[++ lt] = p[i].kp;
		}
		else 
		{
			scanf("%d%d%d",&p[i].ls,&p[i].rs,&p[i].kp);
			lsh[++ lt] = p[i].kp;
		}
	}
	sort (lsh+1 , lsh+1+lt);
	lt = unique (lsh+1 , lsh+1+lt) - lsh - 1;
	
	for(int i = 1 ; i <= n ; i ++)
	{
		Modify (i , 1);
	}
	
	for(int i = 1 ; i <= m ; i ++)
	{
		const Query__ &now = p[i];
		if(now.op == 'C')
		{
			Modify (p[i].ls , -1);
			a[p[i].ls] = p[i].kp;
			Modify (p[i].ls , 1);
		}
		if(now.op == 'Q')
		{
			printf("%d\n",Ask(p[i].rs,p[i].ls,p[i].kp));
		}
	}
	
	return 0;
}