定义一个函数 \(f\),输入一个数组 \(a\),输出一个数组 \(b\) 为 \(a\) 的子序列:\(b_1=a_1\),设 \(b_i\) 在 \(a\) 中的位置为 \(pos_i\),则 \(b_i\) 为 \(a_{pos_{i-1}+1}\sim a_n\) 中第一个严格大于 \(b_{i-1}\) 的数。\(n\le 5\times 10^5\),\(|p_i|\le 10^9,1\le a_i,b_i\le n, b_{i-1}<b_i\)。
给定长度 \(n\) 的数组 \(a\) 和数组 \(p\),以及长度 \(m\le n\) 的严格递增的数组 \(b\)。删除 \(a_i\) 需要 \(p_i\) 的代价,问删除一些数使 \(a\rightarrow a'\),\(f(a')=b\) 的最小代价是多少。
转化问题,变成保留一些数最大代价是多少。
注意到 \(f\) 的定义是严格递增,所以余下的数必然两两不同,显然用 map 可以 \(O(n\log n)\) 预处理出 \(a_i\) 在 \(b\) 中哪个位置出现过。
一个简单的思路是 \(f_i\) 表示考虑 \(a\) 的前 \(i\) 个数,必须保留 \(a_i\)(如果 \(a_i\not\in b\) 则 \(f_i=-\infty\)),能保留的数的最大价值之和。
设 \(a_i=b_j\)。
写出转移方程:$$f_i=\max_{0\le k\le i-1,a_k=b_{j-1}} (f_k+\sum_{t=k+1}^{i-1}[a_t\le a_k][p_t>0]p_t+p_i)$$
直接硬来是 \(O(n^3)\) 的,考虑优化。优化 DP 的一个重要思路是动态维护每个决策点的值。
令 \(g_k=f_k+\sum_{t=k+1}^{i-1}[a_t\le a_k][p_t>0]p_t+p_i\),尝试随着在 \(i\) 增大的过程中维护 \(g_k\)(\(k=0\sim i-1\))。但就算成功维护了 \(g\),算法仍然是 \(O(n^2)\) 的不能接受。还需要再套一层。
于是引入一个 \(G_v=\max_{0\le k<i,a_k=v}\{g_k\}\),则有 \(f_i=G_{b_j-1}+p_i\)。我们尝试动态维护 \(G_x\)(\(x=0\sim n\))。
因为 \(G\) 的变化是基于 \(g\) 的变化,我们先研究 \(g\) 是如何变化的。
在 \(i\rightarrow i+1\) 的时刻,可能有两种更新:一种是 \(g_{0\sim i-1}\) 的更新,一种是新增了 \(g_i\)。
对于旧 \(g_k\) 的改变,都增加了 \([a_i\le a_k][p_i>0]p_i\)。对于 \(p_i\le 0\) 的情况,直接略去,因为不会产生任何贡献;当 \(p_i>0\),每个 \(g_k\) 增加 \([a_k\ge a_i]\cdot p_i\)。
对于新增的 \(g_i\),容易发现 \(g_i=f_i\)。
那么 \(G_x\) 的变化是怎么样的呢?对于旧 \(g_k\) 的改变,容易发现对于 \(v\ge a_i\),\(G_v\) 增加 \(p_i\);对于新增的 \(g_i\),有 \(G_{a_i}=\max(G_{a_i},f_i)\)。
当我们询问 \(G\),只需要查询 \(G_{v}\) 一个位置的值即可。
所以 \(G\) 需要支持:后缀加法、单点取 \(\max\)、单点查询。
直接线段树当然可以,但是有些大材小用了。单点 \(\max\) 可以拆成一次查询和两次后缀加法。再把数组 reverse 一下,就变成前缀加法和单点查询,使用 BIT 可以完成。
标签:Function,le,单点,题解,查询,CF1334F,数组,max,sim From: https://www.cnblogs.com/FLY-lai/p/18416508