P4556 题解

STDLRZ · 2025-05-11 15:02:59 · 题解

本题解总结了大部分原题解里面的做法，并且对其加以详细讲解，目的是让大家可以更好的理解题解的思路。

同时，作者本身也添加了几种方法供大家参考。

因为作者是个蒟蒻，所以若该题解有问题，请指出，感激不尽！

方法 1

前置知识：动态开点线段树、树上差分、LCA。

参考 @shadowice1984 的做法。

做法 & 思考

首先，考虑本题存放救济粮这个操作有什么特点。

因为救济粮可能有很多种，于是就需要用值域线段树。

但是很明显将所有点全部来一棵值域线段树，然后又依次修改肯定是不现实的。

于是考虑树上差分，将一次操作差分成对四个点 x,y,LCA(x,y) 以及 LCA(x,y) 的父亲进行操作。

接着，因为需要做一次类似于前缀和的操作，而一个节点 x 的最终状态是以 x 为根的子树里所有的线段树全部合并起来所得到的最终结果。

考虑如何对线段树进行合并。

我们充分发挥人类智慧，显然如果两个节点 x,y 在合并时已经有一个节点为空，那么直接返回就行。

理解的话，就是相当于把那个不为空的节点的子树给黏贴一份到他的父亲的下面。

然后，如果 x,y 均为叶子节点，我们就需要对其进行相加操作。

理解的话，就是最终 x 的结果肯定是他子树所有救济粮的个数加起来，再去算，而不是全部取 \max。

对于其他情况，则递归到左儿子和右儿子进行合并。

本题该部分该部分代码长这样：

int merge(int x,int y,int l,int r){
    if(!x || !y) return x|y;
    if(l==r) {mx[x]+=mx[y];return x;}
    int mid=(l+r)>>1;
    ls[x]=merge(ls[x],ls[y],l,mid),
    rs[x]=merge(rs[x],rs[y],mid+1,r),
    mx[x]=max(mx[ls[x]],mx[rs[x]]);
    return x;
}

变量含义：ls[x] 为线段树节点 x 的左儿子，rs[x] 为线段树节点 x 的右儿子，mx[x] 为线段树节点 x 所存储的最大值。

时间复杂度证明

线段树合并的时间复杂度是 \mathcal O(n \log n) 的。

证明如下：

设当前 merge 到的两个节点分别为 x,y，现在，我们要将以 rtx 节点为根的线段树和以 rty 节点为根的线段树合并。

首先，一个位置能被递归到，证明这两个位置都有节点（只有一个节点不为空的直接返回了）。

这样，接下来 y 节点在接下来的线段树合并中就不会用到了，因为被 x 节点合并成一个点了（由代码可知）。

这样的话，那些对时间复杂度产生贡献的 x 节点，肯定是在函数 merge(x,y,l,r)，y 节点为空时才会继续往下遍历。

但是，这些 x 节点一旦遇到这种情况则会直接返回，产生的代价为 1。

这样，最多当 y 节点为空，x 节点不为空的时候，x 节点产生一次贡献。而这一次接上去之后，这棵线段树的这个位置上将不会为空。

否则，则为 y 节点产生一次贡献，然后不再产生任何贡献。

为了方便分析，我们可以在一个节点 x 遍历左右儿子节点的时候，先特判一下 if(!x || !y) return x|y; 的情况，如果不满足再递归下去，则此时单个节点仍然最多访问 1 次。

又考虑到原来的 n 棵线段树共有 \log n 个节点，所以综上，时间复杂度为 \mathcal O(n \log n)。

至于空间复杂度，已经在证明里面分析出来了，也是 \mathcal O(n \log n)。

代码 & 实现细节

但是注意，在代码里面，因为一次操作被拆分成了 4 个点，所以此时会约有 4n(\log n+2) 个节点同时存在。

稍微算一下，最坏情况下要开 80 倍的 n。当然可能有优化常数方法，那我就不太清楚了。

方法 1 代码。

扩展部分

有一些题目的线段树合并，可能合并之后要访问合并之前的数据，此时这种做法将会失效。

我们可以先对这两棵线段树做一份备份，但是带来的代价就是，空间常数会翻 2 倍。

