奥法之劫（offa）题解

本人第一次出五校，出的就是这题。

奥法之劫 (offa)

题目信息

时间限制：$1800 \texttt{ ms}$。
空间限制：$512 \texttt{ MiB}$。
本题使用文件输入输出。
输入文件名：offa.in。
输出文件名：offa.out。

题目背景

你很清楚地知道一颗小小的鹅卵石也会引起山崩。同样地，一次单纯的背叛居然引发 了魔法瘟疫，而其后果还在托瑞尔上狂舞肆虐着，且远不止于此。
– 阴影谷之伊尔明斯特，于 1479 DR，永恒者之年

术士：终于到了么，因为奥法之疫而形成的幽暗深渊。

战士：还没能看见深渊的时候，我们就碰到了不少疫变生物，感觉这一路上凶多 吉少啊。

游侠：感想就之后再说吧，现在已经黄昏了，我们得赶紧找扎帐篷的地方了。

术士：确实。嗯……七点钟方向的峡谷中有不少的废弃要塞，我们可以过去看看。

题目描述

游侠：大致勘察了一下。这个峡谷是 U 形的，只有向西一个口子。而其中有 $n$ 座废弃要塞，从西向东第 $i$ 座要塞的编号为 $i$，高度是 $a_i$。

术士：啧。这就有点尴尬了，我的想法是，给出一个长度为 $m$ 的高度序列 $\{b_i\}$， 满足 $\forall 1\le i<m,b_i<b_{i+1}$，然后选择这样的 $m$ 座要塞满足：从西向东的编号分别为 $q_1,q_2,\cdots,q_m$，对于所有的 $1\le i\le m$， $a_{q_i}=b_i$，并且没有要塞向西的视线会被挡住， 即对于选出的每一座要塞，向西方向的其他要塞的高度都会严格小于这座要塞的高度。这样子高度非常合适。如果疫变生物来袭，可以有更佳的作战环境。但因为从远处看看不真切，忽略了除这 $m$ 座要塞之外的会挡住视线的情况。

战士：或许我们可以把其他的 $n-m$ 座要塞拆掉，这样既可以搜刮这些要塞中的资源，又可以解决视线问题。这件事有术士你的身体强化法术应该并不是难事。

游侠：我觉得这不太现实，就算有身体强化，凭我们仨，也要拆到深夜，这样耽误了休息时间，还有可能在拆除的时候被疫变生物攻击。

术士：我倒觉得这不失为一个办法，但是我们可以更聪明一些。我们只需要拆掉一部分要塞，使得最后从其中可以选出 $m$ 座要塞，从西向东的第 $i$ 座要塞的高度要和 $b_i$ 相同，并且选出的要塞都不会被挡住向西的视线。这样便可以解决问题了，也不需要花费太多时间。

战士：我觉得上面的条件可以再加上一个条件：除了选出的 $m$ 座要塞，其他未被拆除的要塞向西的视线都要被挡住，不能给敌人留下任何有视线开阔的要塞。

游侠：我也说一下我的想法吧。根据我勘察的结果，拆除第 $i$ 座要塞的代价是 $p_i$， 我们要尽量让拆除代价总和最小。

术士：那我来做一个最后总结吧，现在我们要解决的问题描述如下：

有 $n$ 座废弃要塞，从西向东第 $i$ 座要塞的高度为 $a_i$，拆除这座要塞的代价为 $p_i$。 现在我们给定一个长度为 $m$ 的高度序列 $\{b_i\}$，满足
$\forall 1\le i<m,b_i<b_{i+1}$。然后我们想要拆掉一部分要塞，使得最后从其中可以选出 $m$ 座要塞，从西向东的编号分别是 $q_1,q_2,\cdots,q_m$，满足：

1. 对于任意的 $1\le i\le m$，$a_{q_i}=b_i$；
2. 选出的要塞向西的视线都不会被挡住；
3. 除了选出的 $m$ 座要塞，其他未被拆除的要塞向西的视线都会被挡住。 最后要最小化拆除代价总和。

战士：嗯。就是这样了。

游侠：那么我们马上开工吧。

输入格式

从文件 offa.in 中读入数据。

输入的第一行包含两个正整数 $n,m$，表示荒野中废弃要塞的数量，以及术士想要保留的废弃要塞的数量。

