前置知识

ST 表

题意简述

给定一个长度为 $n$ 的序列 $v$。初始时，$\forall i\in\{1,2,\dots,n\},v_i=1$。可执行以下操作：

选定一个 $i\in\{1,2,\dots,n\}$。然后：

• 以 $a_i$ 的代价，$\forall j\in \{1,2,\dots,i\}$，令 $v_j\leftarrow0$。

• 以 $b_i$ 的代价，令 $v_i\leftarrow0$。

• 以 $c_i$ 的代价，令 $v_i\leftarrow1$。

有 $q$ 次询问，每次询问给定集合 $P$，求使得序列 $v$ 满足

$$\forall i\in\{1,2,\dots,n\},v_i=\begin{cases} 0,i\not\in P\\ 1,i\in P \end{cases}$$

的 最小总代价。

每次询问相互独立。

数据范围

$1 \leqslant n,\sum m \leqslant 5\times 10^5$，$0\leqslant m \leqslant n$，$1\leqslant q\leqslant \max(n,\sum m)$，$0 \leqslant a_i, b_i, c_i \leqslant 10^9$，$1\leqslant p_i \leqslant n$。

测试点编号	$n \leqslant$	$m$	$\sum m$	$c_i$
$1 \sim 2$	$5 \times 10^5$	$=0$		$\leqslant10^9$
$3 \sim 4$	$7$	$\leqslant7$	$\leqslant15$
$5 \sim 6$	$2000$	$\leqslant1$	$\leqslant2000$
$7$		$\leqslant2000$		$=0$
$8 \sim 11$			$\leqslant2 000$	$\leqslant10^9$
$12 \sim 13$	$5 \times 10^4$	$\leqslant5 \times 10^4$	$\leqslant5 \times 10^4$
$14 \sim 15$	$5 \times 10^5$	$\leqslant1$	$\leqslant5 \times 10^5$
$16$		$\leqslant5 \times 10^5$		$=0$
$17 \sim 20$				$\leqslant10^9$

解题思路

测试点 $1\sim2$

做法

这里令 $a_0=0$，则答案为

$$\displaystyle\min_{i=0}^n\{a_i+\displaystyle\sum_{j=i+1}^nb_i\} $$

正确性证明

$m=0\implies P=\varnothing\implies\forall i\in\{1,2,\dots,n\},i\not\in P\implies$ 在最终的序列 $v$ 中，$\forall i\in\{1,2,\dots,n\},v_i=0$。

因此，我们不可能将 $v_i$ 赋值为 $1$，只可能以 $a_i$ 或 $b_i$ 代价将序列赋值为 $0$。

设我们 用 $b_i$ 的代价单独 赋值为 $0$ 的所有 下标 构成的集合为 $A$。设 $A$ 中最小的元素为 $d$，若 $\exists i\in\{d+1,d+2,\dots,n\},i\not\in A$，则我们必然需要花费 $a_i$ 的代价，将 $v_i\leftarrow0$。此时，我们同时也使得 $\forall i\in\{1,2,\dots,i\},v_i=0$，若不花费 $b_d$ 的代价，也能达成这一效果，因此 至少 $b_d$ 的花费是不必要的，即该条件下的方案 一定不优。

因此得证：若对元素 单独 赋值为 $0$，则必然有 $\forall i\in\{d,d+1,d+2,\dots,n\},i\in A$，其中 $d$ 和 $A$ 的含义同上。也就是说，在最优方案中，单独赋值为 $0$ 的下标必然构成序列下标的一段后缀。

此时还需要对 $v_1,v_2,\dots,v_i$ 全体元素 赋值为 $0$。若 $i\not=d-1$，则必然需要花费 $a_{d-1}$ 的代价将 $d-1$ 之前的元素赋值为 $0$，此时 $a_i$ 的花费是不必要的，即该条件下的方案 一定不优。

因此得证：只有花费 $a_{d-1}$ 的代价将 $v_1,v_2,\dots,v_{d-1}$ 全体赋值为 $0$，才可能成为最优方案。

综上所述，将所有可能成为最优方案的方案再取最优，即为问题的答案：

$$\displaystyle\min_{i=0}^n\{a_i+\displaystyle\sum_{j=i+1}^nb_i\} $$

因而思路正确。

具体实现

