WA on #1 #11

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#define ll long long

using namespace std;

const ll P=998244353;
const ll inv=299473306;

int n, q, B;
ll a[1000010],base[1000010];
vector<int> b;

void update(int l, int r, ll c){
    int idl = l/B, idr = r/B;
    if (idl==idr){
        for (int i = l; i <= r; i++){
            a[i]+=c;
            b[i]=a[i];
        }
        sort(b.begin()+idl*B, b.begin()+(idl+1)*B);
    } else{
        for (int i = l; i < (idl+1)*B; i++){
            a[i]+=c;
            b[i]=a[i];
        }
        sort(b.begin()+idl*B, b.begin()+(idl+1)*B);
        for (int i = idr*B; i <= r; i++){
            a[i]+=c;
            b[i]=a[i];
        }
        sort(b.begin()+idr*B, b.begin()+(idr+1)*B);
        for (int i = idl+1; i < idr; i++) base[i]+=c;
    }
}

ll query(int l, int r, ll c){
    ll cnt = 0;
    int idl = l/B, idr = r/B;
    if (idl==idr){
        for (int i = l; i <= r; i++)
            if (a[i]+base[idl]>=c) cnt++;
    } else{
        for (int i = l; i < (idl+1)*B; i++)
            if (a[i]+base[idl]>=c) cnt++;
        for (int i = idr*B; i <= r; i++)
            if (a[i]+base[idr]>=c) cnt++;
        for (int i = idl+1; i < idr; i++)
            cnt+=B-(lower_bound(b.begin()+i*B, b.begin()+(i+1)*B, c-base[i])-(b.begin()+i*B));
    }
    return cnt;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>q;
	B=sqrt(n);
	for (int i = 0; i < n; i++){
	    cin>>a[i];
	    b.push_back(a[i]);
	}
	for (int i = 0; i <= (n-1)/B; i++) sort(b.begin()+i*B, b.begin()+min((i+1)*B, n));
	while(q--) {
	    char op; int l, r; ll c;
	    cin>>op>>l>>r>>c;
	    l--; r--;
	    if (op=='M') update(l,r,c);
	    else cout<<query(l,r,c)<<'\n';
	}
	return 0;
}