TLE50 on 4-8 救救萌新

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

int n,q,sq;
int a[1000009];
int bel[1000009];
int st[1009];
int ed[1009];
int lazy[1009];
vector<int> ve[1010];

void re(int v)
{
    ve[v].clear();
    for(int i = st[v]; i <= ed[v]; i++)
    {
        ve[v].push_back(a[i]);
    }
    sort(ve[v].begin(),ve[v].end());
}

void add(int l, int r, int k)
{
    if(bel[l]==bel[r])
    {
        for(int i = l; i <= r; i++)
        {
            a[i]+=k;

        }
    }
    else{
        for(int i = l; i <= ed[bel[l]]; i++)
        {
            a[i]+=k;
        }
        for(int i = bel[l]+1; i < bel[r]; i++)
        {
            lazy[i]+=k;
        }
        for(int i = st[bel[r]]; i <= r; i++)
        {
            a[i]+=k;
        }
    }
}
int query(int l, int r, int k)
{
    int ans=0;
    if(bel[l]==bel[r])
    {
        for(int i = l; i <= r; i++)
        {
            if(a[i]+lazy[bel[i]]<k)ans++;
        }
    }else{
        for(int i = l; i <= ed[bel[l]]; i++)
        {
            if(a[i]+lazy[bel[i]]<k)ans++;
        }
        for(int i = bel[l]+1; i < bel[r]; i++)
        {
            re(i);
            vector<int>::iterator be=ve[i].begin();
            if(ve[i].back()>=k)ans+=lower_bound(be,ve[i].end(),k-lazy[i])-be;
        }
        for(int i = st[bel[r]]; i <= r; i++)
        {
            if(a[i]+lazy[bel[i]]<k)ans++;
        }
    }
    return r-l+1-ans;
}
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int main()
{
    cin >> n >> q;
    for(int i = 1; i <= n; i++)a[i]=read();
    sq=sqrt(n);
    for(int i = 1; i <= sq; i++)
    {
        st[i]=n/sq*(i-1)+1;
        ed[i]=n/sq*i;
    }
    ed[sq]=n;
    for(int i = 1; i <= sq; i++)
    {
        for(int j = st[i]; j <= ed[i]; j++)
        {
            bel[j]=i;
        }
    }
    while(q--)
    {
        char opt;
        int l,r,k;
        getchar();
        opt=getchar();
        l=read();
        r=read();
        k=read();
        if(opt=='M')
        {
            add(l,r,k);
        }
        if(opt=='A')
        {
            cout << query(l,r,k) << endl;
        }
    }
}

自认为码风非常正常，已经尽量卡常了,复杂度似乎也没有问题，但是不很确定。求各位大佬帮助！