如题，但不排除是我写挂了。

思路是块内排序，但是蒟蒻一开始就是直接用值排序（而不是题解中说的元素下标），然后再操作。

所以比较难做归并排序，但复杂度瓶颈好像不在这里（？）

88pts 已经是能卡到的极限了，各种题解中的优化都试了，有的加了反而慢

代码，加了各种优化的，学习了一下第一篇题解的思路，%%%。

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#define GCC optimize("Ofast")
#define GCC optimize("inline")
#define GCC optimize("-fgcse")
#define GCC optimize("-fgcse-lm")
#define GCC optimize("-fipa-sra")
#define GCC optimize("-ftree-pre")
#define GCC optimize("-ftree-vrp")
#define GCC optimize("-fpeephole2")
#define GCC optimize("-ffast-math")
#define GCC optimize("-fsched-spec")
#define GCC optimize("unroll-loops")
#define GCC optimize("-falign-jumps")
#define GCC optimize("-falign-loops")
#define GCC optimize("-falign-labels")
#define GCC optimize("-fdevirtualize")
#define GCC optimize("-fcaller-saves")
#define GCC optimize("-fcrossjumping")
#define GCC optimize("-fthread-jumps")
#define GCC optimize("-funroll-loops")
#define GCC optimize("-fwhole-program")
#define GCC optimize("-freorder-blocks")
#define GCC optimize("-fschedule-insns")
#define GCC optimize("inline-functions")
#define GCC optimize("-ftree-tail-merge")
#define GCC optimize("-fschedule-insns2")
#define GCC optimize("-fstrict-aliasing")
#define GCC optimize("-fstrict-overflow")
#define GCC optimize("-falign-functions")
#define GCC optimize("-fcse-skip-blocks")
#define GCC optimize("-fcse-follow-jumps")
#define GCC optimize("-fsched-interblock")
#define GCC optimize("-fpartial-inlining")
#define GCC optimize("no-stack-protector")
#define GCC optimize("-freorder-functions")
#define GCC optimize("-findirect-inlining")
#define GCC optimize("-frerun-cse-after-loop")
#define GCC optimize("inline-small-functions")
#define GCC optimize("-finline-small-functions")
#define GCC optimize("-ftree-switch-conversion")
#define GCC optimize("-foptimize-sibling-calls")
#define GCC optimize("-fexpensive-optimizations")
#define GCC optimize("-funsafe-loop-optimizations")
#define GCC optimize("-fdelete-null-pointer-checks")

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<cassert>
typedef long long ll;
const int _T=158+10;
const int _B=632+10;
const int __=1e5+10;
const int inf=2.1e9;
using namespace std;

namespace ioer
{
#ifdef ONLINE_JUDGE
#define getchar getch
#endif
static const int SIZE=1048576;
bool idigit(char x){return '0'<=x&&x<='9';}
bool iword(char x){return !(x<'a'||x>'z')&&!(x<'A'||x>'Z');}
static char ibuff[SIZE], *ibg=ibuff, *ied=ibuff;
char getch(void){
	if(ibg==ied&&(ied=(ibg=ibuff)+fread(ibuff,1,SIZE,stdin),ibg==ied))
	{return -1;}return *ibg++;
}
template<typename tp>
void read(tp &a){
	char x=getchar();a=0;tp op=0;while(!idigit(x)){op|=(x=='-'),x=getchar();}
	while(idigit(x)){a=(a<<1)+(a<<3)+(x^'0'),x=getchar();}a=op?-a:a;
}
void reads(void){}
template<typename tp,typename... Args>
void reads(tp &head,Args&... arg){read(head);reads(arg...);}
void readchar(char &x){do{x=getchar();}while(!iword(x)&&!idigit(x));}
int readstr(char *s){
	char x;int len=0;readchar(x);
	do{s[len++]=x,x=getchar();}while(iword(x)||idigit(x));return len;
}
static char obuff[SIZE], *obg=obuff;
void flush(void){fwrite(obuff,1,obg-obuff,stdout);obg=obuff;}
void putch(char x){
	if(obg==obuff+SIZE){fwrite(obuff,1,SIZE,stdout);obg=obuff;}*obg++=x;
}
template<typename tp>
void write(tp x){
	if(x<0){putch('-'),x=-x;}static char sta[20];unsigned short top=0;
	do{sta[top++]=(x%10)^48,x/=10;}while(x);while(top) putch(sta[--top]);
}
template<typename tp>void writespace(tp x){write(x);putch(' ');}
template<typename tp>void writendl(tp x){write(x);putch('\n');}
void writestr(char *s){int len=strlen(s);for(int i=0;i<len;i++) putch(s[i]);}
void writespaces(void){}
template<typename tp,typename... Args>
void writespaces(tp head,Args... arg){writespace(head);writespaces(arg...);}
void writendls(void){}
template<typename tp,typename... Args>
void writendls(tp head,Args... arg){writendl(head);writendls(arg...);}
#ifdef ONLINE_JUDGE
#undef getchar
#endif
}
using namespace ioer;

