定义一个函数 \(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