分块

#include<bits/stdc++.h>
#define int long long
#define PII pair<int,int>
#define ULL unsigned long long
#define all(v) v.begin(), v.end()
#define debug(a) cout<<#a<<"="<<a<<endl;
using namespace std;
constexpr int N =  1 * 1e6 + 10,M = 5 * 1e3 + 10,inf = 0x3f3f3f3f;

int n,m;
int a[N],st[N],ed[N],t[N],belong[N],b[N],len,tot;
void tsort(int k)
{
    for(int i=st[k];i<=ed[k];i++) t[i] = a[i];
    sort(t+st[k],t+ed[k]+1);
}
void build()
{
    len = sqrt(n);
    tot = n / len;
    if(n % len) tot ++;
    for(int i=1;i<=n;i++)
    {
        belong[i] = (i-1) / len + 1;
        t[i] = a[i];
    }
    for(int i=1;i<=tot;i++)
    {
        st[i] = (i-1) * len + 1;
        ed[i] = i * len;
    }
    ed[tot] = n;
    for(int i=1;i<=tot;i++)
    sort(t+st[i],t+ed[i]+1);
}
void modify(int l,int r,int w)
{
    int x = belong[l] , y = belong[r];
    if(x == y)
    {
        for(int i=l;i<=r;i++) a[i] += w;
        tsort(x);
        return;
    }

    for(int i=l;i<=ed[x];i++) a[i] += w;
    tsort(x);
    for(int i=st[y];i<=r;i++) a[i] += w;
    tsort(y);
    for(int i=x+1;i<y;i++) b[i] += w;
}
int query(int l,int r,int c)
{
    int x = belong[l] , y = belong[r];
    int res = 0;
    if(x == y)
    {
        for(int i=l;i<=r;i++) if(a[i] >= c - b[x]) res ++;
        return res;
    }

    for(int i=l;i<=ed[x];i++) if(a[i] >= c - b[x]) res ++;
    for(int i=st[y];i<=r;i++) if(a[i] >= c - b[y]) res ++;
    for(int i=x+1;i<=y-1;i++)
    {
        res += ed[i] - (lower_bound(t + st[i] , t + ed[i] + 1 , c - b[i]) - t) + 1;
    }
    return res;
}
void solve()
{
    cin >> n >> m;
    for(int i=1;i<=n;i++) cin >> a[i];
    build();
    while(m--)
    {
        char op[2];
        int l,r,x;
        cin >> op >> l >> r >> x;
        if(*op == 'M') modify(l,r,x);
        else cout << query(l,r,x) << '\n';
    }
}
signed main()
{
    ios::sync_with_stdio(0);cin.tie(nullptr),cout.tie(nullptr);
    int _=1;
    // cin>>_;
    while(_--)
    {
        solve();
    }
    return 0;
}

/**
 *    author: Nijika_jia
 *    created: 2024.10.29 22:09:45
 */