在做题目的时候可以留心注意一下两者的区别。这里就没有另写一份代码来展示这种做法了。

方法 2

其实方法 2 挺傻的（没有方法 1 聪明），这里只是稍微提一下思路，并给出代码。

前置知识：动态开点线段树、启发式合并、LCA。

做法 & 思考 & 时间复杂度

考虑方法 1 中线段树合并的弱智做法。

我们可以比较两棵线段树节点的个数，选一棵节点少的合并到节点多的即可。

这样的话，共有 n \log n 个线段树节点，而启发式合并带一只 \log n，所以时间复杂度是 \mathcal O(n \log^2 n) 的，我写的是空间复杂度为 \mathcal O(n \log^2 n) 的版本。

其实挺像方法 1 的代码的，有兴趣的人可以比较比较两个代码之间的差异。

但不过看起来这个方法没意义。。。

令人惊奇的是，跑的跟方法 1 差不多快，可能是数据没卡吧。

代码

方法 2 代码。

扩展部分

听说用 \tt Splay 可以做到 \mathcal O(n \log n) 的时间复杂度合并，说不定把线段树稍微换一下会有奇效呢！

感兴趣的可以去看一看别的题解怎么写 \tt Splay 的（有写，这里就不赘述了。）

方法 3

前置知识：值域线段树、莫队、树上差分、LCA。

做法 & 思考

因为不能真的给每个节点都分一次救济粮，这样就凉凉了。

所以我们还是考虑树上差分，一个操作对四个点进行操作。

然后，利用 \tt dfn 序的性质：以 x 为根的子树的 \tt dfn 编号是连续的（x 可任意），可以想到，先将所有节点的编号转为 \tt dfn 编号，如果我能求一段区间内的 tag 全部加起来，那我们照样也可以做这道题了。

考虑一个最垃圾的做法，树套树。

但是对于这一道题，线段树中的每一棵线段树看起来需要进行 \mathcal O(\log n) 次合并操作才能查询。

问题就出在这里。如果真的合并，你肯定要先合并线段树上的叶子节点是吧。那已经超时了，时间复杂度达 \mathcal O(n^2)（甚至更高），这个方法没得玩了。

但是，莫队是个好东西啊。你可以放 n 个询问区间进去，然后莫队一下，所有的询问结果就出来了。

这样的好处是，我们只需要用一棵线段树就可以解决问题。

坏处是，时间复杂度为 \mathcal O(n \sqrt[2] n \log n)。

此处空间复杂度为 \mathcal O(n \log n)（因为树上倍增的原因，但是可以优化到 \mathcal O(n)，用树链剖分求 \tt LCA 即可）。

时间复杂度证明

假设 n 与 m 同阶，则时间复杂度 \mathcal O(n \sqrt[2] n \log n) 证明：

设第 i 个块中有 t_i 个 tag，有 s_i 个区间的左端点在第 i 个块中。

则由莫队特性——先按照左端点所在的块编号排序，在一样的情况下按照右端点从小到大排序可得第 i 个块对时间复杂度的贡献：

由 n,m 同阶，且操作总次数（每一个点操作的次数的总和）为 n（准确来说应该是 4n，这里忽略常数），有：

设其为 1 式。

则原式用 1 式化简可得：

考虑 \tt dfn 序的性质。

对于同一个节点 x 的 \tt dfn 序区间（以 x 为根的子树的 \tt dfn 范围，下同）的儿子的 \tt dfn 序互不相干。

并且每一个节点 x 的 \tt dfn 序区间的左端点都不一样。

为什么呢？很好证明（甚至不用证）。节点 x 的 \tt dfn 序区间的左端点是 dfn_x（以 x 为根的树第一个访问的肯定是 x 节点），而每一个点的 \tt dfn 都是不一样的，所以左端点也就不一样了。

利用这个性质，我们得知 s_i=\sqrt[2]n，带入原式，得：

则时间复杂度式子为：

拆开，得：

用 1 式化简，可得最终结果为 2n \sqrt[2]n，忽略常数为 n \sqrt[2]n。

因为线段树一次操作时间复杂度为 \mathcal O(\log n)，所以综上，时间复杂度为 \mathcal O(n \sqrt[2]n \log n)。

扩展 & 为什么要证明时间复杂度？