预处理 $b_i$ 的 后缀和。分别枚举使用 $a_i$ 代价与使用 $b_i$ 代价的分界点，计算对应总代价，不断更新答案。

最终对于每个询问，输出这个答案。

时间复杂度分析

处理后缀和，复杂度 $O(n)$。枚举分界点时，由于此时后缀和可 $O(1)$ 求，因此总复杂度也为 $O(n)$。

对于所有的询问输出答案，复杂度 $O(q)$。

总时间复杂度 $O(n+q)$，可以通过 测试点 $1\sim2$。

参考核心代码

for(i=n;i>=1;i--)
    sumb[i]=sumb[i+1]+1ll*b[i];//计算b数组的后缀和
long long ans=INF;
for(i=0;i<=n;i++)
    ans=min(ans,a[i]+sumb[i+1]);//计算每个总代价，更新答案
int q=R();
while(q--){
    int m=R();
    printf("%lld\n",ans);//对于每个询问，输出答案
}

期望得分

$10$ 分。

测试点 $3\sim4$

做法

令初始的所有 $v_i=1$。

对于每一个位置 $i$，分别枚举 以下情况：

• 使用 $a_i$ 的代价，将 $v_1,v_2,\dots,v_i$ 全部赋值为 $0$，并将 $v_1,v_2,\dots,v_i$ 中应当在最终序列中为 $1$ 的所有元素 $v_j$，使用对应的 $c_j$ 代价将其赋值为 $1$。

• 使用 $b_i$ 的代价，将 $v_i\leftarrow0$。

• 使用 $c_i$ 的代价，将 $v_i\leftarrow1$。

• 不做任何操作。

并继续向下 搜索，直到所有位置的操作都确定完。当所有位置操作做完后，判断当前序列是否与应当的最终序列相同。若不相同，则不合题意；若相同，则更新答案。

这样即可得到最终的答案。

正确性证明

考虑序列的第 $i$ 个位置。

若使用上述第一种操作中，用 $a_i$ 代价将 $v_1,v_2,\dots,v_i$ 全部赋值为 $0$，则只有使用上述的 $\sum c_j$ 代价将前面应当赋值为 $1$ 的元素全部赋值为 $1$，才能保证当前序列是符合题意的序列。若其中含有其他操作，由于可以只使用 $\sum c_j$ 代价进行赋值为 $1$ 的操作，因此这些 其他操作一定是不必要的。

故：使用 $a_i$ 代价将 $v_1,v_2,\dots,v_i$ 全部赋值为 $0$ 和使用 $\sum c_j$ 代价将应当赋值为 $1$ 的元素全部赋值为 $1$，这两个操作是 捆绑的。

对于该位置，也可以做上述的第二、三、四种操作。除此之外，再无别的操作。

因此，我们考虑到了 所有可能符合题意的操作，并从中筛选出了 所有真正符合题意的操作，并取最小答案。所以，这一思路是正确的。

具体实现

使用 深度优先搜索（DFS）实现。

对于每个询问，记 $DFS(now,cost)$ 表示搜索到了 $now$ 位置，当前的所有操作代价总和为 $cost$。则枚举该位置的四种情况：

记 $\Delta$ 表示该位置的一种操作产生的 $cost$ 增加量。

• 第一种情况：$\Delta=a_{now}+\displaystyle\sum_{i=1}^{now}[i\in P]c_i$。

• 第二种情况：$\Delta=b_{now}$。

• 第三种情况：$\Delta=c_{now}$。

• 第四种情况：$\Delta=0$。

继续向下执行 $DFS(now+1,cost+\Delta)$ 即可。注意在枚举对应情况时，需要对序列对应元素 及时赋值。为了便于 回溯，可以在函数内部再开一个数组，记录 赋值前序列的前 $now$ 个元素。

当 $now=n+1$ 时，首先判断当前序列是否与应当得到的最终序列相同。若不同，直接返回；否则，更新答案。

最后输出答案。

时空复杂度分析

时间复杂度：由于对每个位置需要枚举 $4$ 种情况，每次枚举的复杂度为 $O(n)$，因此对每个询问，总复杂度为 $O(n4^n)$。

总时间复杂度 $O(4^nqn)$，可以通过 测试点 $3\sim4$。

空间复杂度：在 DFS 中，递归的最大层数为 $O(n)$ 级别，且每层需要新开一个大小为 $O(n)$ 的临时数组。