#define Read(x) read(x)
#define Write(x) writendl(x)

int n,m,blen,bcnt;
int a[__],pos[__];int Qlag;

struct Block{
	int l,r,len,tag;int Qlag;
	int s[_T],pre;
}b[_B];

// 散块修改
void Modify_(int l,int r,int k){
	int Pos=pos[l];
	if(b[Pos].tag){
		for(int i=b[Pos].l;i<=b[Pos].r;i++) a[i]+=b[Pos].tag;
		b[Pos].tag=0;
	}
	for(int i=l;i<=r;i++) a[i]+=k;
	for(int i=b[Pos].l,j=1;i<=b[Pos].r;i++,j++) b[Pos].s[j]=a[i];
	sort(b[Pos].s+1,b[Pos].s+1+b[Pos].len);
}

// 修改
void Modify(int l,int r,int k){
	if(pos[l]==pos[r]) return Modify_(l,r,k);
	Modify_(l,b[pos[l]].r,k),Modify_(b[pos[r]].l,r,k);
	for(int i=pos[l]+1;i<pos[r];i++) b[i].tag+=k;
}

// 询问在同一块内
int Query_(int l,int r,int k){
	static int _Tmp[_T];unsigned len=0;
	for(int j=l;j<=r;j++) _Tmp[++len]=a[j];
	nth_element(_Tmp+1,_Tmp+k,_Tmp+1+len);
	return _Tmp[k]+b[pos[l]].tag;
}

// 询问散块内最值
int QueryMaxMin_(int l,int r,bool op){
	int ans=op?inf:-inf;
	for(int i=l;i<=r;i++) ans=op?min(ans,a[i]):max(ans,a[i]);
	return ans+b[pos[l]].tag;
}

// 询问区间最大/最小,0最大，1最小
int QueryMaxMin(int l,int r,bool op){
	int ans=op?inf:-inf;
	if(!op) ans=max(QueryMaxMin_(l,b[pos[l]].r,0),QueryMaxMin_(b[pos[r]].l,r,0));
	else ans=min(QueryMaxMin_(l,b[pos[l]].r,1),QueryMaxMin_(b[pos[r]].l,r,1));
	for(int i=pos[l]+1;i<pos[r];i++){
		if(!op) ans=max(ans,b[i].s[b[i].len]+b[i].tag);
		else ans=min(ans,b[i].s[1]+b[i].tag);
	}
	return ans;
}

// 返回 [l,r] 内小于 limit 个数，op 为左/右移 limit 的标记
int check(int l,int r,int limit,bool op){
	if(l>r) return 0;
	int ans=0;
	for(int i=l,res;i<=r;i++){
		if(b[i].Qlag!=Qlag){ // 第一次二分
			b[i].Qlag+=1;
			if(b[i].s[1]>limit-b[i].tag){b[i].pre=0;continue;}
			if(b[i].s[b[i].len]<=limit-b[i].tag){ans+=(b[i].pre=b[i].len);continue;} // 剪枝，但好像没有跑得很快
			res=upper_bound(b[i].s+1,b[i].s+1+b[i].len,limit-b[i].tag)-(b[i].s+1);
			ans+=res,b[i].pre=res;
			continue;
		}
		if(b[i].s[1]>limit-b[i].tag){b[i].pre=0;continue;}
		if(b[i].s[b[i].len]<=limit-b[i].tag){ans+=(b[i].pre=b[i].len);continue;}
		if(op==1){ // 参考第一篇题解，%%%
			res=upper_bound(b[i].s+1+b[i].pre,b[i].s+1+b[i].len,limit-b[i].tag)-(b[i].s+1+b[i].pre);
			ans+=res+b[i].pre,b[i].pre+=res;
		}
		if(op==0){
			res=upper_bound(b[i].s+1,b[i].s+1+b[i].pre,limit-b[i].tag)-(b[i].s+1);
			ans+=res,b[i].pre=res;
		}
	}
	return ans;
}

