传送门：洛谷 CF2244D Yaroslav and Productivity | Codeforces D. Yaroslav and Productivity
更佳的阅读体验：CF2244D 题解

简要题意：给你两个序列 $a$ 和 $b$，每次操作可以选定一个位置 $i$，翻转 $[1, b_i]$ 上的 $a_i$ 的符号，你需要进行任意次操作来最大化 $\sum a_i$。$m \le n \le 2 \times 10^5$。

这里有一个很重要的观察，就是如果我们对 $b$ 排序，把 $b_i$ 当作 $a$ 上的“分隔点”位置，那么就一定存在一种操作的方案，使得相邻两个 $b_i$ 之间对应的 $a_i$ 的符号可以独立决定。

也就是说，我们对 $b$ 排序后，$a$ 就可以被分为形如

$$ [1, b_1], [b_1 + 1, b_2], \cdots, [b_{m - 1} + 1, b_m], [b_m + 1, n] $$

的 $m + 1$ 个区间。我们可以独立决定每个区间内是保持原来的符号，还是整体取反。

此时我们发现，答案其实就是区间和的绝对值再求和。

单组数据时间复杂度 $O(n + m \log m)$。

#include <iostream>
#include <algorithm>
using namespace std;
using ll = long long;

const int N = 2e5 + 10;
int t, n, m;
ll a[N], b[N], ans;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    for (cin >> t; t; --t) {
        ans = 0;
        cin >> n >> m;
        for (int i = 1; i <= n; ++i) {
            cin >> a[i];
            a[i] += a[i - 1];
        } for (int i = 1; i <= m; ++i) cin >> b[i];
        sort(b + 1, b + m + 1);
        for (int i = 1; i <= m; ++i) ans += abs(a[b[i]] - a[b[i - 1]]);
        cout << ans + a[n] - a[b[m]] << '\n';
    } return 0;
}