空间复杂度为 $O(n^2)$，可以通过 测试点 $3\sim4$。

参考核心代码

void DFS(int now,long long cost){
    if(now==n+1){//如果已经确定所有位置的操作
        for(int i=1;i<=n;i++)
            if(tmp[i]!=fnl[i])//判断当前序列是否符合题意，若不符合直接返回
                return;
        ans=min(ans,cost);//否则更新答案
        return;
    }
    long long delta=a[now];//cost增加量
    vector<int>tmp1(now+1);
    for(int i=1;i<=now;i++)
        tmp1[i]=tmp[i];//临时数组，记录赋值前序列
    for(int i=1;i<=now;i++)
        tmp[i]=0;
    for(int i=1;i<=m;i++){
        if(p[i]>now)
            break;
        delta+=c[p[i]];
        tmp[p[i]]=1;//第一种情况
    }
    DFS(now+1,cost+delta);//向下继续搜索
    for(int i=1;i<=now;i++)
        tmp[i]=tmp1[i];//回溯
    tmp[now]=0;
    delta=b[now];
    DFS(now+1,cost+delta);//第二种情况
    tmp[now]=tmp1[now];//回溯
    tmp[now]=1;
    delta=c[now];
    DFS(now+1,cost+delta);//第三种情况
    tmp[now]=tmp1[now];//回溯
    DFS(now+1,cost);//第四种情况
}
...
        fill(tmp+1,tmp+1+n,1);//初始v[i]=1
        fill(fnl+1,fnl+1+n,0);
        for(i=1;i<=m;i++)
            fnl[p[i]]=1;//设定最终序列
        ans=INF;
        DFS(1,0);
        printf("%lld\n",ans);//输出答案

期望得分

$10$ 分。结合 测试点 $1\sim2$ 的算法可以获得 $20$ 分。

测试点 $5\sim6$

做法

令 $a_0=0$。当 $m=1$ 时，对于每个询问，其答案为

$$\min(\displaystyle\min_{i=0}^{p_1-1}\{a_i+\displaystyle\sum_{j=i+1}^{p_1-1}b_j+\displaystyle\sum_{j=p_1+1}^nb_j\},\displaystyle\min_{i=p_1}^n\{a_i+\displaystyle\sum_{j=i+1}^nb_j+c_{p_1}\}) $$

$m=0$ 时的答案与 测试点 $1\sim2$ 中相同。

正确性证明

对于所有的询问，$m=1\implies$ 最终序列中只有一个位置 $p_1$ 满足 $v_{p_1}=1$，其他位置 $i$ 都有 $v_i=0$。

考虑对序列除 $p_1$ 位置外的所有位置赋 $0$ 的方式。由 测试点 $1\sim2$ 的证明，对于最终为全 $0$ 的序列，最优方案使用 $a_i$ 的代价 最多一次。并且，使用 $b_i$ 代价赋值的所有下标必然构成 一段后缀。

现尝试将该结论迁移到 $m=1$ 的情况。若在 $p_1$ 下标前的 $i$ 使用了一次 $a_i$ 代价，则在 $i$ 后面的位置 $j$，再使用一次 $a_j$，也 一定是不优的，证法类似。若使用 $b_i$ 的下标 $i$ 中，存在位置 $j$ 满足最终 $v_j=0$ 且未使用 $b_j$，则必然使用 $a_j$，则该情况回到了 测试点 $1\sim2$，必然不优，所有其他位置 $j$ 必然使用一次 $b_j$。

因此，测试点 $1\sim2$ 的结论在此处 仍然基本成立。

考虑在 $p_1$ 下标及其后面下标 $i$ 处使用 $a_i$ 的情况。此时根据上述推理，必然在 $i+1,i+2,\dots,n$ 处使用 $b_i$。由于最终需要使得 $v_{p_1}=1$，因此还需要 使用一次 $c_{p_1}$，才能符合题意，不需要再使用其他操作。

因此上述答案得证。

具体实现

对于 $m=1$：

预处理 $b$ 数组的前缀和 $sumb$，则 $\displaystyle\sum_{i=l}^rb_i=sumb_r-sumb_{l-1}$。

处理每次询问时，扫一遍序列，按照上述计算式计算即可。

