RT。Ynoi全TLE合适吗

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

#define N 100010

using std::sort;
using std::nth_element;
using std::max;
using std::min;

int n,m,a[N];

inline int read()
{
    int x = 0,f = 1;
    char c = getchar();
    while(c < '0' || '9' < c)
    {
        if(c == '-')
            f = -1;
        c = getchar();
    }
    while('0' <= c && c <= '9')
    {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}

int len,idx,belong[N],L[N],R[N],d[N],lazy[N];
int mn[N],mx[N];

void build()
{
    len = sqrt(n);
    idx = n / len;
    if(n % len) idx++;
    memset(mn,0x3f,sizeof(mn));
    memset(mx,-0x3f,sizeof(mx));
    for(int i = 1;i <= n;i++)
    {
        belong[i] = (i - 1) / len + 1;
        mn[belong[i]] = min(mn[belong[i]],a[i]);
        mx[belong[i]] = max(mx[belong[i]],a[i]);
    }
    for(int i = 1;i <= idx;i++)
    {
        L[i] = (i - 1) * len + 1;
        R[i] = i * len;
    }
    memcpy(d,a,sizeof(a));
    for(int i = 1;i <= idx;i++)
        sort(d + L[i],d + 1 + R[i]);
}

void add(int x,int y,int z)
{
    if(belong[x] == belong[y])
    {
        for(int i = x;i <= y;i++)
            a[i] += z;
        mn[belong[x]] = 0x3f3f3f3f;
        mx[belong[x]] = -0x3f3f3f3f;
        for(int i = L[belong[x]];i <= R[belong[x]];i++)
        {
            d[i] = a[i];
            mn[belong[x]] = min(mn[belong[x]],a[i]);
            mx[belong[x]] = max(mx[belong[x]],a[i]);
        }
        sort(d + L[belong[x]],d + R[belong[x]] + 1);
        return;
    }
    int from = belong[x];
    for(int i = x;i <= R[from];i++)
        a[i] += z;
    mn[from] = 0x3f3f3f3f;
    mx[from] = -0x3f3f3f3f;
    for(int i = L[from];i <= R[from];i++)
    {
        d[i] = a[i];
        mn[from] = min(mn[from],a[i]);
        mx[from] = max(mx[from],a[i]);
    }
    sort(d + L[from],d + R[from] + 1);

    from = belong[y];
    for(int i = L[from];i <= y;i++)
        a[i] += z;
    mn[from] = 0x3f3f3f3f,mx[from] = -0x3f3f3f3f;
    for(int i = L[from];i <= R[from];i++)
    {
        d[i] = a[i];
        mn[from] = min(mn[from],a[i]);
        mx[from] = max(mx[from],a[i]);
    }
    sort(d + L[from],d + R[from] + 1);

    for(int i = belong[x] + 1;i <= belong[y] - 1;i++)
    {
        lazy[i] += z;
        //printf("mn/mx[%d to %d] += %d = %d,%d\n",L[i],R[i],z,mn[i],mx[i]);
        mn[i] += z;
        mx[i] += z;
    }
}

int tmp[N],top;

int query(int x,int y,int k)
{
    if(belong[x] == belong[y])
    {
		//printf("A\n");
        top = 0;
        if(k > y - x + 1)
            return -1;
        for(int i = x;i <= y;i++)
            tmp[++top] = a[i] + lazy[belong[x]];
        nth_element(tmp + 1,tmp + k,tmp + 1 + top);
        return tmp[k];
    }
	//printf("B\n");
    int l = 0x3f3f3f3f,r = -0x3f3f3f3f,mid,ans = -1;
    for(int i = x;i <= R[belong[x]];i++)
    {
		//printf("a[%d] = %d + %d\n",i,a[i],lazy[belong[x]]);
        l = min(l,a[i] + lazy[belong[x]]);
        r = max(r,a[i] + lazy[belong[x]]);
    }
    for(int i = L[belong[y]];i <= y;i++)
    {
		//printf("a[%d] = %d + %d\n",i,a[i],lazy[belong[y]]);
        l = min(l,a[i] + lazy[belong[y]]);
        r = max(r,a[i] + lazy[belong[y]]);
    }
    for(int i = belong[x] + 1;i <= belong[y] - 1;i++)
    {
        //printf("%d to %d.mn = %d,mx = %d\n",L[i],R[i],mn[i],mx[i]);
        l = min(l,mn[i]);
        r = max(r,mx[i]);
    }
	//printf("l = %d,r = %d\n",l,r);
    while(l <= r)
    {
       
        mid = l + r >> 1;
        int check = 0; //printf("l = %d,r = %d,mid = %d\n",l,r,mid);
        for(int i = x;i <= R[belong[x]];i++)
        {
            if(a[i] + lazy[belong[x]] <= mid)
			{
				//printf("+a[%d] = %d\n",i,a[i]);
                check++;
			}
        }
        for(int i = L[belong[y]];i <= y;i++)
        {
            if(a[i] + lazy[belong[y]] <= mid)
			{
				//printf("+a[%d] = %d\n",i,a[i]);
                check++;
			}
        }
        for(int i = belong[x] + 1;i <= belong[y] - 1;i++)
        {
            int ll = L[i],rr = R[i],mmid,aans = L[i] - 1;
			while(ll <= rr)
			{
				mmid = ll + rr >> 1;
				if(d[mmid] + lazy[i] <= mid)
				{
					ll = mmid + 1;
					aans = mmid;
				}
				else
					rr = mmid - 1;
			}
			//printf("i = %d,kuai = %d to %d,aans = %d\n",i,L[i],R[i],aans);
			check += aans - L[i] + 1;
        }
		//printf("mid = %d,check = %d,k = %d\n",mid,check,k);
		if(check >= k)
        {
            ans = mid;
            r = mid - 1;
        }
        else
            l = mid + 1;
    }
	return ans;
}/*     4 5
      3     6
      +     +
1 2 3 4 5 6 7*/

int main()
{
	//freopen("maker.in","r",stdin);
	//freopen("std.out","w",stdout);
    n = read(),m = read();
    for(int i = 1;i <= n;i++)
        a[i] = read();
    build();
    int op,l,r,k;
    while(m--)
    {
        op = read(),l = read(),r = read(),k = read();
		if(op == 0)
			add(l,r,k);
		else
			printf("%d\n",query(l,r,k));
    }
	return 0;
}