提交记录

#include<bits/stdc++.h>
using namespace std;
const int INF=2147483647;
int n,m,t,a[100001]={0},b[100001]={0},l[1001]={0},r[1001]={0},add[1001]={0},pos[100001]={0};
void build(){//预处理 
    int num=n/t;
    if(n%t>0) num++;
    for(int i=1;i<=num;i++) l[i]=(i-1)*t+1,r[i]=i*t;
    r[num]=n;
    for(int i=1;i<=num;i++){
        for(int j=l[i];j<=r[i];j++) pos[j]=i;
        sort(a+l[i],a+r[i]+1);
    }
}
int getmax(int x,int y){//查询区间最大值 
    int p=pos[x],q=pos[y],ans=-INF;
    if(p==q){
        for(int i=x;i<=y;i++) ans=max(ans,b[i]+add[p]);
    }else{
        for(int i=p+1;i<=q-1;i++) ans=max(ans,a[r[i]]+add[i]);
        for(int i=x;i<=r[p];i++) ans=max(ans,b[i]+add[p]);
        for(int i=l[q];i<=y;i++) ans=max(ans,b[i]+add[q]);
    }
    return ans;
}
int getmin(int x,int y){//查询区间最小值 
    int p=pos[x],q=pos[y],ans=INF;
    if(p==q){
        for(int i=x;i<=y;i++) ans=min(ans,b[i]+add[p]);
    }else{
        for(int i=p+1;i<=q-1;i++) ans=min(ans,a[l[i]]+add[i]);
        for(int i=x;i<=r[p];i++) ans=min(ans,b[i]+add[p]);
        for(int i=l[q];i<=y;i++) ans=min(ans,b[i]+add[q]);
    }
    return ans;
}
int getnum(int x,int y,int d){//查询区间小于等于 d的个数 
    int p=pos[x],q=pos[y],ans=0;
    if(p==q){
        for(int i=x;i<=y;i++) if(b[i]+add[p]<=d) ans++;
    }else{
        for(int i=p+1;i<=q-1;i++) ans+=upper_bound(a+l[i],a+r[i]+1,d)-a-1;//整块 
        for(int i=x;i<=r[p];i++) if(b[i]+add[p]<=d) ans++;
        for(int i=l[q];i<=y;i++) if(b[i]+add[q]<=d) ans++;
    }
    return ans;
}
int query(int x,int y,int k){//查询区间第 k小值 
    int p=pos[x],q=pos[y];
    if(k<1 || y-x+1<k) return -1;
    int l=getmin(x,y),r=getmax(x,y),ans=-1;
    while(l<=r){//二分答案 
        int mid=(l+r)/2,cnt=getnum(x,y,mid);
        if(cnt<k) l=mid+1;
        else r=mid-1,ans=mid;
    }
    return ans;
}
void change(int x,int y,int d){//零散块暴力修改 
    int p=pos[x];
    for(int i=x;i<=y;i++) b[i]+=d;
    for(int i=l[p];i<=r[p];i++) a[i]=b[i];
    sort(a+l[p],a+r[p]+1);
}
void update(int x,int y,int d){//区间修改加上 k 
    int p=pos[x],q=pos[y];
    if(p==q) change(x,y,d);
    else{
        for(int i=p+1;i<=q-1;i++) add[i]+=d;//打懒标记 
        change(x,r[p],d),change(l[q],y,d);
    }
}
int main(){
    scanf("%d%d",&n,&m);
    t=sqrt(n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),b[i]=a[i];//a 数组为要排序的数组，b为原数组 
    build();
    while(m--){
        int opt,l,r,k;
        scanf("%d%d%d%d",&opt,&l,&r,&k);
        if(opt==1) printf("%d",query(l,r,k));
        else update(l,r,k);
    }
    return 0;
}