SHTARR

#include "bits/stdc++.h"
using namespace std;

ofstream OUT ("C:\\Users\\Anushi Maheshwari\\Documents\\CodeChef\\Checker\\Wrong.txt");
ifstream fin ("C:\\Users\\Anushi Maheshwari\\Documents\\CodeChef\\Test\\Test.out");
ofstream fout ("Out");

#define N 1000010
#define BS 1000
#define NBS 1000

int n;
int a[N];
int l,r,x;
int block[NBS+5][BS+5];
int len[NBS+5];
int kk[BS+5];
int it,it2;
bitset<NBS+5> lazy;
int cnt;

void block_processor(int id){
    cnt++;
    lazy[id]=0,len[id]=0;

    int l=id*BS;
    if(l>=n) return;
    int r=max(n,l+BS);

    block[id][len[id]++]=a[l];
    for(int i=l;i<r;i++){
        if(a[i]>a[len[id]-1]){
            block[id][len[id]++]=a[i];
        }
    }
}

int start(){
    int low=x;
    int bid=(x/BS);
    int high=max(n,(bid+1)*BS);
    int sz=0;
    for(int i=low;i<high;i++){
        if(a[i]>=l){
            //cout<<a[i]<<":"<<kk.size()<<" ";
            l=a[i]+1;
            kk[sz++]=a[i];
            if(l>r) break;
        }
    }
    //cout<<kk.size()<<endl;
    return sz;
}

int query(int id){
    int sz=len[id];
    if(sz==0 || block[id][sz-1]<=l || (l>r)) return 0;
    if(block[id][sz-1]<=r && block[id][0]>=l) {l=block[id][sz-1]+1;return sz;}
    it=lower_bound(block[id],block[id]+sz,r)-block[id];
    it2=lower_bound(block[id],block[id]+sz,l)-block[id];
    l=block[id][it]+1;
    return it-it2+1;
}

int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    clock_t sta=clock();
    cnt=0;
    int t,q,ans;
    char ty;
    fin>>t;
    while(t--){
        fin>>n>>q;
        for(int i=0;i<n;i++) fin>>a[i];
        for(int i=0;i<NBS;i++) block_processor(i);
        while(q--){
            fin>>ty>>x>>l;--x;
            if(ty=='+'){
                a[x]+=l;
                block_processor((int)(x/BS));
            }
            else{
                fin>>r;
                ans=start();
                for(int i=int(x/BS)+1;i<1000;i++)
                 ans+=query(i);
                OUT<<ans<<endl;
            }
        }
    }
    cout<<(double)((double)(clock()-sta)/CLOCKS_PER_SEC)<<" "<<cnt;
    return 0;
}