WA on #2,3,5,7~10

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=1e6+10;

int n;

struct Decompose
{
	int len,id[MAXN],a[MAXN],b[MAXN],lazy[1010],l[1010],r[1010],tot;
	
	void build()
	{
		tot=sqrt(n);
		for(int i=1;i<=tot;i++)
		{
			l[i]=n/tot*(i-1)+1;
			r[i]=n/tot*i;
		}
		r[tot]=n;
		for(int i=1;i<=tot;i++)
		{
			for(int j=l[i];j<=r[i];j++)id[j]=i;
		}
	}
	
	void sort(int x)
	{
		for(int i=l[x];i<=r[x];i++)b[i]=a[i];
		std::sort(b+l[x],b+r[x]+1);
	}
	
	void add(int al,int ar,int d)
	{
		int lid=id[al],rid=id[ar];
		if(lid==rid)
		{
			for(int i=al;i<=ar;i++)a[i]+=d;
			sort(lid);
			return;
		}
		for(int i=al;i<=r[lid];i++)a[i]+=d;
		for(int i=lid+1;i<rid;i++)lazy[i]+=d;
		for(int i=l[rid];i<=ar;i++)a[i]+=d;
		sort(lid);
		sort(rid);
	}
	
	int query(int al,int ar,int d)
	{
		int lid=id[al],rid=id[ar],ret=0;
		if(lid==rid)
		{
			for(int i=al;i<=ar;i++)
			{
				if(a[i]+lazy[lid]>=d)ret++;
			}
			return ret;
		}
		for(int i=al;i<=r[lid];i++)
		{
			if(a[i]+lazy[lid]>=d)ret++;
		}
		for(int i=lid+1;i<rid;i++)
		{
			ret+=r[i]-(lower_bound(b+l[i],b+r[i]+1,d-lazy[i])-b)+1;
		}
		for(int i=l[rid];i<=ar;i++)
		{
			if(a[i]+lazy[rid]>=d)ret++;
		}
		return ret;
	}
}A;

signed main()
{
	int q;
	cin>>n>>q;
	for(int i=1;i<=n;i++)cin>>A.a[i];
	A.build();
	while(q--)
	{
		char op;
		int l,r,c;
		cin>>op>>l>>r>>c;
		if(op=='M')A.add(l,r,c);
		else cout<<A.query(l,r,c)<<'\n';
	}
	return 0;
}