相信很多人有这个疑问：为什么要证明？这不是很显然的嘛？

不不不，那就错了。

根据证明中的一个式子（第 i 个块对时间复杂度的贡献）：s_i \cdot t_i+n，其实说明了一些问题。

现在，让我们思考一下，能不能把这个算法卡掉呢？

由这个式子，我们知道，后面的一项 n 已经卡不了了，于是我们想办法卡前面的。

我们可以让所有操作都集中在第 i 个块内的点中，这样就有 t_i=n 了。

然后，我们可以让所有的询问的左端点全部集中在第 i 个块内，那么又有 s_i=n。

欸，这样时间复杂度不就变成了 n^2+n \sqrt[2] n 了嘛？

这就是问题所在。但是真实可不可以卡呢？（前面只是理论可卡）

其实是可以的。我们设第一个块的左端点为 1，右端点为 k(k=\lfloor \sqrt[2]n \rfloor)，那么可以有如下询问：

第 i 个询问：

• 若 i 为奇数，则区间为 [1,k+i]；
• 若 i 为偶数，则区间为 [k,k+i]。

这样，右端点总贡献是 n，但是左端点不断的在整个块内横扫（从 1 扫到 k，又从 k 扫到 1，以此类推）。我们将所有的操作全部都集中到 [2,k-1] 中，这样每一次扫，都需要 \mathcal O(n) 的时间。

但是因为有 n 个区间（上面的询问个数至少也有 n-k 个，而 k 很小，直接忽略），所以时间复杂度为 \mathcal O(n^2+n)。

但是为什么本题是正确的呢？

因为 \tt dfn 序有一个特点：左端点互不相同。

这样我们就控制了 s_i，使得 s_i=\sqrt[2]n，然后再化简式子，就得到了正确的结果。

所以，以后如果有题目，说左端点互不相同，说不定就可以用上莫队了呢！

代码

温馨提示：

• 请使用 vector，若您使用链式前向星，则您有可能会 TLE。
• 因为本题莫队带了 4 倍常数，所以请使用奇偶性优化，否则也可能会 TLE。
• 您的线段树的左儿子和右儿子请不要写成 x*2 和 x*2+1，应该要写成 x<<1 和 x<<1|1，否则也有可能过不了。
• 其他卡常方法。

方法 3 代码。

方法 4

做法 & 思考

前置知识：树链剖分、线段树、差分。

参考 @x义x 的做法。

容易想到，我们不一定要树上差分，我们如果能将树上的一条链给搞成多段连续区间，再差分也是可以的。

所以，我们使用树链剖分将树上的一条链剖成 \log n 个连续区间，然后再进行差分，使得左端点添加 z 种类救济粮，右端点 +1 减少 z 类救济粮即可。

这样，我们只需要算一遍前缀和，我们就可以知道所有节点的答案了。

具体的，若 dfn_x=u，则设 fid_u=x，则算完 1 \sim x 的前缀和后，你就算出来了 fid_x 节点的答案。

在本题来说，除了 \mathcal O(n \cdot \alpha(n)) 的解法（或者说是 \mathcal O(n) 吧，\alpha(n) 直接看成常数，当然题解区确实有一个严格 \mathcal O(n) 的做法），其他的都不如他快了。

树链剖分的常数是很小的，所以本题中，若没有和其他常数很大的数据结构结合，那么这种做法已经算是很优了。

时间复杂度为 \mathcal O(n \log^2 n)，并不需要证明，学过树链剖分的都知道。

但不过看在 oi-wiki 也没有的份上，我就给个链接（我自己写的），这里就不偏题了，有兴趣的可以自己去看。

树链剖分时间复杂度证明。

总结

有的时候在树上合并线段树很困难，就可以先转成序列再差分就简单许多倍。

代码

方法 4 代码。

方法 5

前置知识：树链剖分、动态开点线段树、值域线段树、并查集。

暴力

参考 @AC_love 的做法。

首先，我们考虑不差分怎么办。

不差分？首先需要使用树链剖分，先将问题转换为多段连续的区间。

接下来，因为把这些救济粮真的发给他们实在是太不现实了，于是我们转而考虑统计 y 节点有第 x 种救济粮，并且对于每一个救济粮开一个线段树存起来就行了。

