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

· · 题解

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;
}