继上个帖后，我成功把 10TLE（3s-4s）卡成了 9TLE（2-3s）+1WA……

（对拍1e4的数据没问题

看到题解区有篇blog算法一样，而且笔者说不用卡常，还用了许多加常数的#define int long long和using namespace std，百思不得其解，求助大佬卡常

#include <cstring>
#include <cmath>
#include <algorithm>
#include <ctime>

#define N 100010

using std::sort;
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];

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

inline void add(int x,int y,int z)
{
    if(belong[x] == belong[y])
    {
        for(int i = x;i <= y;i++)
            a[i] += z;
        for(int i = L[belong[x]];i <= R[belong[x]];i++)
            d[i] = 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;
    }
    for(int i = L[from];i <= R[from];i++)
    {
        d[i] = a[i];
    }
    sort(d + L[from],d + R[from] + 1);

    from = belong[y];
    for(int i = L[from];i <= y;i++)
    {
        a[i] += z;
    }
    for(int i = L[from];i <= R[from];i++)
    {
        d[i] = a[i];
    }
    sort(d + L[from],d + R[from] + 1);

    for(int i = belong[x] + 1;i <= belong[y] - 1;i++)
    {
        lazy[i] += z;
    }
}

int tmp[N],top;

inline int get_min(int x,int y)
{
    int res = 0x3f3f3f3f;
    if(belong[x] == belong[y])
    {
        for(int i = x;i <= y;i++)
            res = min(res,a[i] + lazy[belong[x]]);
        return res;
    }
    for(int i = x;i <= R[belong[x]];i++)
    {
        res = min(res,a[i] + lazy[belong[x]]);
    }
    for(int i = L[belong[y]];i <= y;i++)
    {
        res = min(res,a[i] + lazy[belong[y]]);
    }
    for(int i = belong[x] + 1;i <= belong[y] - 1;i++)
    {
        res = min(res,d[L[i]] + lazy[i]);
    }
    return res;
}

inline int get_max(int x,int y)
{
    int res = -0x3f3f3f3f;
    if(belong[x] == belong[y])
    {
        for(int i = x;i <= y;i++)
            res = max(res,a[i] + lazy[belong[x]]);
        return res;
    }
    for(int i = x;i <= R[belong[x]];i++)
    {
        res = max(res,a[i] + lazy[belong[x]]);
    }
    for(int i = L[belong[y]];i <= y;i++)
    {
        res = max(res,a[i] + lazy[belong[y]]);
    }
    for(int i = belong[x] + 1;i <= belong[y] - 1;i++)
    {
        res = max(res,d[R[i]] + lazy[i]);
    }
    return res;
}

inline int check(int x,int y,int mid)
{
    int ck = 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]);
            ck++;
		}
    }
    for(int i = L[belong[y]];i <= y;i++)
    {
        if(a[i] + lazy[belong[y]] <= mid)
		{
			//printf("+a[%d] = %d\n",i,a[i]);
            ck++;
		}
    }
    for(int i = belong[x] + 1;i <= belong[y] - 1;i++)
    {
        int ll = L[i],rr = R[i],mmid,aans = L[i] - 1;
        if(d[L[i]] + lazy[i] > mid)
            continue;
        if(d[R[i]] + lazy[i] <= mid)
        {
            ck += R[i] - L[i] + 1;
            continue;
        }
		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);
        ck += aans - L[i] + 1;
    }
    return ck;
}

inline int query(int x,int y,int k)
{
    if(k < 1 || k > y - x + 1)
        return -1;
    if(belong[x] == belong[y])
    {
		//printf("A\n");
        top = 0;
        
        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 = get_min(x,y),r = get_max(x,y),mid,ans = -1;
    
    if(k == 1)
        return l;
    if(k == y - x + 1)
        return r;
	//printf("l = %d,r = %d\n",l,r);
    while(l <= r)
    {
       
        mid = l + r >> 1;
		//printf("mid = %d,check = %d,k = %d\n",mid,check,k);
		if(check(x,y,mid) >= k)
        {
            ans = mid;
            r = mid - 1;
        }
        else
            l = mid + 1;
    }
	return ans;
}/*     4 5
      3     6
      +     +
1 2 3 4 5 6 7*/

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

int main()
{
    //double tim = time(0);
    //别管这个double
	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
        {
			write(query(l,r,k));
            putchar('\n');
        }
    }
    //printf("time:%.5f\n",time(0) - tim);
	return 0;
}