求数据

//
//  main.cpp
//  P5356
//
//  Created by mac on 2020/11/23.
//
#include<bits/stdc++.h>
using namespace std;
#define int long long
int be[1000001];
struct cxk{
    int zhi,xv;
}a[1000001];
bool cmp(cxk a,cxk b)
{
    return a.zhi<b.zhi;
}
bool cmpp(cxk a,cxk b)
{
    return a.zhi>b.zhi;
}
int n,m;
queue<cxk>q;
queue<cxk>qq;
int tag[1000001];
int rb[1000001];
signed main( )
{
    //freopen("stdin.in","r",stdin);
    //freopen("stdout.out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].zhi;
        a[i].xv=i;
    }
    int gn=sqrt(n);
    int gnn=ceil(double(n)/gn);
    for(int i=1;i<=gnn;i++)
    {
        rb[i]=min(i*gn,n);
        for(int j=i*gn-gn+1;j<=min(i*gn,n);j++)
        be[j]=i;
        sort(a+rb[i-1]+1,a+rb[i]+1,cmp);
    }
    for(int i=1;i<=m;i++)
    {
        int o,l,r,k;
        cin>>o>>l>>r>>k;
        if(o==1)
        {
            if(k==0||k>(r-l+1))
            {
                cout<<"-1"<<endl;
                continue;
            }
            if(be[l]==be[r])
            {
                int p=be[l];
                int o=0;
                for(int j=rb[p-1]+1;j<=rb[p];j++)
                {
                    if(a[j].xv<=r&&a[j].xv>=l)o++;
                    if(o==k)
                    {
                        cout<<a[j].zhi+tag[p]<<endl;
                        break;
                    }
                }
            }
            else
            {
                int ll=-20001;
                int rr=20001;
                int da=0;
                while(ll<=rr)
                {
                    int ans=0;
                    int mid=(ll+rr)/2;
                    int p=be[l];
                    for(int j=rb[p-1]+1;j<=rb[p];j++)
                    if(a[j].xv>=l&&a[j].zhi+tag[p]<=mid)ans++;
                    p=be[r];
                    for(int j=rb[p-1]+1;j<=rb[p];j++)
                    if(a[j].xv<=r&&a[j].zhi+tag[p]<=mid)ans++;
                    for(int j=be[l]+1;j<=be[r]-1;j++)
                    {
                        cxk t;
                        t.zhi=mid-tag[j];
                        long long r=upper_bound(a+rb[j-1]+1,a+rb[j]+1,t,cmp)-a-rb[j-1]-1;
                        ans+=r;
                    }
                    if(ans>=k)
                    {
                        da=mid;
                        rr=mid-1;
                    }
                    else ll=mid+1;
                }
                cout<<da<<endl;
            }
            
        }
        if(o==2)
        {
            if(be[l]==be[r])
            {
                int p=be[l];
                for(int j=rb[p-1]+1;j<=rb[p];j++)
                {
                    if(a[j].xv<=r&&a[j].xv>=l)
                    {
                        a[j].zhi+=k;
                        q.push(a[j]);
                    }
                    else qq.push(a[j]);
                }
                int ccnt=rb[p-1]+1;
                while(!q.empty( )&&!qq.empty( ))
                {
                    if(q.front( ).zhi<qq.front( ).zhi)
                    {
                        a[ccnt]=q.front( );
                        q.pop( );
                    }
                    else{
                        a[ccnt]=qq.front( );
                        qq.pop( );
                    }
                    ccnt++;
                }
                while(!q.empty( ))
                {
                    a[ccnt]=q.front( );
                    q.pop( );
                    ccnt++;
                }
                while(!qq.empty( ))
                {
                    a[ccnt]=qq.front( );
                    qq.pop( );
                    ccnt++;
                }
            }
            else
            {
                for(int j=be[l]+1;j<=be[r]-1;j++)tag[j]+=k;
                int p=be[l];
                for(int j=rb[p-1]+1;j<=rb[p];j++)
                {
                    if(a[j].xv>=l)
                    {
                        a[j].zhi+=k;
                        q.push(a[j]);
                    }
                    else qq.push(a[j]);
                }
                int ccnt=rb[p-1]+1;
                while(!q.empty( )&&!qq.empty( ))
                {
                    if(q.front( ).zhi<qq.front( ).zhi)
                    {
                        a[ccnt]=q.front( );
                        q.pop( );
                    }
                    else{
                        a[ccnt]=qq.front( );
                        qq.pop( );
                    }
                    ccnt++;
                }
                while(!q.empty( ))
                {
                    a[ccnt]=q.front( );
                    q.pop( );
                    ccnt++;
                }
                while(!qq.empty( ))
                {
                    a[ccnt]=qq.front( );
                    qq.pop( );
                    ccnt++;
                }
                p=be[r];
                for(int j=rb[p-1]+1;j<=rb[p];j++)
                {
                    if(a[j].xv<=r)
                    {
                        a[j].zhi+=k;
                        q.push(a[j]);
                    }
                    else qq.push(a[j]);
                }
                ccnt=rb[p-1]+1;
                while(!q.empty( )&&!qq.empty( ))
                {
                    if(q.front( ).zhi<qq.front( ).zhi)
                    {
                        a[ccnt]=q.front( );
                        q.pop( );
                    }
                    else{
                        a[ccnt]=qq.front( );
                        qq.pop( );
                    }
                    ccnt++;
                }
                while(!q.empty( ))
                {
                    a[ccnt]=q.front( );
                    q.pop( );
                    ccnt++;
                }
                while(!qq.empty( ))
                {
                    a[ccnt]=qq.front( );
                    qq.pop( );
                    ccnt++;
                }
            }
        }
    }
}