自动搬运

查看原文

来自洛谷，原作者为

	2018heyuyang **

搬运于2025-08-24 22:09:55，当前版本为作者最后更新于2019-11-22 16:56:04，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

前言

UPD by 2020.11.30，找到了更优的解法

旧题解已转移至这里

一年前，我写这道题时弄出了一个“缩减二分长度”的优化

这项剪枝表现出了优异的效果，我没加什么优化就过了这题甚至没加快读

然后写了篇题解，通俗易懂，码风清新，备受好评

但是现在看来那篇题解写得太烂了，表述不严谨且仍有优化空间，于是我决定重新投一份$($配合旧题解食用更佳$)$

正片

一些变量/预处理

分块算法，首先我们要给块内排序，这里我们不使用结构体$($可以减小常数且代码更美观$)$

int a[N],lazy[N/block+5];//原数组，整体加标记 
int p[N];bool cmp(int x,int y){return a[x]<a[y];}//排序数组 
int main()
{
	int n,m;scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	B=(n-1)/block+1;
	for(int i=1;i<=B;i++)
	{
		bl[i]=br[i-1]+1;
		br[i]=br[i-1]+block;
	}br[B]=n;//分块基本操作 
	for(int i=1;i<=B;i++)
	{
		for(int j=bl[i];j<=br[i];j++)w[p[j]=j]=i;
		sort(p+bl[i],p+br[i]+1,cmp);
	}//对于一个块内的p数组，其对应的a数组是从小到大的 
	/*
	......
	*/
	return 0;
}

可以看到，$p$数组 反映了 $a$数组 的大小关系

修改

大段打 $lazy$标记，小段暴力修改 $a$数组，然后用归并排序的思想来维护 $p$数组

小段里面有两类数，一部分是不需要修改的数，另一部分则需要 $+k$

我们知道 $p$数组 存的是一堆下标，对应到 $a$数组 是排好序的

于是我们只要把 $p$数组 按上述规则划分开来，然后来个简单的归并即可维护

int c1[N],t1;
int c2[N],t2;//tmp数组 
void msort(int L,int R,int l,int r,int k)
{//块左端，块右端，区间加范围 
	t1=t2=0;//搞完以后c里面是一堆下标，对应a数组是从小到大的 
	for(int i=L;i<=R;i++)(l<=p[i]&&p[i]<=r)?a[c1[++t1]=p[i]]+=k:c2[++t2]=p[i];
	while(t1&&t2)p[R--]=(a[c1[t1]]>a[c2[t2]])?c1[t1--]:c2[t2--];//从大到小丢进去 
	while(t1)p[R--]=c1[t1--];
	while(t2)p[R--]=c2[t2--];//归并排序基本操作 
}

查询（重点）

二分答案，设二分值域为$L$和$R$，每次枚举$mid$

然后查询区间内 小于等于$mid$ 的数 的个数 $($记为$s)$

若 $s<k$，则 $mid$ 显然不为答案，令$L=mid+1$

若 $s>=k$，则令 $ans=mid$ ，$R=mid-1$

如何得知区间内 小于等于$mid$ 的数 的个数 呢？

再套一个二分就行，正常思路是小段暴力，大段用 $p$数组 二分

（优化1）

后来我发现，哎，为什么小段要暴力呢？

其实我们可以再弄一个 $c$数组，把小段像修改操作那样归并一下

然后我们就可以“在小段上二分了”

我原来的题解里是没有这个优化的，两端都是暴力统计（我太菜了）

当我想起来时，然后去看别人的题解，发现他们都加了。。。

（优化2）

预先确定二分的值域范围，不要直接$L=-2147483648$，$R=2147483647$

因为题目的数据有一句“每次加上的数和原序列的数在$[-2 \times 10^4 , 2 \times 10^4]$内”

（优化3）

这也是我在旧题解里面提出的一个大优化

假设我们某次枚举了一个$mid$，然后其中有一个块 $[l,r]$，我们得出 $[l,pos]$ 这些东西 小于等于$mid$