也可以使用 $sumb_n-sumb_i-b_{p_1}$ 代替 $\displaystyle\sum_{j=i+1}^{p_1-1}b_j+\displaystyle\sum_{j=p_1+1}^nb_j$。

扫完整个序列之后输出答案即可。

时间复杂度分析

处理前缀和，复杂度 $O(n)$。每次回答询问时，需要扫一遍序列，单次回答复杂度 $O(n)$。

总时间复杂度 $O(qn)$，可以通过 测试点 $5\sim6$。

参考核心代码

以下代码略去了 $m=0$ 的情况。

...//预处理b数组前缀和
    for(i=0;i<p[1];i++)//计算前半部分答案
        ans=min(ans,a[i]+sumb[n]-sumb[i]-b[p[1]]);
    for(i=p[1];i<=n;i++)//计算后半部分答案
        ans=min(ans,a[i]+sumb[n]-sumb[i]+c[p[1]]);
    printf("%lld\n",ans);//输出答案

期望得分

$10$ 分。结合 测试点 $1\sim2$ 的算法可以获得 $20$ 分，结合 测试点 $3\sim4$ 的算法可以获得 $20$ 分，结合 测试点 $1\sim4$ 的算法可以获得 $30$ 分。$(1)$

测试点 $7$

做法

令 $a_0=0$。则对于每个询问，其答案为

$$\displaystyle\min_{i=0}^n\{a_i+\displaystyle\sum_{j=i+1}^n[j\not\in P]b_j\} $$

正确性证明

根据 测试点 $3\sim4$ 的推理，我们知道，将 $v_1,v_2,\dots,v_i$ 全部赋值为 $0$ 的操作，往往和将所有 $j\in P,j\in\{1,2,\dots,i\}$ 的 $v_j\leftarrow1$ 的操作是 捆绑的。

并且由于 $c_i=0$，因此我们 可以无视 赋值为 $1$ 的代价，只需要考虑 $a_i$ 和 $b_i$ 即可。

根据 测试点 $1\sim2$ 的推理，若分别使用一次 $a_i,a_j$，这样的 总代价一定是更大的。因此，$a_i$ 最多只可能使用一次。确定 $a_i$ 使用位置后，只需要在其后面使用 $b_i$ 将对应位置 $v_i\leftarrow0$。同时，由于 $m\geqslant1$，为尽可能 最小化总代价，只对最终序列中所有 $v_i=0$ 的位置 $i$ 使用 $b_i$ 的代价即可。这些位置的代价是 必须使用，不可替代 的，若在其他位置使用其他代价，则都是不必要的。

我们证明了在这些答案中一定能够取到所有合法总代价的 下界，因此该思路是正确的。

具体实现

对于每一次询问，处理一个 后缀和 数组：$sum_i=\displaystyle\sum_{j=i}^n[i\not\in P]b_i$。

然后，扫一遍序列，按照上式计算即可。

最后输出答案。

时间复杂度分析

对于每次询问，需要处理后缀和数组，复杂度 $O(n)$；扫一遍序列并计算，复杂度 $O(n)$。

总时间复杂度 $O(qn)$。根据该解法，可以通过 测试点 $1\sim2,7$。

参考核心代码

    for(i=1;i<=m;i++)
        fnl[p[i]]=1;//设定最终序列
    for(i=n;i>=1;i--)
        sumb1[i]=sumb1[i+1]+b[i]*(!fnl[i]);//求b的上述后缀和
    for(i=0;i<=n;i++)
        ans=min(ans,a[i]+sumb1[i+1]);//根据上式计算答案
    printf("%lld\n",ans);//输出答案

期望得分

$15$ 分。结合 测试点 $3\sim4$ 的算法可以获得 $25$ 分，结合 测试点 $5\sim6$ 的算法可以获得 $25$ 分，结合测试点 $3\sim6$ 的算法可以获得 $35$ 分。$(2)$

测试点 $8\sim11$

做法

对于每个询问，设 $dp_i$ 表示考虑将序列 $[1,p_i]$ 变为合法序列的 最小总代价。则

$$dp_i=\min(\displaystyle\min_{j=p_{i-1}+2}^{p_i}\{a_j+\displaystyle\sum_{k=1}^{p_{i-1}}[k\in P]c_k+\displaystyle\sum_{k=j}^{p_i-1}b_k\},dp_{i-1}+\displaystyle\sum_{k=p_{i-1}+1}^{p_i-1}b_k,a_{p_i}+\displaystyle\sum_{k=1}^{p_i}[k\in P]c_k) $$

