RT O2: 最后两点AC 其余MLE 求助

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int n;
int T,L;
struct Node{
	int w,id;
	bool operator < (const Node & buf) const{
		return w<buf.w;
	}
} a[10000001];
int BEGIN(int p){return L*(p-1)+1;}
int END(int p){return min(L*p,n);}
int NUM(int p){return ceil(double(p)/L);} 
int LENGTH(int p){
	if(END(p)==n) return n-(T-1)*L;
	else return L;
}
void Prework(){
	T=ceil(sqrt(double(n))),L=ceil(double(n)/T);
	for(int i=1;i<=T;i++) sort(a+BEGIN(i),a+END(i)+1);
}
void change(int ind,int c){
	for(int i=BEGIN(NUM(ind));i<=END(NUM(ind));++i) if(a[i].id==ind) a[i].w=c;
	sort(a+BEGIN(ind),a+END(ind)+1);
}
int query(int l,int r,int k){
	int ans=0;
	for(int i=BEGIN(NUM(l));i<=END(NUM(l))&&i<=r;++i) if(a[i].id>=l&&a[i].id<=r&&a[i].w==k) ans++;
	if(NUM(l)!=NUM(r)) for(int i=END(NUM(r));i>=BEGIN(NUM(r))&&i>=l;--i) if(a[i].id>=l&&a[i].id<=r&&a[i].w==k) ans++;
	for(int i=NUM(l)+1;i<NUM(r);i++) ans+=upper_bound(a+BEGIN(i),a+END(i)+1,(Node){k,0})-lower_bound(a+BEGIN(i),a+END(i)+1,(Node){k,0});
	return ans;
}

int Q;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>Q;
	for(int i=1;i<=n;i++) cin>>a[i].w,a[i].id=i;
	Prework();
	while(Q--){
		char opt;int l,r,w;
		cin>>opt>>l>>r;
		if(opt=='C') change(l,r);
		if(opt=='Q') cin>>w,cout<<query(l,r,w)<<'\n';
	}
}