// 询问，二分答案，值域为 [min,max]。
int Query(int l,int r,int k){
	if(pos[l]==pos[r]) return Query_(l,r,k);
	static int _tmp[_T*2];unsigned len=0;Qlag+=1;// 用于统计散块内
	for(int i=l;i<=b[pos[l]].r;i++) _tmp[++len]=a[i]+b[pos[l]].tag;
	for(int i=b[pos[r]].l;i<=r;i++) _tmp[++len]=a[i]+b[pos[r]].tag;
	sort(_tmp+1,_tmp+1+len);bool op=0;// op 为 1 是右移答案，为 0 是左移答案
	int lf=QueryMaxMin(l,r,1),rt=QueryMaxMin(l,r,0),mid,cnt,ans=rt;
	while(lf<=rt){
		mid=(1ll*lf+rt)/2;
		cnt=upper_bound(_tmp+1,_tmp+1+len,mid)-_tmp-1;
		int res=check(pos[l]+1,pos[r]-1,mid,op);
		if(res+cnt<k) lf=mid+1,op=1;
		else rt=mid-1,ans=mid,op=0;
	}
	return ans;
}

int main(){
//	freopen("5356.in","r",stdin);
//	freopen("5356.out","w",stdout);
	Read(n),Read(m);assert(n==100000);
	for(int i=1;i<=n;i++) Read(a[i]);
	blen=_T-10,bcnt=n/blen;
	for(int i=1;i<=bcnt;i++){
		b[i].l=b[i-1].r+1,b[i].r=b[i-1].r+blen,b[i].len=blen;
	}
	if(b[bcnt].r<n){
		bcnt++,b[bcnt].l=b[bcnt-1].r+1,b[bcnt].r=n,b[bcnt].len=n-b[bcnt-1].r;
	}
	for(int i=1;i<=bcnt;i++){
		for(int j=b[i].l;j<=b[i].r;j++){
			b[i].s[j-b[i].l+1]=a[j],pos[j]=i;
		}
		sort(b[i].s+1,b[i].s+1+b[i].len);
	}
	for(int i=1,op,l,r,k;i<=m;i++){
		Read(op),Read(l),Read(r),Read(k);
		if(op==1) Write(Query(l,r,k));
		if(op==2) Modify(l,r,k);
	}
	flush();
	return 0;
}

但发现加了好多优化过不了，打算自己发展

代码

const int _T=145+10;
const int _B=689+10;
const int __=1e5+10;
const int inf=2.1e9;

// 省略火车头，快读等。
// 可能是因为结构体比较慢，拆开了，但好像没有快多少
int n,m,blen,bcnt;
int a[__],pos[__];
int L[_B],R[_B],len[_B],tag[_B],s[__];

void Modify_(int l,int r,int k){
	int Pos=pos[l];
	if(tag[Pos]){
		for(int i=L[Pos];i<=R[Pos];i++) a[i]+=tag[Pos];
		tag[Pos]=0;
	}
	for(int i=l;i<=r;i++) a[i]+=k;
	for(int i=L[Pos];i<=R[Pos];i++) s[i]=a[i];
	std::sort(s+L[Pos],s+1+R[Pos]);
}

void Modify(int l,int r,int k){
	if(pos[l]==pos[r]) return Modify_(l,r,k);
	Modify_(l,R[pos[l]],k),Modify_(L[pos[r]],r,k);
	for(int i=pos[l]+1;i<pos[r];i++) tag[i]+=k;
}