对于每个询问，令 $p_{m+1}=n+1$，且计算 $dp_{m+1}$ 时的上述式子 不包含第三项，则答案为 $dp_{m+1}$。

正确性证明

根据前面几个测试点的推理，我们注意到，将一段 区间全部赋值为 $0$ 已成为 重要的子问题。由于 $\forall i\in\{1,2,\dots,m-1\},p_i\lt p_{i+1}$，因此我们在考虑到 $p_i$ 时，$\forall j\in\{p_{i-1}+1,p_{i-1}+2,\dots,p_i-1\}$，都需要使得最终序列的 $v_j=0$，且 $p_{i-1}$ 及前面的最小代价已知。

现考虑所有可能将该区间全部赋值为 $0$ 的方案：

• 对于一个 $j\in\{p_{i-1}+1,p_{i-1}+2,\dots,p_i-1\}$，使用 $a_j$ 的代价，将 $v_1,v_2,\dots,v_j$ 全部赋值为 $0$。此后需要立即执行 $\forall k\in\{1,2,\dots,j\},k\in P,v_k\leftarrow1$ 的操作（具体原因见 测试点 $3\sim4$），并将位置 $j$ 到 $p_i-1$ 这段后缀中每个位置 $k$，全部用 $b_k$ 的代价赋值为 $0$。$a_j$ 不可能在不同位置使用多次，原因见 测试点 $1\sim2,5\sim6$ 等，这里不再赘述。

• 对于该区间的所有位置 $i$，使用 $b_i$ 代价，将 $v_i\leftarrow0$。由于该操作 基于 $p_{i-1}$ 及前面已经操作好的序列，因此需要将该代价与 $dp_{i-1}$ 累加。

• 在 $p_i$ 位置使用 $a_{p_i}$ 代价，将 $v_1,v_2,\dots,v_{p_i}$ 全部赋值为 $0$，再 $\forall k\in\{1,2,\dots,p_i\},k\in P,v_k\leftarrow1$。该操作其实与第一个操作类似，但赋值为 $1$ 的元素多了一个 $v_{p_i}$。

若 $b_i$ 代价使用的下标不构成 $\{1,2,\dots,p_i-1\}$ 的一段后缀，则该方案 一定不优，具体已在 测试点 $1\sim2,5\sim6$ 中证明。

由于已知最终序列中 $v_{p_i}=1$，因此若使用 $b_{p_i}$ 代价，单独将 $v_{p_i}\leftarrow0$，则该操作必然是 多余的。

综上，我们已经考虑到了此时所有可能的最优情况。

对于 $dp_{m+1}$，由于实际上不存在 $n+1$ 位置的元素，因此只能将 $v_{p_m},v_{p_m+1},\dots,v_n$ 全部赋值为 $0$，故其计算式中只有前两项。

因此，我们考虑完了 整个序列 的所有可能最优情况，故该思路是正确的。

具体实现

预处理 $b$ 的前缀和 $sumb$。

对于每次询问，在枚举每个 $p_i$ 时，先扫 $p_{i-1}+2$ 到 $p_i$，计算前两项更新 $dp$ 值，再 动态更新 $\displaystyle\sum_{j=1}^{p_i}[j\in P]c_j$。具体地，在每次计算完式中前两项后，直接将 $c_{p_i}$ 加入该询问的 $sumc$。然后，计算第三项，更新 $dp$ 值。

扫完每个 $p_i$ 后，输出 $dp_{m+1}$。注意 $dp_{m+1}$ 的计算中 没有第三项。

时间复杂度分析

预处理 $sumb$，复杂度为 $O(n)$。处理每次询问，扫的范围 刚好覆盖了整个序列，因此复杂度为 $O(n)$。扫 $p_i$ 以及动态更新 $sumc$，复杂度 $O(m)$。

总时间复杂度 $O(qn)$。根据该解法，可以通过 测试点 $3\sim11$。

