自动搬运

查看原文

来自洛谷，原作者为

	XiaoShanYunPan 想成为一个好人

搬运于2025-08-24 22:59:01，当前版本为作者最后更新于2024-07-08 21:34:15，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

THUPC2024 古明地枣的袜子

古明地枣是谁？

题意

有一个长度为 $n$ 的序列。

给出 $n$ 个操作 $(x_i,y_i)$，每个操作为将 $a_1,a_2,\cdots,a_{x_i}$ 全部加上 $y_i$。

有 $m$ 次相互独立的询问，询问若 $a$ 初始全为 $0$，则做完操作 $(x_l,y_l),(x_{l+1},y_{l+1}),\cdots,(x_r,y_r)$ 后全局最大值为多少。

数据范围：$n,m\le 5\times 10^5$，时限 10s。

题解

（下面在计算时间复杂度时认为 $n,m$ 同级。）

zz 神仙讲的，虽然我没听。

观察数据范围和时限，首先排除单双 $\log$，因为这俩最多 2s。

猜测是个根号算法，那我们需要想办法分块。

下设块长为 $B$。

常见的分块要么对 $a$ 分，要么对操作分。

我们单纯对 $a$ 分会出现一堆操作挤在一个块内的情况，而对操作分块又可能出现块内操作太过分散的问题。

于是人类智慧地，把两者结合到一起，先将操作按 $x$ 排序后再分块，同时记录操作的时间戳。

这样子可以规避上面两种可能导致复杂度退化的情况，看上去就要优秀一些。

有了分块，接下来考虑怎么维护。

注意到我们询问是全局的，如果考虑每个块统计，那么想要做到一个根号就必须 $\mathcal{O}(1)$ 处理每个块的询问。

这样我们不得不进行预处理，设预处理出块 $b$ 在询问 $[l,r]$ 时的最大值为 $f_{b,l,r}$。

直接处理会发现我们连数组都存不下，肯定爆炸了。

但是注意到对于某个块内，有大量的询问是本质相同的，实际上一个块内最多只有 $\dfrac{B(B-1)}{2}$ 种本质不同的询问。

这样我们可以把 $l,r$ 离散化为块内对应的操作按照时间戳排序后的排名，空间复杂度就降下来可以存储了。

不过即使如此，怎么算出 $f$ 也是个关键的问题。

如果你想，你可以暴力套一个 $\log$，用线段树等 DS 简单维护一下，然后把 $B$ 平衡一下取到 $\mathcal{O}(n\sqrt{n\log n})$ 的时间复杂度。

但是，太烂了，我们需要严格根号算法。

注意到我们需要把操作排序之后才能够解决一个块内的答案。

这个时候人类智慧地意识到我们可以使用 归并排序。

在归并排序的分治过程中处理答案，看看怎么分治。

对于一个分治区间 $[l,r]$，它表示我们处理按照 $x$ 排序后的操作 $l$ 到 $r$。

此时我们能够得到两个更小区间里的 $f$，此时 $f_{i,j}$ 表示区间内时间戳排名为 $i$ 到 $j$ 操作做完后的最大值。

现在我们枚举 $f_{i,j}$，计算当前这个区间的答案。

分类讨论如何转移：

• 如果之前的最大值位于右半区间，此时它的所有贡献已经被算完，左边的其它操作无法对其产生贡献，直接令 $f_{i,j}$ 和右半最大值取 $\max$ 即可。
• 如果之前的最大值位于左半区间，此时右半区间的操作可以对其产生贡献，利用前缀和可以简单计算出贡献，令 $f_{i,j}$ 和加上贡献的左半最大值取 $\max$ 即可。

对于一个 $i,j$，我们意识到其对应的左右区间的情况是不同的。

详细来说，我们可以设在时间戳排名为 $[i,j]$ 的操作中，原本位于左半区间的为左半区间排名为 $[il,jl]$，同理设右半区间为 $[ir,jr]$，这个可以在归并排序时计算。

然后我们就可以利用 $il,jl,ir,jr$ 来转移 $f_{i,j}$ 了。

分析分治的时间复杂度会发现 $T(n)=2T(\dfrac{n}{2})+\mathcal{O}(n^2)=\mathcal{O}(n^2)$，而我们对每个块做此操作，总时间复杂度为 $\mathcal{O}(nB)$。

结合询问的总时间复杂度 $\mathcal{O}(\dfrac{n^2}{B})$，取 $B=\sqrt{n}$ 时最优，为 $\mathcal{O}(n\sqrt{n})$。

然后就是细节了：

• 注意到对于一个区间 $[l,r]$，如果一整个区间的操作的 $x$ 均相同，那么我们不能够直接用其信息转移更大的区间，因为更大的区间可能包含更多操作。

考虑下面一个例子：

在分治时左半区间有操作 $1,2$ 对 $a_1$ 进行修改，而右半区间有操作 $3$ 同样对 $a_1$ 进行修改。