int Query_(int l,int r,int k){
	static int _Tmp[_T];unsigned len=0;
	for(int j=l;j<=r;j++) _Tmp[++len]=a[j];
	std::nth_element(_Tmp+1,_Tmp+k,_Tmp+1+len);
	return _Tmp[k]+tag[pos[l]];
}

int QueryMaxMin_(int l,int r,bool op){
	int ans=op?inf:-inf;
	for(int i=l;i<=r;i++) ans=op?std::min(ans,a[i]):std::max(ans,a[i]);
	return ans+tag[pos[l]];
}

int QueryMaxMin(int l,int r,bool op){
	int ans=op?inf:-inf;
    // 发现散块询问比较慢，果断直接询问整个散块
//	if(!op) ans=max(QueryMaxMin_(l,R[pos[l]],0),QueryMaxMin_(L[pos[r]],r,0));
//	else ans=min(QueryMaxMin_(l,R[pos[l]],1),QueryMaxMin_(L[pos[r]],r,1));
	for(int i=pos[l];i<=pos[r];i++){
		if(!op) ans=std::max(ans,s[R[i]]+tag[i]);
		else ans=std::min(ans,s[L[i]]+tag[i]);
	}
	return ans;
}

// 放弃了玄学优化
int check(int l,int r,int limit,int k){
	if(l>r) return 0;
	int ans=0;
	for(int i=r;i>=l;i--){
		if(s[L[i]]>limit-tag[i]){continue;}
		if(s[R[i]]<=limit-tag[i]){ans+=len[i];continue;}
		ans+=std::upper_bound(s+L[i],s+1+R[i],limit-tag[i])-(s+L[i]);
		if(ans>=k) return ans;
	}
	return ans;
}

int Query(int l,int r,int k){
	if(pos[l]==pos[r]) return Query_(l,r,k);
	static int _tmp[_T*2];unsigned len=0;
	for(int i=l;i<=R[pos[l]];i++) _tmp[++len]=a[i]+tag[pos[l]];
	for(int i=L[pos[r]];i<=r;i++) _tmp[++len]=a[i]+tag[pos[r]];
	std::sort(_tmp+1,_tmp+1+len);
	int lf=QueryMaxMin(l,r,1),rt=QueryMaxMin(l,r,0),mid,cnt,ans=rt,dl=lf,dr=rt;
	bool first=1;
	double delta=k/(r-l+1.0);
	if(delta<0.25) delta=0.25;// 能快一点
	if(delta>0.75) delta=0.75;
	while(lf<=rt){
		if(first) first=0,mid=(1ll*lf+rt)*delta;
		else mid=(1ll*lf+rt)/2;
		cnt=std::upper_bound(_tmp+1,_tmp+1+len,mid)-_tmp-1;
		int res=check(pos[l]+1,pos[r]-1,mid,k-cnt);
		if(res+cnt<k) lf=mid+1;
		else rt=mid-1,ans=mid;
	}
    // 当时还算了一下k与答案在相似的位置的概率
//	printf("%.2lf ",std::max(delta/(1.0*(ans-dl)/(dr-dl)),(1.0*(ans-dl)/(dr-dl))/delta));
	return ans;
}

int main(){
	freopen("5356.in","r",stdin);
	freopen("5356.out","w",stdout);
	Read(n),Read(m);
	for(int i=1;i<=n;i++) Read(a[i]);
	blen=_T-10,bcnt=n/blen;
	for(int i=1;i<=bcnt;i++){
		L[i]=R[i-1]+1,R[i]=R[i-1]+blen,len[i]=blen;
	}
	if(R[bcnt]<n){
		bcnt++,L[bcnt]=R[bcnt-1]+1,R[bcnt]=n,len[bcnt]=n-R[bcnt-1];
	}
	memcpy(s,a,sizeof s);
	for(int i=1;i<=bcnt;i++){
		for(int j=L[i];j<=R[i];j++) pos[j]=i;
		std::sort(s+L[i],s+1+R[i]);
	}
	for(int i=1,op,l,r,k;i<=m;i++){
		Read(op),Read(l),Read(r),Read(k);
		if(op==1) Write(Query(l,r,k));
		if(op==2) Modify(l,r,k);
	}
	flush();
	return 0;
}

QwQ，悬赏关注 $\times 1$。