这里需要用到动态 \tt push\_down 开点线段树，具体代码如下：

void push_down(int x){
    if(lazy[x]){
        if(!ls[x]) ls[x]=++idcnt;
        if(!rs[x]) rs[x]=++idcnt;
        lazy[ls[x]]+=lazy[x],lazy[rs[x]]+=lazy[x],
        mx[ls[x]]+=lazy[x],mx[rs[x]]+=lazy[x],
        mn[ls[x]]+=lazy[x],mn[rs[x]]+=lazy[x],lazy[x]=0;
    }
    return ;
}
void upd(int &x,int l,int r,int fl,int fr){
    if(!x) x=++idcnt;
    if(l==fl && r==fr) {++mx[x],++mn[x],++lazy[x];return ;}
    push_down(x);
    int mid=(l+r)>>1;
    if(fr<=mid) upd(ls[x],l,mid,fl,fr);
    else if(fl>mid) upd(rs[x],mid+1,r,fl,fr);
    else upd(ls[x],l,mid,fl,mid),upd(rs[x],mid+1,r,mid+1,fr);
    mx[x]=max(mx[ls[x]],mx[rs[x]]),
    mn[x]=min(mn[ls[x]],mn[rs[x]]);
    return ;
}

变量含义：ls[x],rs[x] 分别为 x 的左儿子和 x 的右儿子，mx[x],mn[x] 分别为线段树节点 x 所存储的最大值和线段树节点 x 所存储的最小值，lazy[x] 为懒标记，idcnt 为节点编号。

考虑如何统计答案。

首先，考虑到要统计哪个救济粮数量最多，先从单个救济粮的数量入手。

引理 1 & 证明

先来个引理 1：

• 经过 t 次上面的 upd 后，线段树最多会分为 2t+1 段极大且值相同的段。对于一段值相同且极大，仅当这一段的所有位置的值都为某个数废话，该区间极大仅当这个区间的左端点和右端点都不能延申了。

证明：

我们发现，刚开始就有 1 段，这就是 1 的来历。

假设之前有 x 段极大值相同的段（以后简写为 m-s 段），那么这一次的修改操作可能导致的结果如下：

• 这一次修改是对其中一个 m-s 段内进行了一次 +1 操作。
• 这一次修改是对 k 个 m-s 段进行了一次 +1 操作，其中中间的 k-2 段被完全覆盖，开头和结尾两段可能被完全覆盖，也可能只是被覆盖部分。

对于第 1 种情况，如果完全覆盖该 m-s 段，则不会产生新的 m-s 段；如果只覆盖了左端点或者右端点，则会产生 1 个新的 m-s 段（两段分裂），否则就会新产生 2 段 m-s 段。

对于第 2 种情况，对于中间的 k-2 个 m-s 段不会产生新的 m-s 段，讨论最左边和最右边的两个 m-s 段。

若最左边和最右边的 m-s 段都被完全覆盖，则不会产生新的 m-s 段；

若最左边 m-s 段的左端点未被覆盖，而最右边的 m-s 段被完全覆盖，则会产生 1 个 m-s 段；

若最右边 m-s 段的右端点未被覆盖，而最左边的 m-s 段被完全覆盖，则会产生 1 个 m-s 段；

否则会产生 2 个 m-s 段。

综上，每一次分裂最多产生 2 个 m-s 段，t 次分裂后最多产生 2t+1 个 m-s 段。

运用引理 1

我们只需要找到值相同的极大 m-s 段，然后对这一段区间进行答案更新即可。

对于每一个 m-s 段，最多会分为 \log n 段进行修改，但是最多会有 n \log n 个 m-s 段，所以这一部分的时间复杂度为 \mathcal O(n \log^2 n)。

考虑如何修改答案。

我们维护一段区间的答案的最小值，如果当前答案比这段区间最小的答案还要裂，则不管；否则更新。

这一次修改，每一个点最坏情况下会被修改 2\sqrt[2]n 次。

至于为什么是这样，很好解释。最坏情况如下：第一次修改，答案被更新为只有一包救济粮的那种，第二次修改，答案被更新为只有两包救济粮的那种，以此类推，第 2\sqrt[2]n 次修改，答案会被更新为只有 2\sqrt[2]n 包救济粮的那种。

