标签：10 le num val max 乱讲区间杂题最优化

你校的最优化杂题乱讲。

保证难度随机排序，使用 mt19937 生成题目序列。

最优化问题往往使用贪心，dp，二分，最短路解决。

其中贪心往往可以通过感性理解，凭借人类本能想到贪心方式，继而写出正解，但有些比较厉害的题目却需要进行严谨的证明，而且可能会推出与感性结论相差很大的结论。

dp 则需要一定的积累或者自己的灵光一现先推出转移方程，再在转移方程之上考虑如何优化到可以接受的复杂度，所以先推出暴力方程实际上还是比较重要的。

Waterfront eJOI2021

现有 \(n\) 丛初始高度为 \(h_i\) 的灌木。每丛灌木每天都会生长 \(g_i\) 的高度。

每天在灌木生长完毕后，园丁将对灌木剪枝 \(k\) 次。每次可以将任意一丛高度不小于 \(x\) 的灌木剪短 \(x\) 个单位。

求 \(m\) 天后最高的一丛灌木的高度的最小值。

\(1 \le n, m \le 10^4 , 1 \le k \le 1000\)。

注意到我们要关注的实际上是最后一天的灌木高度，如果最高的灌木没办法被剪短，那么即使去剪其他的灌木也是无济于事的，而且天数越大，能剪短的灌木也会变多，所以尽可能的在早的天数剪短当前第 \(m\) 天最高的灌木直到不是最高或是无法再剪肯定是不劣的。

另外注意一个问题就是我们在找最早可剪天的时候不能每次都从头找，要用指针记录下每次的最早可剪天，对于所有的灌木的指针，他们最多不会移动超过 \(MN\) 次，而剪短灌木的次数不会超过 \(Mk\) 次，总时间复杂度为 \(O(MN+Mk\log_2N)\)。

不加指针的复杂度就是 \(O(NMk\log_2N)\)。

Difficult Mountain CF1601D

\(n\) 个人相约去爬山，山的初始攀登难度为 \(d\)，每位登山者有两个属性：技巧 \(s\) 和整洁度 \(a\)。

技巧为 \(s\) 的登山者能登上攀登难度为 \(p\) 的山当且仅当 \(p\le s\)。在一位整洁度为 \(a\) 的登山者登上攀登难度为 \(p\) 的山后，山的攀登难度会变为\(max⁡(p,a)\)。

请给这些登山者指定一个爬山的先后顺序，最大化登上山的人数。

如果轮到一位登山者时他能登上山，则他一定会选择登山。

\(1\le n\le5\times 10^5,0\le d,s_i,a_i\le10^9\)。

此题有两种解法，第一种 dp，第二种神仙贪心。

Sol1:

我们不知道上山顺序是怎么安排的，但我们知道山的高度是递增的，把所有的 \(s_i\ge d\) 的登山者都拉出来然后按 \(a_i\) 排序，令 \(f_i\) 表示由第 \(i\) 个登山者更新高度时最大的登山人数是多少，转移方程还是比较好推的：

\[\large f_i=\max_{0\le j\le x} f_j+num_{j,i-1,a_i}+1 \]

因为 \(i\) 要上山需满足 \(s_i\ge a_j\)，所以 \(x\) 是满足这个等式最大的 \(j\)。\(num_{j,i-1,a_i}\) 表示在 \([j,i-1]\) 中 \(s_j\ge a_i\) 的人的数量。

这个 \(num\) 维护方式有很多种，你可以选择使用两只老鸽的树套树（虽然可能过不去），也可以选择写大常数一只老鸽的主席树或是什么别的东西。

当然因为题解的线段树优化我没看懂而且我写的线段树优化跑的比题解要快了不少，这里介绍一下我的优化方式。

我们考虑拆一下 \(num\) 的贡献:

\[\max f_j+num_{j,i-1,k}+1=\max f_j+num_{0,i-1,k}-num_{0,j,k}+1=\max (f_j-num_{0,j,k}) +num_{0,i-1,k}+1 \]