这一轮的 $mid$ 枚举结束后

若 $s<k$ ，则说明 $mid$ 比正确答案小了，那么以后我们枚举的$MID$就比这个$mid$大

那么对于上述的块 $[l,r]$，我们以后得出的位置一定大于等于$pos$

我们便可以把左端点拉过来，减少块内二分位置的区域

若 $s>=k$ ，那么以后我们枚举的$MID$就比这个$mid$小

那么对于上述的块 $[l,r]$，我们以后得出的位置一定小于等于$pos$

我们便可以把右端点拉过来，减少块内二分位置的区域

在随机数据下，这个优化快到离谱，但是也不是不能卡掉，hack数据很简单，然后可以把我的代码卡到10s

以下为hack数据生成代码

#include<ctime>
#include<cstdio>
#include<cstdlib>
#include<random>
using namespace std;
mt19937 rnd;
int random(int x){return (rnd()%x+x)%x;}//[0,x-1]
int main()
{
	freopen("1.in","w",stdout);
	rnd.seed(time(0));
	int n=100000,m=100000;printf("%d %d\n0",n,m);
	for(int i=2;i<=n;i++)printf(" 20000");
	puts("");
	for(int i=1;i<=50000;i++)puts("2 2 100000 20000");
	for(int i=50001;i<=100000;i++)puts("1 1 100000 100000");
	return 0;
}

不过很抱歉，这玩意是可以处理的

因为“每次加上的数和原序列的数在$[-2 \times 10^4 , 2 \times 10^4]$内”

这样会导致部分区间的值域范围大小很小

我们只要在块内二分前先判断一下，是否整个块都比$mid$大$/$小 $($优化4$)$

这样可以使得 优化3 变快不少，其他题解也提到了这个，不过lxl的数据很水，随便使用几个优化即可AC

复杂度

空间复杂度$O(N)$是跑不掉的

我的代码时间复杂度随机情况下是$O(N\sqrt{NΔ})$，最坏是$O(N\sqrt{N}Δ)$，其中$Δ$是二分次数，你大概可以看成20到30

这里的最优复杂度块长取$(\sqrt{NΔ})$，最坏复杂度块长取$(\sqrt{N}Δ)$

也就是说数据越随机，块长我就取得越小，代码就能跑得更快，但是数据毒瘤一点的话复杂度就会退化

至此，我们得出了一个空间复杂度为$O(N)$，时间复杂度是$O(N\sqrt{N}Δ)$的在线做法，但是因为剪枝多，跑得非常快，测了一下上面的hack数据，没加读入输出优化（只有O2）跑了2秒

但这个代码可以卡掉，经过与大佬的讨论，我们只需构造出多个相似的段，比如说$\sqrt{N}$个块长得一模一样而且里面$1$到$\sqrt{N}$每个数都出现一次，当然这种数据不常见，但是我们这是学术研究，不能随便口糊过去

于是这种做法就宣告失败了，但是这道题还是能过的

关于本题数据

lxl的数据水到什么程度呢？

如果你把上面的数据生成器弄出来的数据给目前所有题解测一下，你会发现都过不了（截至2020.11.30），TLE也就算了（最快的大概跑到5秒），但是有几个题解是WA？

然后看了下WA掉的题解，发现他们二分答案的初始范围是错的$($会爆$int)$

下面给出我的代码（抄就抄吧，抄不走我对分块的热情）

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=100005;
const int block=700;
int B,bl[N/block+5],br[N/block+5],w[N];//左，右，从属块 

int a[N],lazy[N/block+5];//原数组，整体加标记 
int p[N];bool cmp(int x,int y){return a[x]<a[y];}//排序数组 