参考核心代码

    p[m+1]=n+1;//边界条件
    long long sumc=0;//每次询问动态更新在P中i的c[i]总和
    for(i=1;i<=m+1;i++){
        dp[i]=INF;
        for(j=p[i-1]+1;j<=p[i]-1;j++)
            dp[i]=min(dp[i],sumc+a[j]+sumb[p[i]-1]-sumb[j]);//式子中的第一项
        dp[i]=min(dp[i],sumb[p[i]-1]-sumb[p[i-1]]+dp[i-1]);//第二项
        sumc+=c[p[i]];//更新sumc
        if(i<=m)
            dp[i]=min(dp[i],a[p[i]]+sumc);//第三项，注意多了c[p[i]]
    }
    printf("%lld\n",dp[m+1]);//输出答案

期望得分

$45$ 分。结合 测试点 $1\sim2$ 的算法可以获得 $55$ 分。

测试点 $12\sim13$

做法

记 $val_i=a_i-\displaystyle\sum_{j=1}^ib_j$，则前述有关 $dp$ 表达式也可写作：

$$dp_i=\min(\displaystyle\sum_{k=1}^{p_{i-1}}[k\in P]c_k+\displaystyle\sum_{k=1}^{p_i-1}b_k+\displaystyle\min_{j=p_{i-1}+1}^{p_i-1}val_j,dp_{i-1}+\displaystyle\sum_{k=p_{i-1}+1}^{p_i-1}b_k,a_{p_i}+\displaystyle\sum_{k=1}^{p_i}[k\in P]c_k) $$

对于第一个式子，使用 分块 事先计算每个整块内的 $val_i$ 的最小值即可。

正确性证明

上式中，第二、三个式子可以直接转移。

考虑将第一个式子进行变形：

$$\begin{aligned}\displaystyle\min_{j=p_{i-1}+1}^{p_i-1}\{\displaystyle\sum_{k=1}^{p_{i-1}}[k\in P]c_k+a_j+\displaystyle\sum_{k=j+1}^{p_i-1}b_k\} &=\displaystyle\sum_{k=1}^{p_{i-1}}[k\in P]c_k+\displaystyle\min_{j=p_{i-1}+1}^{p_i-1}\{a_j+\displaystyle\sum_{k=1}^{p_i-1}b_k-\displaystyle\sum_{k=1}^jb_k\}\\ &=\displaystyle\sum_{k=1}^{p_{i-1}}[k\in P]c_k+\displaystyle\min_{j=p_{i-1}+1}^{p_i-1}\{a_j-\displaystyle\sum_{k=1}^jb_k+\displaystyle\sum_{k=1}^{p_i-1}b_k\}\\ &=\displaystyle\sum_{k=1}^{p_{i-1}}[k\in P]c_k+\displaystyle\min_{j=p_{i-1}+1}^{p_i-1}\{val_j+\displaystyle\sum_{k=1}^{p_i-1}b_k\}\\ &=\displaystyle\sum_{k=1}^{p_{i-1}}[k\in P]c_k+\displaystyle\sum_{k=1}^{p_i-1}b_k+\displaystyle\min_{j=p_{i-1}+1}^{p_i-1}val_j \end{aligned}$$

可以发现，该式子变成了两个可预处理或动态更新的 定值 与一个 区间最小值 的形式，并且该序列 $val$ 不会发生改变。因此我们可以直接运用分块思想，处理出每一块的最小值，加速询问的回答。

在恒等变形中每一步都保证正确，因此思路正确。

具体实现

预处理 $val_i=a_i-sumb_i$，并对 $val$ 数组分块：每 $O(\sqrt n)$ 个元素切成一个块，并预处理第 $i$ 块中的 $val_i$ 最小值 $minn_i$。其余预处理与 测试点 $8\sim11$ 中所述相同。

对于每个询问，加速 dp 转移：对于第一个式子，计算 $\displaystyle\min_{i=l}^rval_i$ 时，将询问区间划分为中间的 整块 与两端 散块。对于所有整块，直接取对应块中的最小值；否则，暴力扫对应 散块区间，求最小值。求出区间最小值，并计算，更新答案。

其余仍按照 $dp$ 表达式转移即可。

最后输出 $dp_{m+1}$。

时间复杂度分析

由 测试点 $8\sim11$ 的分析可知，复杂度瓶颈在 dp。对于每次转移，分块求区间最小值，整块最多 $O(\sqrt n)$ 个，散块大小在 $O(\sqrt n)$ 级别，复杂度为 $O(\sqrt n)$，因此回答每次询问的复杂度为 $O(m\sqrt n)$。