乍一看不是很好维护的样子，但是我们有个很聪明的想法，我们不好在 \(i\) 处知道 \(num_{0,j,a_i}\)，但是我们可以把 \(-num_{0,j,a_j}\) 也同 \(f_j\) 一起丢进线段树里，接着考虑到 \(a_i\) 是递增的，而对于 \(s_j<a_i\) 这样的只会减少一次贡献，我们就可以把扫过的位置的 \(s_i\) 丢进堆里，每次转移前就把 \(s_j<a_i\) 的弹出，并对区间 \([j,i)\) 加 \(1\)，这样不仅保证了在线段树里的 \(num\) 是在 \(i\) 上的 \(num\)，而且堆的大小就是 \(num_{0,i,a_i}\)。之后就线段树爱怎么写怎么写。时间复杂度 \(O(n\log_2n)\)。

Sol2:

神仙贪心，绝对写不出来的东西。

有点赶工期，这里直接 copy 了 \(\text{Alex\_Wei}\) 的题解。~~虽然洛谷题解不能复制 md 有点难蚌。~~

把所有登山者分成两类：一类是 \(a_i\le s_i\) 的记为集合 \(S\)，一类是 \(s_i<a_i\) 的记为集合 \(T\)。前者内部互不干扰，而后者可以按照 \(a_i\) 从小到大排序贪心。观察 \(S\) 对 \(T\) 的影响，对于 \(i\in S\)，\(j\in T\)，若 \(sj<ai\le si<aj\)，那么 \(i,j\) 之间只能选一个，显然选 \(i\) 更优因为 \(a_i<a_j\)，其他情况下可以证明 \(i,j\) 可以同时选择。

如果将所有 \((s_i,a_i)\) 按照 \(\max⁡(a_i,s_i)\) 为第一关键字，\(si\) 为第二关键字（主要考虑到 \(sj<ai\le si=aj\) 的情况，此时 \(j\) 应先被选）排序，那么对于上面的特殊情况，\(i\) 一定先于 \(j\) 被选。故排序后直接贪心就行，时间复杂度 \(O(n\log_2⁡n)\)。

Andrey's Tree CF1935F

给你一棵 \(n\) 个点的树，对于 \(\forall v\in[1,n]\)，你需要解决下面的问题：

先去掉节点 \(v\) 和与其相连的边；然后在剩余的图上加若干条边，在 \((x,y)\) 之间连边的代价是 \(|x-y|\)。求使得图连通的最小代价。

每次询问独立。对于每个询问，先输出最小代价和加的边数 \(k\)，然后再输出 \(k\) 行每行代表一条边。

\(1\le n\le 2\times 10^5\)。

最好的情况肯定是连接的全部是 \((x,x+1)\)，也就是说答案下界是 \(deg_u-1\)，我们考虑能不能取到它。

首先 \(u=1\) 或 \(u=n\) 肯定是取得到的。构造的话我们只要处理出 \(u\) 的每个子树中最大的节点编号是多少，记为 \(gv_v\)， \(\forall gv_v<n\) 连接 \((gv_v,gv_v+1)\) 即可。

若是 \(u\ne 1,u\ne n\)，那么 \(u\) 就会将 \([1,n]\) 分为 \([1,u-1]\) 和 \([u+1,n]\) 两个区间，若是这两个区间中没有连通的段，那么可以将这两个区间分别按照 \(1\) 或 \(n\) 来处理，再加上一个 \((u-1,u+1)\)，答案依旧为 \(deg_u\)。

若是左右区间的点是部分被连通的，令 \(sv_v\) 为连通块最小点，\(gv_v>u\) 的就连 \((gv_v,gv_v+1)\)，不是的话就连 \((sv_v,sv_v-1)\)。这样的话两个区间内部所确定连通块都是连通的，还需要连右区间最小的 \(sv_m\) 到 \(sv_m-1\) 的边，就可以确保连通，当然，如果 \(sv_m=1\) 就可以不用连了，已经被连上了。

答案就可以使用换根 dp 解决，时间复杂度 \(O(n)\)。

梅深不见冬 P5521

给定一棵 \(n\) 个点的树，点有正整数点权 \(w_i\) 。对于每个点 \(i\)，求出向其放 \(w_i\) 个梅花所需要准备的最小梅花数。

放梅花的规则如下：Alice 沿着这棵树的某一个欧拉序行进，只有当Alice 处于 \(u\)，且 \(u\) 的所有孩子 \(v\) 都放上了 \(w_v\) 个梅花后，才能在 \(u\) 上放梅花。不过 Alice 可以在任意时刻收回放在任意点上的梅花。

\(n \le 10^5\)。