int c1[N],t1;
int c2[N],t2;//tmp数组 
void msort(int L,int R,int l,int r,int k)
{//块左端，块右端，区间加范围 
	t1=t2=0;//搞完以后c里面是一堆下标，对应a数组是从小到大的 
	for(int i=L;i<=R;i++)(l<=p[i]&&p[i]<=r)?a[c1[++t1]=p[i]]+=k:c2[++t2]=p[i];
	while(t1&&t2)p[R--]=(a[c1[t1]]>a[c2[t2]])?c1[t1--]:c2[t2--];//从大到小丢进去 
	while(t1)p[R--]=c1[t1--];
	while(t2)p[R--]=c2[t2--];//归并排序基本操作 
}

int c[N],t;

int asl[N/block+5],asr[N/block+5],as[N/block+5];

int main()
{
//	freopen("1.in","r",stdin);
//	freopen("1.out","w",stdout);
	int n,m;scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	B=(n-1)/block+1;
	for(int i=1;i<=B;i++)
	{
		bl[i]=br[i-1]+1;
		br[i]=br[i-1]+block;
	}br[B]=n;//分块基本操作 
	for(int i=1;i<=B;i++)
	{
		for(int j=bl[i];j<=br[i];j++)w[p[j]=j]=i;
		sort(p+bl[i],p+br[i]+1,cmp);
	}//对于一个块内的p数组，其对应的a数组是从小到大的 
	
	while(m--)
	{
		int cz,l,r,k;scanf("%d%d%d%d",&cz,&l,&r,&k);
		int ql=w[l],qr=w[r];
		if(cz==1)//查询 
		{
			if(k>r-l+1){puts("-1");continue;}
			if(ql==qr)
			{
				for(int i=bl[ql],j=0;i<=br[ql];i++)
				{
					if(l<=p[i]&&p[i]<=r&&++j==k)
					{
						printf("%d\n",a[p[i]]+lazy[ql]);break;
					}//不要漏掉lazy标记... 
				}
			}
			else
			{
				t1=t2=t=0;//把小段取出来归并，不过要注意此时c数组的处理方式和修改操作不一样 
				for(int i=br[ql];i>=bl[ql];i--)if(l<=p[i])c1[++t1]=a[p[i]]+lazy[ql];//左边 
				for(int i=br[qr];i>=bl[qr];i--)if(p[i]<=r)c2[++t2]=a[p[i]]+lazy[qr];//右边 
				while(t1&&t2)c[++t]=(c1[t1]<c2[t2])?c1[t1--]:c2[t2--];//从小到大丢进去 
				while(t1)c[++t]=c1[t1--];
				while(t2)c[++t]=c2[t2--];
				
				if(ql+1==qr){printf("%d\n",c[k]);continue;}
				
				//然后的情况是从c数组和很多个大段里面找第k小，注意此时c数组是确定的值，且无需lazy标记 
				int L=c[1],R=c[t],ans;
				for(int i=ql+1;i<qr;i++)
				{
					L=min(L,a[p[bl[i]]]+lazy[i]);
					R=max(R,a[p[br[i]]]+lazy[i]);
					as[i]=asl[i]=bl[i]-1;asr[i]=br[i]+1;
				}as[0]=asl[0]=0;asr[0]=t+1;//找到最值以及预处理，这个下标0是给c数组用的 
				while(L<=R)//二分开始！ 
				{
					int mid=(L+R)/2,s=0,fucl,fucr,fucmid;//mid为二分值，s为比mid小或者等于mid的个数 
					fucl=asl[0]+1;fucr=asr[0]-1;
					if(fucl<=fucr)
					{
						if(c[fucr]<=mid){as[0]=fucr;fucl=fucr+1;}//优化 
						else if(c[fucl]>mid)fucr=fucl-1;
						while(fucl<=fucr)
						{
							fucmid=(fucl+fucr)/2;
							if(c[fucmid]<=mid){as[0]=fucmid;fucl=fucmid+1;}
							else fucr=fucmid-1;
						}
					}
					s+=as[0];
					if(s<k)
					{
						for(int i=ql+1;i<qr;i++)
						{
							fucl=asl[i]+1;fucr=asr[i]-1;//asl和asr是不可以踩到的地方 
							if(fucl<=fucr)
							{
								if(a[p[fucr]]+lazy[i]<=mid){as[i]=fucr;fucl=fucr+1;}//优化 
								else if(a[p[fucl]]+lazy[i]>mid)fucr=fucl-1;
								while(fucl<=fucr)//合法范围 
								{
									fucmid=(fucl+fucr)/2;
									if(a[p[fucmid]]+lazy[i]<=mid){as[i]=fucmid;fucl=fucmid+1;}//bl[i]~fucmid都小于等于mid 
									else fucr=fucmid-1;
								}
							}
							s+=as[i]-bl[i]+1;
							if(s>=k)//你s都大于等于k了说明什么，ans必能更新啊，还二分个锤子 
							{//mid的排名一定>=s，当s>=k时，mid>=k，此时可以更新答案ans 
								while(i>ql){asr[i]=as[i]+1;as[i]=asl[i];i--;}
								break;
							}
						}
					}
					if(s>=k)
					{
						asr[0]=as[0]+1;as[0]=asl[0];
						ans=mid;R=mid-1;//ans只会越来越小 
					}
					else
					{
						L=mid+1;asl[0]=as[0];
						for(int i=ql+1;i<qr;i++)asl[i]=as[i];
					}
				}
				printf("%d\n",ans);
			}
		}
		else //修改 
		{
			if(ql==qr)msort(bl[ql],br[ql],l,r,k);//使用归并思想处理小块 
			else
			{
				msort(bl[ql],br[ql],l,br[ql],k);
				msort(bl[qr],br[qr],bl[qr],r,k);
				for(int i=ql+1;i<qr;i++)lazy[i]+=k;//打标记 
			}
		}
	}
	return 0;
}