在合并求解区间 $[1,3]$ 时，不能够取 $[3,3]$ 的最大值来转移，因为此时三个操作都被执行了，需要直接得到 $a_1$ 的最终结果。

假设操作 $3$ 令 $a_1$ 变得很大，此时我们的 $f$ 可能直接取到仅操作操作 $3$ 后 $a_1$ 的值，导致答案错误。

这个东西实现的时候稍微小心一点即可。

代码

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
constexpr int N=500010,B=666,INF=1e9;
struct operation
{
	int x,y,t;
	bool operator < (operation oth) {return x<oth.x;}
}op[N],sorted[N];
ll f[B+10][B+10],tmp[B+10][B+10];/*预处理答案*/
ll s[N];/*操作的y的前缀和，分治时需要动态处理*/
int now;
int pl[N],pr[N];
template<typename Type>inline void chkmax(Type &a,Type b){if(a<b)a=b;return;}
int change[N],cs[N];/*见正文细节部分*/
void solve(int l,int r)
{
	if(l==r)
	{
		f[l-now][l-now]=change[l]?op[l].y:-INF;
		return;
	}
	int mid=(l+r)>>1;
	solve(l,mid),solve(mid+1,r);
	s[mid]=0;
	for(int i=mid+1;i<=r;i++)s[i]=s[i-1]+op[i].y;
	pl[l-1]=l-1,pr[l-1]=mid;
	for(int i=l,j=mid+1,k=l;i<=mid||j<=r;k++)
	{
		if(j>r||(i<=mid&&op[i].t<op[j].t))sorted[k]=op[i],i++;
		else sorted[k]=op[j],j++;
		pl[k]=i-1,pr[k]=j-1;
	}
	for(int i=l;i<=r;i++)op[i]=sorted[i];
	for(int i=l;i<=mid;i++)for(int j=i;j<=mid;j++)tmp[i-now][j-now]=f[i-now][j-now];
	for(int i=mid+1;i<=r;i++)for(int j=i;j<=r;j++)tmp[i-now][j-now]=f[i-now][j-now];
	for(int i=l;i<=r;i++)
	{
		for(int j=i;j<=r;j++)
		{
			/*计算f[i][j]*/
			f[i-now][j-now]=-INF;
			int il=pl[i-1]+1,ir=pr[i-1]+1,jl=pl[j],jr=pr[j];
			if(cs[mid]-cs[l-1])chkmax(f[i-now][j-now],tmp[il-now][jl-now]+s[jr]-s[ir-1]);
			if(cs[r]-cs[mid])chkmax(f[i-now][j-now],tmp[ir-now][jr-now]);
		}
	}
	return;
}
struct question{int l,r;ll ans=-INF;}q[N];
int n,m;
ll suf[N];/*后缀和*/
int rt[N];/*t为i的op的编号*/
int rk[N];/*对应在此块内的排名*/
inline void Calc_Block(int l,int r)
{
	now=l-1;
	for(int i=l;i<=r;i++)for(int j=i;j<=r;j++)f[i-now][j-now]=-INF;
	solve(l,r);
	suf[0]=0;
	for(int i=1;i<=n;i++)suf[i]=suf[i-1]+(rt[i]>r?op[rt[i]].y:0);/*把后面的块的操作预处理*/
	rk[1]=1;
	for(int i=1,j=l;i<=n;i++)
	{
		if(i==op[j].t)j++,rk[i+1]=rk[i]+1;
		else rk[i+1]=rk[i];
	}
	for(int i=1;i<=m;i++)if(cs[r]-cs[l-1])chkmax(q[i].ans,f[rk[q[i].l]][rk[q[i].r+1]-1]+suf[q[i].r]-suf[q[i].l-1]);
	return;
}
template<typename Type>inline void r(Type &x)
{
	x=0;
	char c=getchar();
	bool f=c=='-';
	while(c<'0'||c>'9')c=getchar(),f|=c=='-';
	while(c>='0'&&c<='9')x*=10,x+=c-'0',c=getchar();
	if(f)x=-x;
	return;
}
int main()
{
	r(n),r(m);
	for(int i=1;i<=n;i++)r(op[i].x),r(op[i].y),op[i].t=i;
	for(int i=1;i<=m;i++)r(q[i].l),r(q[i].r);
	sort(op+1,op+n+1);
	n++,op[n]={n,0,n+1};//UKE
	for(int i=1;i<=n;i++)change[i]=op[i-1].x!=op[i].x,cs[i]=cs[i-1]+change[i];
	for(int i=1;i<=n;i++)rt[op[i].t]=i;
	for(int i=1,j=B;i<=n;i+=B,j+=B)Calc_Block(i,min(j,n));
	for(int i=1;i<=m;i++)printf("%lld\n",q[i].ans);
	return 0;
}

鸣谢

参考文章：https://www.cnblogs.com/peiwenjun/p/18257226 ，膜拜 peiwenjun 佬。

代码实现是我自己敲的，但是对着佬的代码看了半天所以敲得都一样了。