全TLE求助

#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll MAXN=1e5+5;
ll n,m;
ll op,x,y,z,blen;
struct block{
	ll b_l,b_r,lazy_add;
}b[MAXN];
ll b_id[MAXN];
ll cnt;
struct node{
	ll num,id;
	bool operator == (const node &oth)const{
		return num==oth.num;
	}
}a[MAXN];
bool cmp_num(node n1,node n2){
	return n1.num<n2.num;
}
bool cmp_id(node n1,node n2){
	return n1.id<n2.id;
}
ll count(ll L,ll R,ll X){
	ll res=upper_bound(a+L,a+R+1,(node){X,0},cmp_num)-a-1;
    return (ll)res;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i].num;
		a[i].id=i;
	}
	blen=sqrt(n);
	for(int i=1;i<=n;i+=blen)b[++cnt]=(block){i,min(i+blen-1,n),0};
	for(int i=1;i<=cnt;i++)for(int j=b[i].b_l;j<=b[i].b_r;j++)b_id[j]=i;
	for(int i=1;i<=cnt;i++)sort(a+b[i].b_l,a+b[i].b_r+1,cmp_num);
    for(int i=1;i<=m;i++){
        cin>>op>>x>>y>>z;
        if(op==2){
            if(b_id[x]==b_id[y]){
                sort(a+b[b_id[x]].b_l,a+b[b_id[x]].b_r+1,cmp_id);
                for(int i=x;i<=y;i++)a[i].num+=z;
                sort(a+b[b_id[x]].b_l,a+b[b_id[x]].b_r+1,cmp_num);
            }
            else{
                for(int i=b_id[x]+1;i<b_id[y];i++)b[i].lazy_add+=z;
                sort(a+b[b_id[x]].b_l,a+b[b_id[x]].b_r+1,cmp_id);
                for(int i=x;i<=b[b_id[x]].b_r;i++)a[i].num+=z;
                sort(a+b[b_id[x]].b_l,a+b[b_id[x]].b_r+1,cmp_num);
                sort(a+b[b_id[y]].b_l,a+b[b_id[y]].b_r+1,cmp_id);
                for(int i=b[b_id[y]].b_l;i<=y;i++)a[i].num+=z;
                sort(a+b[b_id[y]].b_l,a+b[b_id[y]].b_r+1,cmp_num);
            }
        }
        else{
            if(b_id[x]==b_id[y]){
                sort(a+b[b_id[x]].b_l,a+b[b_id[x]].b_r+1,cmp_id);
                cout<<a[x+z-1].num<<'\n';
                sort(a+b[b_id[x]].b_l,a+b[b_id[x]].b_r+1,cmp_num);
                continue;
            }
            ll L=-4e9,R=4e9,mid=0,ans=0;
//            for(int i=b_id[x];i<=b_id[y];i++)L=min(L,a[b[i].b_l].num+b[i].lazy_add),R=max(R,a[b[i].b_r].num+b[i].lazy_add);
            while(L<=R){
                mid=(L+R)>>1;
                ll s=0;
                for(int i=b_id[x]+1;i<b_id[y];i++)s+=count(b[i].b_l,b[i].b_r,mid-b[i].lazy_add);
                sort(a+b[b_id[x]].b_l,a+b[b_id[x]].b_r+1,cmp_id);
                for(int i=x;i<=b[b_id[x]].b_r;i++)s+=(a[i].num+b[b_id[x]].lazy_add<=mid);
                sort(a+b[b_id[x]].b_l,a+b[b_id[x]].b_r+1,cmp_num);
                sort(a+b[b_id[y]].b_l,a+b[b_id[y]].b_r+1,cmp_id);
                for(int i=b[b_id[y]].b_l;i<=y;i++)s+=(a[i].num+b[b_id[y]].lazy_add<=mid);
                sort(a+b[b_id[y]].b_l,a+b[b_id[y]].b_r+1,cmp_num);
                if(s<z)L=mid+1;
                else R=mid-1,ans=mid;
            }
            cout<<ans<<'\n';
        }
    }
	return 0;
}