难道你觉得这份题解已经结束了吗？

并不，这题还剩一个条件没有用过，就是“离线”

有的人可能会问了，区间加还能离线？

那你可以康康这题（话说这题怎么时限变750ms了）

在某个奇妙的冬夜，我裹着被子翻来覆去，然后脑子里冒出了一个idea...

还记得我们二分答案后要求什么吗？区间有多少数小于等于$mid$

现在来这么一道经典题目，有两种操作

$1.$区间加 $k$

$2.$求区间内小于等于$k$的数的个数

其实这题是可以$O(N\sqrt{N})$离线做的（块长取$\sqrt{N}$），套用P4118的思想即可

那么我们只要应用这项黑科技，就可以直接大力二分答案

然后复杂度是$O(N\sqrt{N}Δ)$的，这种做法似乎和众多题解的复杂度相当

但是这里又能优化，就很离谱

以下内容不难，但是涉及上面的思想，而且我不会过于详细地解释

设块长为$B$，我们有$N$个小段修改，$\frac{N^2}{B}$个大段询问，

因为二分答案的缘故，我们要搞$Δ$次，每次重构会浪费很多复杂度

我们对比二分操作中询问的两个不同的$mid$，然后发现修改操作完全一致

于是我们可以先预处理出小段修改后的序列，这样可以将复杂度从$O(NΔ(B+\frac{N}{B}))$变成$O(N(B+Δ\frac{N}{B}))$，

然后块长取$(\sqrt{NΔ})$，复杂度似乎就是$O(N\sqrt{NΔ})$

但是这里有个小瑕疵，就是块长比块的数量大一些

每一个大段的询问均摊不是$O(1)$的，最终我们选取块长略大于$(\sqrt{NΔ})$

复杂度也许是$O(N\sqrt{NkΔ})$，其中 $k$ 近似于 $loglogN$ 级别

上面这部分本来是口糊的

但与大佬交流了一下，他说这样做还真的可以$O(N\sqrt{NkΔ})$

于是我们的新做法：时空复杂度都略大于$O(N\sqrt{NΔ})$，但是肯定比$O(N\sqrt{N}Δ)$小不少

虽然不及神仙的$O(N\sqrt{NlogN})$做法，但是这也不失为一种优秀的做法

结语

跟大佬交流，虽然看起来被D飞了，但是学到的真的不少

如果还有什么好的意见，欢迎提出