按照本能想，我们肯定是想着先放子树所需樱花最多的儿子，因为儿子节点的樱花是不可以立马拿走的，但儿子的子树是可以全部拿走并用于后面的节点的，按这个方式一步一步放下去就可以知道当前节点的答案是多少了。

~~如果你想到这个策略，那么恭喜你，这题结束了。~~

这个策略确实是对的，但是还是要证明一下的。

令 \(ans_x\) 表示节点 \(x\) 的答案，\(w_x\) 表示 \(x\) 要放的樱花数，\(val_x\) 表示 \(x\) 子树要多少樱花。显然 \(val_x=ans_x-w_x\)。

令 \(val_x>val_y\)。

则先放 \(x\) 再放 \(y\) 需要

\[\max (ans_x,ans_y+w_x)=\max (val_x+w_x,val_y+w_y+w_x)=\max (val_x,val_y+w_y)+w_x \]

反之 \(x\) 要

\[\max(ans_y,ans_x+w_y)=\max(val_y+w_y,val_x+w_x+w_y)=\max(val_y,val_x+w_x)+w_y=val_x+w_x+w_y \]

若先放 \(x\) 取 \(val_x\)，则 \(val_x+w_x<val_x+w_x+w_y\)。

若先放 \(x\) 取 \(val_y+w_y\)，则 \(val_y+w_y+w_x<val_x+w_x+w_y\)。

则无论怎么取，先放 \(x\) 都更优。

得证。

时间复杂度 \(O(n\log_2n)\)。

惊蛰 P8467

给定非负整数序列 \(\{a_n\}\)，定义函数 \(f(x,y)\) 为

\[f(x,y)=\begin{cases} x-y,&x\ge y\\ C,&x< y \end{cases}, \]

其中 \(C\) 是给定常数。请构造一个不增非负整数序列 \(\{b_n\}\)，最小化

\[\sum_{i=1}^nf(b_i,a_i). \]

你仅需输出这一最小化的结果。

设 \(V\) 为序列 \(\{a_n\}\) 中元素以及常数 \(C\) 的值域。

\(1\le n\le10^6\)，\(V\subseteq[0,10^9]\)。

令 \(s\) 表示 \(\{a_n\}\) 中不同的元素的个数。我们可以很容易想到一个 \(O(ns)\) 复杂度的暴力 dp。

我们首先证明一个结论，那就是 \(\{b_n\}\) 中的元素一定都是 \(\{a_n\}\) 中出现过的。

结论比较显然，证明就粗糙一点。

因为如果不满足，我们把该位 \(b_i\) 变小，直到满足，那么答案一定变小。

令 \(g_{i,j}\) 表示 \(b\) 填到第 \(i\) 位取值为第 \(j\) 小数。

则 \(g_{i,j}=\min_{j\le k \le s} g_{i-1,k}+f(j,k)\)。

这个是 \(O(ns^2)\) 的加个后缀 \(\min\) 优化就是 \(O(ns)\) 的了。

接下来就是神仙线段树想法了。

滚过后缀 \(\min\) 后方程长这样：

设 \(a_i\) 为第 \(k\) 小的数，\(rev_i\) 表示第 \(i\) 小的数是多少。

\[g_{i,j}= \begin{cases} & g_{i-1,j}+C \text{ if } j<k \\ & g_{i-1,j}+rev_j-a_i \text{ if } j\ge k \end{cases} \]

\(C\) 和 \(-a_i\) 都可以直接线段树。我们只需要考虑一下怎么满足后缀 \(\min\) 操作。

我们考虑 \(g_{i,j}\) 肯定是一个不降序列，\(+C\) 不影响 \([1,k)\)，\(rev_j-a_i\) 也是一个不降序列加上去也不影响 \([k,s]\)，影响的只有两者的交界一部分。

大概长成这样。

上图中虚线就是要推平的部分，至于找到这个位置，只需在线段树上二分即可。

综上，你的线段树需要支持区间 \(\min\)，区间加，区间覆盖，区间标记加即加上 \(b\)，还有二分就可以以超大常数 \(O(n\log_2n)\) 写出此题。

可能会被卡常。

超级钢琴 P2048

