RT。。

一开始对于非整块 add 用的是 sort，拿了 70 pts。然后换成归并就更慢了？？

#include<bits/stdc++.h>
#define max(a,b) a>b?a:b
#define min(a,b) a<b?a:b
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#pragma GCC optimize(3,"Ofast","inline")
using namespace std;
const int b=400,mx=1e5+5,up=1<<8; 
int a[mx];
struct num
{
	int s,w;
	friend bool operator<(num x,num y)
	{
		return x.s<y.s;
	}
}st[mx],fz1[mx],fz2[mx];
int bl[mx],fl[mx],fr[mx],tag[mx],ks;
char ibuf[900<<20],*s,out[900<<20];
int wz;
inline int read()
{
    register int u=0,w=1;
    while(*s<48)
	{
		if(*s=='-') w=-1;
		s++;
	} 
    while(*s>32)
        u=u*10+*s++-48;
    return u*w;
}
void print(int x)
{
	if(x<0) 
	{
		out[wz++]='-',print(-x);
		return;
	}
    if(x>9) print(x/10);
	out[wz++]=x%10+'0';
}
int n;
void init()
{
	int i,j;
	for(i=1;i-1+b<=n;i+=b)
		fl[++ks]=i,fr[ks]=i-1+b;
	if(i<=n)
		fl[++ks]=i,fr[ks]=n;
	for(i=1;i<=n;i++)
		st[i]=num({a[i],i});
	for(i=1;i<=ks;i++)
	{
		for(j=fl[i];j<=fr[i];j++)
			bl[j]=i;
		sort(st+fl[i],st+fr[i]+1);
	}	
}
void add(int l,int r,int k)
{
	int i,j,w,w1,w2;
	if(bl[l]==bl[r])
	{
		for(i=l;i<=r;i++)
			a[i]+=k;
		for(i=fl[bl[l]];i<=fr[bl[l]];i++)
			st[i].s=a[st[i].w];
		w1=w2=0;
		for(i=fl[bl[l]];i<=fr[bl[l]];i++)
			if(st[i].w>=l&&st[i].w<=r)
				fz1[w1++]=st[i];
			else
				fz2[w2++]=st[i];
		i=j=0;
		for(w=fl[bl[l]];i<w1&&j<w2;w++)
			if(fz1[i]<fz2[j])
				st[w]=fz1[i++];
			else
				st[w]=fz2[j++];
		while(i<w1) st[w++]=fz1[i++];
		while(j<w2) st[w++]=fz2[j++];
		return;
	}
	for(i=l;i<=fr[bl[l]];i++)
		a[i]+=k;
	for(i=fl[bl[l]];i<=fr[bl[l]];i++)
		st[i].s=a[st[i].w];
	w1=w2=0;
	for(i=fl[bl[l]];i<=fr[bl[l]];i++)
		if(st[i].w>=l)
			fz1[w1++]=st[i];
		else
			fz2[w2++]=st[i];
	i=j=0;
	for(w=fl[bl[l]];i<w1&&j<w2;w++)
		if(fz1[i]<fz2[j])
			st[w]=fz1[i++];
		else
			st[w]=fz2[j++];
	while(i<w1) st[w++]=fz1[i++];
	while(j<w2) st[w++]=fz2[j++];
	
	for(i=bl[l]+1;i<bl[r];i++)
		tag[i]+=k;
		
	for(i=fl[bl[r]];i<=r;i++)
		a[i]+=k;
	for(i=fl[bl[r]];i<=fr[bl[r]];i++)
		st[i].s=a[st[i].w];	
	w1=w2=0;
	for(i=fl[bl[r]];i<=fr[bl[r]];i++)
		if(st[i].w<=r)
			fz1[w1++]=st[i];
		else
			fz2[w2++]=st[i];
	i=j=0;
	for(w=fl[bl[r]];i<w1&&j<w2;w++)
		if(fz1[i]<fz2[j])
			st[w]=fz1[i++];
		else
			st[w]=fz2[j++];
	while(i<w1) st[w++]=fz1[i++];
	while(j<w2) st[w++]=fz2[j++];
}
int bound(int l,int r,int k)
{
	int i,w=l-1;
	for(i=up;i>=1;i/=2)
		if(w+i<=r&&st[w+i].s<=k)
			w+=i;
	return w-l+1;
}
int check(int l,int r,int mid)
{
	int s=0,i;
	if(bl[l]==bl[r])
	{
		for(i=l;i<=r;i++)
			s+=a[i]+tag[bl[i]]<=mid;
	}
	else
	{
		for(i=l;i<=fr[bl[l]];i++)
			s+=a[i]+tag[bl[i]]<=mid;
		for(i=bl[l]+1;i<bl[r];i++)
			s+=bound(fl[i],fr[i],mid-tag[i]);
		for(i=fl[bl[r]];i<=r;i++)
			s+=a[i]+tag[bl[i]]<=mid;
	}
	return s;
}
int ask(int l,int r,int k)
{
	int le=2e9,ri=-2e9,mid,re,i;
	if(bl[l]==bl[r])
	{
		for(i=l;i<=r;i++)
			le=min(le,a[i]+tag[bl[i]]),ri=max(ri,a[i]+tag[bl[i]]);
	}
	else
	{
		for(i=l;i<=fr[bl[l]];i++)
			le=min(le,a[i]+tag[bl[i]]),ri=max(ri,a[i]+tag[bl[i]]);
		for(i=bl[l]+1;i<bl[r];i++)
			le=min(le,st[fl[i]].s+tag[i]),ri=max(ri,st[fr[i]].s+tag[i]);
		for(i=fl[bl[r]];i<=r;i++)
			le=min(le,a[i]+tag[bl[i]]),ri=max(ri,a[i]+tag[bl[i]]);
	}
	while(le<=ri)
	{
		mid=(long long)le+ri>>1;
		if(check(l,r,mid)>=k)
			ri=mid-1,re=mid;
		else
			le=mid+1;
	}
	return re;
}
int main()
{
//	freopen("in","r",stdin);
//	freopen("out3","w",stdout);
	fread(s=ibuf,1,900<<20,stdin);
	int m,i,opt,l,r,k;
	n=read(),m=read();
	for(i=1;i<=n;i++)
		a[i]=read();	
	init();
	while(m--)
	{
		opt=read(),l=read(),r=read(),k=read();
		if(opt==1) print(ask(l,r,k)),out[wz++]='\n';
		else add(l,r,k);
	}
	fwrite(out,1,wz,stdout);
} 

是写法常数太大了吗？