接下来一行，包含 $n$ 个整数，第 $i$ 个整数为 $a_i$，表示从西向东第 $i$ 座废弃要塞的高度。

再接下来一行，包含 $n$ 个整数，第 $i$ 个整数为 $p_i$，表示从西向东第 $i$ 座拆除废弃要塞的代价。

再接下来一行，包含 $m$ 个整数，第 $i$ 个整数为 $b_i$，表示术士想要保留的从西向东第 $i$ 座废弃要塞的高度。

输出格式

输出到文件 offa.out 中。

若可以找到一种拆除方案满足术士的计划，则输出一行最小的拆除代价总和； 否则输出 Impossible。

样例

样例输入 1

11
1 3 1 2 6 8 7 7 4 11 10
0 9 11 -7 6 -5 0 3 -2 10 1
3
1 3 6 

样例输出 1

0

样例解释 1

我们拆除第 $4,6,7,8,9,10,11$ 座要塞，选取第 $1,2,5$ 座要塞，这样拆除总代价为 $−7 − 5 + 0 + 3 − 2 + 10 + 1 = 0$，可以证明这是最小的拆除代价总和。

样例输入 2

6
1 6 2 2 3 5
-1 0 9 8 7 2
2
1 4 

样例输出 2

Impossible

样例解释 2

在原来的要塞中，不存在高度为 $4$ 的要塞，所以不管怎么拆要塞都不能满足术士的要求。

样例 3

见选手目录下的 offa/offa3.in 与 offa/offa3.ans。

本样例满足 Subtask #2 的限制。

样例 4

见选手目录下的 offa/offa4.in 与 offa/offa4.ans。

本样例满足 Subtask #3 的限制。

样例 5

见选手目录下的 offa/offa5.in 与 offa/offa5.ans。

本样例满足 Subtask #4 的限制。

样例 6

见选手目录下的 offa/offa6.in 与 offa/offa6.ans。

数据范围与提示

对于所有的数据，$1\le m\le n\le 5\times 10^6$，$1\le a_i,b_i\le n$，$|p_i|\le 10^9$，且保证 $\forall 1\le i<m,b_i<b_{i+1}$。

Subtask #1 (13 points)：$n\le 20$。
Subtask #2 (27 points)：$n\le 1000$。
Subtask #3 (10 points)：$m=1$。
Subtask #4 (10 points)：$\{a_i\}$ 为 $1\sim n$ 的排列。
Subtask #5 (20 points)：$n\le 500000$。
Subtask #6 (20 points)：无特殊性质。

提示：本题输入输出规模较大，请注意选择较为高效的输入方式（下发文件中的 offa/fast_input.cpp 可以拷贝使用）。

题解

原题链接

CF1334F Strange Function

数据范围有加强，加强思路来自题解下面的讨论区。

简要题意

定义两个序列之间的函数 $f$：给出一个长度为 $l$ 的序列 $\{x_i\}$，$f(\{x_i\})$ 为所有满足 $1\le i\le l,x_i>x_{i-1},x_i>x_{i-2},\cdots,x_i>x_1$ 的 $x_i$ 按照原序列次序组成的新序列。

给定一个长度为 $n$ 的序列 $\{a_i\}$ 和一个长度为 $m$ 的序列 $\{b_i\}$，在序列 $\{a_i\}$ 中删除第 $i$ 个数的代价为 $p_i$，求最小的删除代价，使得 $f(\{a_i\})=\{b_i\}$，或者给出无解。

算法一

若 $\{b_i\}$ 不是 $\{a_i\}$ 的子序列则无解。否则枚举每个数删或者不删，最后判断取最小代价。

时间复杂度为 $O(2^nm)$，空间复杂度为 $O(n)$，期望得分 $13$ 分。

算法二