总时间复杂度 $O((q+\sum m)\sqrt n)$。根据该解法，可以通过 测试点 $1\sim13$。

参考核心代码

void InitBlock(){//初始化分块，预处理每个块val[i]最小值
    siz=sqrt(n);
    int num=n/siz+(n%siz!=0);
    for(int i=1;i<=n;i++)
        bel[i]=i/siz+(i%siz!=0);
    for(int i=1;i<=num;i++){
        int bl=siz*(i-1)+1,br=siz*i;
        minn[i]=INF;
        for(int j=bl;j<=br;j++)
            minn[i]=min(minn[i],val[j]);//预处理出最小值
    }
}
long long Min(int l,int r){//暴力求区间最小值
    long long ans=INF;
    for(int i=l;i<=r;i++)
        ans=min(ans,val[i]);
    return ans;
}
long long MinInterval(int l,int r){//求区间最小值
    if(l>r)
        return INF;
    if(bel[l]==bel[r])
        return Min(l,r);//同一块内直接暴力求
    long long ans=INF;
    for(int i=bel[l]+1;i<=bel[r]-1;i++)
        ans=min(ans,minn[i]);//中间整块
    int rtl=bel[l]*siz,ltr=(bel[r]-1)*siz+1;
    return min({Min(l,rtl),ans,Min(ltr,r)});//两端散块取最小值，再与ans取min
}

期望得分

$75$ 分。$(4)$

测试点 $14\sim20$

做法

$dp$ 数组和 $val$ 数组含义与 测试点 $8\sim15$ 相同。

在每次计算转移方程的第一项时，使用 ST 表 快速求其中的 $\displaystyle\min_{j=p_{i-1}+1}^{p_i-1}val_j$ 即可。

正确性证明

dp 转移的正确性已经在 测试点 $8\sim11$ 中证明。

可以发现 $val$ 数组具有 静态 的特点，因此可以使用 ST 表加速求 静态区间最小值。

故该思路正确。

具体实现

使用 ST 表，预处理 $val$ 数组中每个 从 $i$ 开始，长度为 $2^j$ 的区间最小值，记为 $ST_{i,j}$。

在求区间 $[l,r]$ 的最小值时，令 $x=\lfloor\log_2(r-l+1)\rfloor$，只需求出 $\min(ST_{l,x},ST_{r-2^x+1,x})$ 即可。

仍按照上述 $dp$ 表达式进行转移。最终输出 $dp_{m+1}$。

时空复杂度分析

时间复杂度：对于每次 dp 转移，由于使用 ST 表，故可以做到 $O(1)$。因此处理所有询问，总复杂度为 $O(q+\sum m)$。预处理出 ST 表需要 $O(n\log n)$ 的复杂度。

总时间复杂度 $O(n\log n)$，可以通过 本题。

空间复杂度：ST 表本身需要 $O(n\log n)$ 的空间复杂度，其余数组空间复杂度为 $O(n)$。

空间复杂度 $O(n\log n)$，可以通过 本题。

参考核心代码

long long MinInterval(int l,int r){//ST表单次询问求区间最小值
    if(l>r)
        return INF;
    long long ex=log_2[r-l+1];
    return min(ST[l][ex],ST[r-(1<<ex)+1][ex]);
}
...//预处理部分
    for(i=1;i<=n;i++)
        ST[i][0]=val[i];
...
    for(i=1;i<=log_2[n];i++)
        for(j=1;j<=n-(1<<i)+1;j++)
            ST[j][i]=min(ST[j][i-1],ST[j+(1<<(i-1))][i-1]);//ST 表预处理
...
    ...
    dp[i]=min(dp[i],sumb[p[i]-1]+sumc+MinInterval(p[i-1]+1,p[i]-1));//转移该式子时只需调用MinInterval函数即可
    ...//其余的dp转移

期望得分

$100$ 分。

---

$(1)$ 实际上，该实现也通过了 测试点 $7$。

$(2)$ 实际上，该实现也通过了 测试点 $4$。

$(3)$ 实际上，该实现也通过了 测试点 $1\sim2,12\sim13,17$。

$(4)$ 实际上，该实现也通过了 测试点 $14\sim20$。