所以，有：

所以解释完毕。

因为每一个点递归修改需要 \log n 的时间（代码里面分了 3 段函数，那就是 3 \log n），所以时间复杂度为 O(n \log^3 n+n \sqrt[2]n \log n)。

时间复杂度说明

为什么是 n \log^3 n+n \sqrt[2]n \log n 呢？

首先，我们看第一项：他是 n \log^2 n \cdot \log n，其中 n \log^2 n 表示共有 n \log^2 n 段要进行答案更新。

我们来考虑如下情况。

首先，如果一段没有要更新的，那么在这一段被分成了 \log n 段后，程序就会意识过来，没有必要继续往下递归了，就会自己终止，这部分的时间复杂度为 O(n \log^3 n)。

否则，如果有一个点要更新，那么就会再走 \log n 的距离去更新这个点，因为每一个点都要走 \log n 的距离才能得到更新，所以这一部分的时间复杂度就是 \mathcal O(n \sqrt[2] n \log n) 的。

所以时间复杂度就是这么多。

可以通过。

代码

方法 5 暴力代码。

优化

有的人肯定会说了，你这时间复杂度是不是太逆天了，该优化优化了吧。

我们这里来搞搞优化。

首先，我们不用每一次都去更新他的答案，想想可不可以只更新一次就行。这样就更好了。

我们只需要保存下来每一次要更新的东西，然后排一下序，再从大到小更新一遍，更新过的不管，没更新过的更新，这样就可以了。

时间复杂度此时被我们优化到了 \mathcal O(n \log^3 n+(n \log^2 n) \cdot \log(n \log^2 n)，其中 \log(n \log^2 n) 的意思不是 n \log^3 n，意思是对 n \log^2 n 取以二为底的对数。

考虑能不能进一步优化。

首先，对于排序，因为每一个更新都有两维，第一维是这种救济粮的包数，第二维是救济粮的编号。因为两者均小于 10^5，做类似于基数排序的操作，先对第二维排个序，再对第一维排个序，排序的时间复杂度就能被优化到 \mathcal O(n \log^2 n)。

考虑对第一部分进行优化。

我们发现，并查集最适合搞这种只覆盖一次的问题了。直接用并查集跳过那些已经被更新的点不就行了么？

不不不，那你的时间复杂度也并没有优化，仍然是 \mathcal O(n \log^3 n) 的。因为只使用路径压缩最坏还是 \log 的。

我们只要能够有办法，再使用一个按秩合并就可以做到常数级了。

对此，我的解决办法是，定义一个 bid_i 表示这个点实际所代表的位置，初始值有 bid_i=i。

假设我们现在要使 fa_x=y，如果此时 sz_y 更小，则我们在将 x 合并到 y 后，将 bid_x 和 bid_y 互换一下，这样我们得到的 bid_y 就是 y 此时代表的真实编号。

可以自己举几个例子模拟一下。

然后至于在更新的时候，注意要访问到的是那个真实的点 bid_x，不是那个没有实在意义的 x！！

该部分代码：

for(int i=1;i<=gxcnt;++i){
  int l=gx[i].l,r=gx[i].r;
  int x=find(l);
  while(bid[x]<=r) ans[bid[x]]=gx[i].id,merge(bid[x],bid[x]+1),x=find(x);
}

其中，merge 表示并查集合并，gx 表示那 n \log^2 n 个更新答案的东西。

这样我们就以非常妙的方法使得时间复杂度变为 \mathcal O(n \log^2 n \alpha(n)) 了，直接忽略掉 \alpha(n) 即可，这是常数级。

但是，咱就是说，因为没差分的原因，常数比人家要大几倍。

代码

方法 5 优化代码。

总结

所有的只用路径压缩没用按秩合并的都可以通过 bid 这个巧妙的数组转换为既用按秩合并又路径压缩的并查集，时间复杂度直接优化到常数级。

结尾

方法 6 那个 \mathcal O(n) 我现在是实在不会，等我学了虚树后一定过来补。

至于那个并查集，我觉得通过这篇题解，那些只按秩合并的并查集的时间复杂度都将不是问题，因为 bid 帮我们解决了所有问题。

说句实话，希望那群卡只按秩合并的并查集的人不要恨我！