自动搬运

查看原文

来自洛谷，原作者为

	R_8x 你充Q币吗

搬运于2025-08-24 23:17:53，当前版本为作者最后更新于2025-06-10 20:12:13，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

P12751 [POI 2017 R2] 集装箱 Shipping containers - 题解

不知道各位大神都是用的是什么做法，但是我使用了根号分治。

思路：

首先，本题要求对序列进行修改操作，很像数据结构题，但是像线段树这种数据结构只能对连续区间进行加和，并不能处理这种操作，所以肯定不能通过此题。

先想想数据范围较小的情况，我们可以直接暴力模拟，对答案数组跳着加一，理论时间复杂度是 $O(nq)$ 的，但是如果询问的 $d_i$ 较大时，这种暴力模拟的时间复杂度可能会很优，甚至在 $d_i$ 接近 $n$ 的时候达到常数级别。当然，直接暴力模拟肯定会超时。

然后我们很容易想到一种简单的算法：我们可以认为每一次要修改的下标是一个等差数列，然后把操作离线，按 $d_i$ 排序，然后处理 $d_i$ 相同的操作。对于 $d_i$ 相同的操作，我们可以维护差分数组，对等差数列的首项加一，末项的下一项减一，然后对差分数组求前缀和……不是普通的前缀和，而是跳着加（常规的前缀和是 w[i]+=w[i-1]，而我们需要 w[i]+=w[i-d]）。

但很明显，在处理的 $d_i$ 种类很多时，这种做法的时间复杂度也会变劣，所以第二种方法也不能通过此题。

难道这题就这样变得无解了吗？

当然不是，我们还有利器——根号分治（不会的同学可以看一下 这位大佬的文章，并完成模版题 CF1207F）。注意到第一种思路在 $d_i$ 较大时会较优，而第二种思路在 $d_i$ 种类较少时更优，且第二种思路不会因为 $d_i$ 较小而变劣。所以我们仍然可以将操作离线，按 $d_i$ 排序，设 $lim$ 为 $\sqrt{n}$，当 $d_i$ 小于 $lim$ 时使用第二个思路，否则使用第一个思路，这样就会使算法时间复杂度达到 $O(q\sqrt{n})$，可以通过此题。

代码：

#include<bits/stdc++.h>
using namespace std;
int d[200005],ans[200005];
int n,q;
struct node
{
	int a,l,d;
}que[100005];
int lim;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>q;
	lim=sqrt(n);
	for(int i=1;i<=q;i++)
		cin>>que[i].a>>que[i].l>>que[i].d;
	sort(que+1,que+q+1,[](node x,node y){return x.d<y.d;});
	int pre=que[1].d;
	for(int i=1;i<=q;i++)
	{
		if(que[i].d<lim)
		{
			if(que[i].d==pre)
				d[que[i].a]+=1,d[que[i].a+que[i].l*que[i].d]--;
			else
			{
				for(int j=pre;j<=n;j++)
					d[j]+=d[j-pre];
				for(int j=1;j<=n;j++)
					ans[j]+=d[j],d[j]=0;
				pre=que[i].d;
				d[que[i].a]+=1,d[que[i].a+que[i].l*que[i].d]--;
			}//第二种思路
		}
		else
		{
			for(int k=que[i].a,j=1;k<=n&&j<=que[i].l;k+=que[i].d,j++)
				ans[k]++;
		}//第一种思路
	}
	for(int i=pre;i<=n;i++)
		d[i]+=d[i-pre];
	for(int i=1;i<=n;i++)
		ans[i]+=d[i];//注意细节，这里差分数组会被少加一次，所以要另外加
	for(int i=1;i<=n;i++)
		cout<<ans[i]<<" ";
	return 0;
}