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

GW_tzym · 2025-11-05 17:24:12 · 题解

::::info[闲话] 在某场神秘的比赛的T2，我想到了类似于根号分治的解法，但由于没有见过根号分治，所以阈值选错了，想来练练这种题，结果由于数组开小了，被虐的死去活来。。。遂写题解纪念一下 :::: 题意很清楚，讲一下为什么是根号分治。初看此题，我们有种十分简单且暴力的做法：模拟一遍，但这样的话复杂度是 O(\sum l) 的当 d 很小的时候，l 可能很大，导致超时。反过来当 d 很大的时候，l 不可能很大，原因就是他给的限制：

满足 a+d \times (l-1) \le n

那这个 d 多大才算大呢？答案是 \sqrt n ~要不然叫根号分治~。对于大于 \sqrt n 的 d，我们直接暴力修改就行，对于 d 小的情况呢？我们可以按 d 分类，把操作记在差分数组里，然后 O(n) 做前缀和，答案累加，输出即可。
然后再给个提示（就是这个）数组要开到 2 \times 10^5。因为他保证 a+d \times (l-1) \le n 但没保证 a+d \times l \le n，所以在差分时会越界。

#include<iostream>
#include<cmath>
using namespace std;
unsigned int ans[200010];
unsigned int c[200010][320];
int main()
{
    int n,k;
    cin>>n>>k;
    int num=sqrt(n);
    //int num=316;开静态的动态的都行，自己设一个也行
    for(int i=1;i<=k;i++)
    {
        int a,d,l;
        cin>>a>>l>>d;
        if(d>num)
        {
            for(int j=0;j<l;j++)
            {
                ans[a+(j*d)]++;
            }
        }
        else
        {
            c[a][d]++;
            c[a+(d*l)][d]--;
        }
    }
    for(int i=1;i<=num;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(j>=i)c[j][i]+=c[j-i][i];
            ans[j]+=c[j][i];
        }
    }
    for(int i=1;i<=n;i++)
    {
        cout<<ans[i]<<" ";
    }
}