THUPC2024 古明地枣的袜子

· · 题解

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}，计算当前这个区间的答案。

分类讨论如何转移：

对于一个 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})。

然后就是细节了：

考虑下面一个例子：

在分治时左半区间有操作 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 佬。

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