考虑 $m=1$ 的情况，现在我们已经知道了要留下哪一个值。我们求出所有 $a_x=b_1$ 的 $x$，我们考虑如果 $f\left(\{a'_i\}\right)$ 留下的位置只有 $x$ 的话序列 $\{a'_i\}$ 要满足什么条件。很显然的，要满足 $a'_1=b_1$，且 $a'_1$ 要为全局最大值。

那么我们枚举 $x$，它的答案就是：

$\sum\limits_{i=1}^{x-1} {p_i}+\sum\limits_{i=x+1}^n{[a_i>b_1\vee p_i<0]p_i}$

两个和式可以分别用前、后缀和来维护，于是我们可以做到 $O(1)$ 计算当前位置的答案

时空复杂度均为 $O(n)$，综合前面算法，期望总得分 $23$ 分。

算法三

考虑 $\{a_i \}$ 是一个排列的情况，现在我们已经知道了要留下那些位置。设 $a_x=b_i,a_y=b_{i+1}$，我们考虑 𝑥 与 𝑦 之间要删那些数。很显然，与算法二一样，$a_j>b_i$ 或 者 $p_j<0$ 的位置要删。那么我们直接模拟一遍就好了，还要注意 $b_1$ 之前和 $b_m$ 之后 的该删的也要删掉。

时空复杂度均为 $O(n)$，综合前面算法，期望总得分 $33$ 分。

算法四

考虑一个 $DP$，设 $f_{i,j}$ 表示我们考虑到了 $\{a_i\}$ 的第 $i$ 位，$\{b_j\}$ 第 $j$ 位的最小代价总和。

转移方程分 $a_I<b_j,a_i>b_j,a_i=b_j$ 三种情况：

若 $a_i<b_j$，第 $i$ 项元素可以删除也可以不删除，因为该元素不会加入新数组，对结果不产生影响，可以得到

$f_{i,j}=f_{i-1,j}+\min(0,p_i)$

若 $a_i>b_j$，则 $a_i$ 必须删除，因此

$f_{i,j}=f_{i-1,j}+p_i$

若 $a_i=b_j$，可以由 $f_{i-1,j-1}$ 不删除得到，也可以由 $f_{i-1,j}$ 进行删除或不删除得到， 有三种可能，即

$f_{i,j}=\min(f_{i-1,j-1},f_{i-1,j},f_{i-1,j}+p_i)$

时空复杂度均为 $O(nm)$，综合前面算法，期望得分 $60$ 分。

算法五

我们发现算法四中的第二维其实可以去掉，因为我们可以马上知道 $DP$ 到 $\{a_i\}$ 中的第 $i$ 位时 $j$ 在哪里：我们设 $f_i$ 表示考虑到了 $\{a_i\}$ 的第 $i$ 位的最小代价总和。为了减少边界条件的判断，我们在 $\{a_i\}$ 和 $\{b_i\}$ 后面再加一个哨兵点，权值为 $n$，删除代价为 $0$。 接着，我们按照 $a_i$ 从小到大 $DP$：

若 $a_i\notin \{b_j\}$，则忽略；

若 $a_i\in \{b_j\}$，则同算法二一样的：

$f_i=\min_{x=1}^{i-1}\left(f_x+\sum\limits_{k=x+1}^{i-1}{[a_k>b_{j-1}\vee p_k<0]p_k} \right)[a_x=b_{j-1}]$

其中上面的和式中的东西可以拆成 $a_k>b_{j-1},p_k\ge 0$ 与 $p_k<0$ 两部分。后一部分可以同算法二一样用前缀和维护；而前一部分可以用树状数组维护。

时间复杂度为 $O(n^2\log{n})$，空间复杂度为 $O(n)$，综合前面算法，期望得分 $60$ 分。

算法六

我们发现算法四中的 $a_i<b_j$ 与 $a_i>b_j$ 两种情况的 $j$ 必然是两个连续的区间，且都由 $f_{i-1,j}$ 转移过来，并且二者所加的 $0$ 以及 $\min(0, p_i)$ 也都是常数，可以用区间加进行维护；而 $a_i=b_j$ 的情况也只有一个点，单点修改即可。这些操作都可以用线段树或者树状数组来实现。

时间复杂度为 $O(n\log{m})$，空间复杂度为 $O(m)$，期望得分 $80$ 分。

算法七

我们发现算法五中 $a_i\in \{b_j\}$ 的转移其实不需要枚举 $x$，这个转移方程可以用广义的前缀最小值优化。什么意思呢？因为 $f_i$ 只会从满足 $a_x=b_{j-1}$ 的 $f_x$ 转移而来， 然后我们再改写一下状态转移方程：

$f_i=\min_{x=1}^{i-1}\left(f_x+\sum\limits_{k=x+1}^{i-1}{[a_k>b_{j-1}\land p_k\ge 0]p_k}+\sum\limits_{k=x+1}^{i-1}{[p_k<0]p_k} \right)[a_x=b_{j-1}]$

我们记 $s1_x=\sum_{k=1}^x{[a_k>b_{j-1}\land p_k\ge 0]p_k},s2_x=\sum_{k=1}^x{[p_k<0]p_k}$，那么又有：

$f_i=\min_{x=1}^{i-1}(f_x+s1_{i-1}-s1_x+s2_{i-1}-s2_x)$

我们再记一个数组 $g_y$，并且假设当前我们要求的是 $f_k$，那么：

$g_y=\min_{x=1}^{k-1}(f_x-s1_x-s2_x)[a_x=y]$

这就是之前说的广义前缀最小值，意即所有满足 $a_x=y$ 的 $x$ 组成的子序列的前缀最小值。

又有了新的方程：

$f_i=g_{b_{j-1}}+s1_{i-1}+s2_{i-1}$

我们只需要在求出 $f_i$ 后将 $g_{a_i}$ 更新一下就可以做到每个点 $O(1)$ 转移了。

其中 $s1_x$ 还是需要树状数组来求，所以时间复杂度为 $O(n\log{n})$，空间复杂度为 $O(n)$，综合前面算法期望得分 $80$ 分。

算法八

发现复杂度的瓶颈在于求 $s1_x$，我们考虑重构状态转移方程。

考虑贡献后移。我们称区间 $(b_{j-1},b_j]$ 为“区间 $j$ ”。在计算 $f_i$ 时，我们可以只考虑满足 $a_k$ 在“区间 $j$ ”中的 $k$ 的贡献，这是为什么呢？因为虽然从当前来看，并没把该删的都删了，比如说 $a_k>b_j$ 的就没有删掉；但是从整体上来看，最后该删掉的就是 $a_k$ 在“区间 $1$ ”、“区间 $2$ ”、$\cdots$、“区间 $m + 1$ ”的 $k$，而计算完 $f_n$ 时，我们已经将“区间 $1\sim m+1$ ”的都算完了，所以这样 $DP$ 是不影响最后答案的。

我们预处理出每一个位置 $k$ 它的 $a_k$ 所在的“区间 $q_k$ ”，实时维护 $h_l$ 表示这时“区间 $l$ ”要删掉的元素的代价总和，并且将 $g_y$ 改为只需要记录 $f_x-s2_x$ 的广义前缀最小值。那么就有新的方程：

$f_i=g_{b_{j-1}}+s2_{i-1}+h_j$

直观来看求 $q_k$ 是需要 $\texttt{lower\_bound}$ 的，但是因为 $\{b_i\}$ 单增，所以双指针就好了。

时空复杂度均为 $O(n)$，期望得分 $100$ 分。

标程

#include <bits/stdc++.h>
#define il inline
#define ll long long
const int N=5e6+5;

int n,m,a[N],b[N],id[N],q[N]; ll f[N],g[N],h[N],p[N];

il char gc()
{
    static char buf[1<<20],*ss,*tt;
    if (tt==ss)
    {
        tt=(ss=buf)+fread(buf,1,1<<20,stdin);
        if (tt==ss) return EOF;
    }
    return *ss++;
}

il int read()
{
    int res,sign=1; char c;
    while ((c=gc())<'0'||c>'9') if (c=='-') sign=-1; res=c^48;
    while ((c=gc())>='0'&&c<='9') res=(res<<3)+(res<<1)+(c^48);
    return res*sign;
}

int main()
{
    freopen("offa.in","r",stdin),freopen("offa.out","w",stdout);
	
    n=read(); int i,j; ll F,x=0;
    for (i=1; i<=n; i++) a[i]=read();
    for (i=1; i<=n; i++) p[i]=read();
    m=read(),n++,a[n]=n;
    for (i=1; i<=m; i++) id[b[i]=read()]=i;
    m++,b[m]=n,id[n]=m,memset(g,63,8*m+8),F=g[0],g[0]=0;
    for (i=j=1; i<=n; q[i++]=j) if (b[j]<i) j++;
	
    for (i=1; i<=n; i++)
    {
        j=id[a[i]];
        if (j) f[i]=g[j-1]<F?g[j-1]+h[j]+x:F;
        if (p[i]>-1) h[q[a[i]]]+=p[i];
        else x+=p[i];
        if (j) (f[i]<F)&&(g[j]=std::min(g[j],f[i]-x));
    }
    if (f[n]<F) printf("%lld",f[n]);
    else puts("Impossible");
	
    return 0;
}