给定一个长为 \(n\) 的序列 \(\{A\}\)，定义序列中左端点为 \(l\)，右端点为 \(r\) 的一段价值为 \(val_{l,r}=\sum^{r}_{i=l} A_i\)，请你选取 \(k\) 对满足 \(r_i-l_i+1\in[L,R]\) 的 \(l_i,r_i\)，并最大化 \(\sum^{k}_{i=1}val_{l_i,r_i}\)。

\(1\le n\le 5\times 10^5,1\le k\le5\times 10^5,-1000\le A_i\le1000,1\le L\le R\le n\)。

数据保证有解。

首先使用前缀和转化问题 \(val_{l,r}=sum_r-sum_{l-1}\)，可知我们只要确定了 \(l\) 并给定合法区间就能用线段树可以知道这个 \(l\) 对应的最大权值是多少。

先暴力一点的想，我们会将所有的合法 \((l,r)\) 对的权值放入一个堆里，在取 \(k\) 次堆顶，但因为 \((l,r)\) 对实在太多了，这个方法是不行的。

那我们就考虑怎么减少进入堆中的 \((l,r)\) 对，先前提到了确定 \(l\) 再给定一个区间就可以知道这个区间中哪个 \(val_{l,r}\) 最大，我们就可以考虑用区间配上一个确定的 \(l\)，来表示一个区间内最大的 \(val_{l,r}\) 是多少，而确定的 \(l\) 的个数最大是 \(n\)。

我们再考虑选过这个点后怎么办，我们令 \((L,l,r,x)\) 这样一个四元组来表示确定 \(L\) 和区间 \([l,r]\) 对应的最大值的点位在 \(x\)，那么显然的，要表示这个 \(L\) 剩下的 \((l,r)\) 对的最大权值，就可以表示为 \((L,l,x-1,x_l)\) 和 \((L,x+1,r,x_r)\)。当然如果新加入的区间是越界的，那么就不用放进堆里了。显然这样放是不重不漏的。

那么使用这种表示方法我们在堆里放置的四元组最多是 \(n+2k\) 的，达到了我们的要求。

时间复杂度 \(O((n+k)\log_2n)\)。

Shop CF521D

有 \(k\) 个正整数 \(a_{1\dots k}\)。
有 \(n\) 个操作，每个操作给定正整数 \(t, i, b\)，有三种可能：
如果 \(t = 1\)，这个操作是将 \(a_i\) 赋值为 \(b\)；
如果 \(t = 2\)，这个操作是将 \(a_i\) 加上 \(b\)；
如果 \(t = 3\)，这个操作是将 \(a_i\) 乘以 \(b\)。
你可以从 \(n\) 个操作中选择最多 \(m\) 个操作，并按你想要的顺序执行。
你的目标是最大化 \(\prod_{i=1}^k a_i\) 的值。
\(k,n \le 10^5\)。

显然赋值只会拿最大的 \(b\) 赋值，如果最大的还小于 \(a_i\) 就不赋值。

然后我们如果对于一个 \(a_i\) 所有操作都要用上，那么肯定是先赋值再加法最后乘法。

赋值是可以转化为加法的，而单个加法又可以转化为乘法，多个加法因为肯定是从大的开始取，所以可以将 \(a_i\) 加上其前面的再转化为乘法。

所以所有的有用操作都可以转化为乘法。

把他们都放到堆里面就是了。时间复杂度 \(O(n\log_2n)\)。

团队竞技 JOISC2022

给定 \(N\) 个三维点 \((X_i,Y_i,Z_i)\)，令一个三元组 \((i,j,k)\) 的权值为 \(X_i+Y_j+Z_k\)，请你在满足以下条件的情况下寻找权值最大的三元组，如果不存在满足以下条件的三元组，请输出 \(-1\)。

\(i\ne j\ne k\)
\(X_i>max(X_j,X_k)\)
\(Y_j>max(X_i,Y_k)\)
\(Z_k>max(Z_i,Z_j)\)
\(3\le N\le1.5\times 10^5,1\le X_i,Y_i,Z_i\le 10^8(1\le i\le N)\)。

我们把所有的 \(X_i,Y_i,Z_i\) 都分别丢进 \(qx,qy,qz\) 三个堆里，如果三个堆中取出的三元组 \((i,j,k)\) 中有存在相等的，那么这个就是不合法的，将 \(i,j,k\) 中相等的全都从对应堆中弹出，直到不存在相同编号，这时取出的 \((i,j,k)\) 的权值就是最大的。

存在一个堆弹完了就是无解。