B. Artistic Balance Tree

时间限制：1.5 秒
内存限制：256 MB

问题描述

在学习了艺术平衡树之后，Lizhou 遇到了以下问题。

你有一个由 $n$ 个整数组成的数组 $a$ 。你需要按顺序对 $a$ 执行恰好 $m$ 次操作。每次操作包含两个步骤。具体地，在第 $i$ 次操作中，你会得到一个整数 $x_i$ ，然后你需要：

首先，选择一个中心下标 $u$ 和一个非负长度 $y$ ，使得区间 $[u-y, u+y]$ 完全落在 $[1, n]$ 内（即 $u-y \ge 1$ 且 $u+y \le n$ ）。对于每个 $1 \le i \le y$ ，交换元素 $a_{u-i}$ 和 $a_{u+i}$ 。
然后，标记下标 $x_i$ 处的元素。如果该元素已经被标记，则什么也不做。注意，标记是打在元素上的，而不是打在位置上的。这意味着如果将来某次操作将该元素与其他元素交换，标记仍会跟随该元素。

在执行完所有 $m$ 次操作后，你的任务是找到所有未标记元素的最小可能总和。

输入格式

每个测试包含多个测试用例。第一行包含整数 $t$ （ $1 \le t \le 10^4$ ），表示测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$ （ $1 \le n, m \le 10^5$ ）——数组 $a$ 的长度和操作次数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ （ $-10^9 \le a_i \le 10^9$ ）——数组 $a$ 的元素。

第三行包含 $m$ 个整数 $x_1, x_2, \dots, x_m$ （ $1 \le x_i \le n$ ）——每次操作中要标记的位置下标。

保证所有测试用例的 $n$ 之和不超过 $10^5$ 。
保证所有测试用例的 $m$ 之和不超过 $10^5$ 。

输出格式

对于每个测试用例，输出一个整数——所有操作结束后未标记元素的最小可能总和。

样例输入

6
7 4
1 2 3 4 5 6 7
1 2 3 4
7 4
1 -2 3 4 -5 -6 -7
7 6 5 4
7 5
21 -45 234 -8 423 12 -987
6 6 6 6 6
7 5
-21 45 -234 8 -423 -12 987
7 7 7 7 7
7 3
-1 2 -3 4 5 6 7
1 2 3
7 3
-1 -2 -3 -4 -5 -6 -7
1 2 3

样例输出

样例说明

第一个测试用例：一种最优操作序列如下：

选择中心 $u = 4$ ，长度 $y = 3$ ，数组变为 $[7,6,5,4,3,2,1]$ 。然后标记元素 $a_1 = 7$ 。
选择中心 $u = 1$ ，长度 $y = 0$ ，数组不变。然后标记元素 $a_2 = 6$ 。
选择中心 $u = 1$ ，长度 $y = 0$ ，数组不变。然后标记元素 $a_3 = 5$ 。
选择中心 $u = 1$ ，长度 $y = 0$ ，数组不变。然后标记元素 $a_4 = 4$ 。

最终未标记的元素是 $1, 2, 3$ ，总和为 $1 + 2 + 3 = 6$ 。

第二个测试用例：一种最优操作序列如下：

选择中心 $u = 4$ ，长度 $y = 3$ ，数组变为 $[-7,-6,-5,4,3,-2,1]$ 。然后标记元素 $a_7 = 1$ 。
选择中心 $u = 5$ ，长度 $y = 1$ ，数组变为 $[-7,-6,-5,-2,3,4,1]$ 。然后标记元素 $a_6 = 4$ 。
选择中心 $u = 1$ ，长度 $y = 0$ ，数组不变。然后标记元素 $a_5 = 3$ 。
选择中心 $u = 5$ ，长度 $y = 1$ ，数组变为 $[-7,-6,-5,4,3,-2,1]$ 。然后标记元素 $a_4 = 4$ 。

未标记的元素是 $-2, -5, -6, -7$ ，总和为 $(-2) + (-5) + (-6) + (-7) = -20$ 。

AC 代码

很有意思的奇偶位置转换题目，需要看清题目的本质就是奇偶位置互不影响
然后我们给奇偶分开讨论
单独对于奇数，我们需找到所有大于零的数，然后尽量删了，如果大于零的数多，那就尽量删，否则就只删大于零的，因为可以通过交换做到一直标记一个数

当然还需要一定的特判，正常来说是不删负数，但是必须标记一个负数的时候，我们就标记最小的，写一个判断

// Problem: CF 2222 B
// Contest: Codeforces - Spectral::Cup 2026 Round 1 (Codeforces Round 1094, Div. 1 + Div. 2)
// URL: https://codeforces.com/contest/2222/problem/B
// Memory Limit: 256 MB
// Time Limit: 1500 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
#define int long long

void fun(vector<int>& p){
    sort(p.begin(),p.end());
    //p.erase(unique(p.begin(),p.end()),p.end());
    reverse(p.begin(),p.end());
}

void solve(){
    int n,m;
    cin>>n>>m;
    vector<int> a(n+1),p(m),ao,ae;
    int sum=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum+=a[i];
        if(i&1) ao.push_back(a[i]);
        else ae.push_back(a[i]);
    }

    fun(ao);
    fun(ae);

    int cnto=0,cnte=0;
    for(int i=0;i<m;i++){
        cin>>p[i];
        if(p[i]&1) cnto++;
        else cnte++;
    }
    //cout<<cnto<<" "<<cnte<<endl;

    int ans=0;
    for(int i=0;i<ao.size()&&i<cnto;i++){
        //cout<<ao[i]<<endl;
        if(i&&ao[i]<=0) break;
        ans+=ao[i];
    }
    for(int i=0;i<ae.size()&&i<cnte;i++){
        //cout<<ae[i]<<endl;
        if(i&&ae[i]<=0) break;
        ans+=ae[i];
    }

    cout<<sum-ans<<endl;

    return ;
}


signed main(){
    int t;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}