蒟蒻刚学 OI 2600ms ，问大佬这道题怎么优化啊

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define max(x,y) (x>y?x:y)
#define min(x,y) (x<y?x:y)
#define EDGE 2000000001LL

inline ll read(){
    ll s(0),w(1); char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') w=-1; ch=getchar();}
    while (ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^'0'), ch=getchar();
    return s*w;
}

void write(ll s){
    if (s<0) s=-s, putchar('-');
    if (s>9) write(s/10);
    putchar(s%10+'0');
}

void writeln(ll s){
    write(s); putchar('\n');
}

void writeln(){
    putchar('\n');
}

struct Data{
    ll val,ind;
}a[192608];

ll tag[192608],add[1926],l[1926],r[1926],n,m,bsize,t;

bool cmp(Data p,Data q){
    return p.val<q.val;
}

inline void bsort(const ll &p){  //p*log(p)
    sort(a+l[p],a+r[p]+1,cmp);
}

inline void init(){ // n*log(p)
    bsize = ceil(sqrt(n)); if (n%bsize==0) t = n/bsize; else t = n/bsize+1;
    for (register int i(0);i<n;i++){
        a[i].ind = i; tag[i] = i/bsize;
        if (i%bsize==0) l[tag[i]] = i;
        if ((i+1)%bsize==0||i==n-1) r[tag[i]] = i; 
    }
    for (register int i(0);i<t;i++){
        add[i] = 0; bsort(i);
    }
}

inline void update(const ll &L,const ll &R,const ll &x){ // p*log(p)
    if (tag[L]==tag[R]){
        for (register int i(l[tag[L]]);i<=r[tag[L]];i++){
            if (a[i].ind>=L&&a[i].ind<=R) a[i].val+=x;
        }
        bsort(tag[L]);
    }else{
        for (register int i(l[tag[L]]);i<=r[tag[L]];i++){
            if (a[i].ind>=L&&a[i].ind<=R) a[i].val+=x;
        }
        for (register int i(r[tag[R]]);i>=l[tag[R]];i--){
            if (a[i].ind>=L&&a[i].ind<=R) a[i].val+=x;
        }
        for (register int i(tag[L]+1);i<=tag[R]-1;i++) add[i]+=x;
        bsort(tag[L]); bsort(tag[R]);
    }
}

inline ll bsearch(ll p,ll x){ // log(p)
    ll L(l[p]), R(r[p]);
    while (L<R){
        ll MID((L+R)/2);
        if (a[MID].val+add[tag[MID]]<=x) L = MID+1; else R = MID;
    }
    return L-l[p];
}

inline ll ssearch(ll p,ll L,ll R,ll x){ // p
    ll ret(0);
    for (register int i(l[p]);i<=r[p];i++){
        if (a[i].val+add[tag[i]]<=x&&a[i].ind>=L&&a[i].ind<=R) ret++;
    }
    return ret;
}

inline ll search(ll L,ll R,ll k){ // log(EDGE)*p*log(p)
    ll _L(-EDGE), _R(EDGE);
    while (_L<_R){
        ll _MID((_L+_R)/2), ans(0);
        if (tag[L]==tag[R]){
            ans += ssearch(tag[L],L,R,_MID);
        }else{
            ans += ssearch(tag[L],L,R,_MID);
            ans += ssearch(tag[R],L,R,_MID);
            for (register int i(tag[L]+1);i<=tag[R]-1;i++) ans += bsearch(i,_MID);
        }
        if (ans<k) _L = _MID+1; else _R = _MID; 
    }
    return _L;
}

inline ll query(ll L,ll R,ll k){ // log(EDGE)*(p+log(p))
    if (k<1||R-L+1<k) return 0;
    return search(L,R,k);
}

int main(){
    ios::sync_with_stdio(false);
    n = read(); m = read();
    for (register int i=0;i<n;i++) a[i].val = read();
    init();
    for (register int i=1;i<=m;i++){ // m*p*log(p) && m*log(EDGE)*p*log(p)
        ll opt,L,R,k; opt = read(); L = read()-1; R = read()-1; k = read();
        if (opt==1){
            writeln(query(L,R,k));
        }else{
            update(L,R,k);
        }
    } 
    return 0;
}