题目大意：
给出数组a，问对于所有满足\(1\le k\le n\)的奇数\(k\)，\(f([a_1,a_2,...,a_k])\)的值。\(f([a_1,a_2,...,a_n])\)的值为对数组\([a_1,a_2,...,a_n]\)进行\(\frac{n+1}{2}\)次操作（选择数组中的三个元素，将其中一个取相反数，然后让它们合并成一个元素）后,数组最后剩下元素的最大值。
考虑数组中每个元素对答案的贡献（答案为所有元素的贡献之和）。
操作之前，数组中第\(i\)个元素对答案的贡献为\(a_i\)。每经过一次操作后，其中一个元素对答案的贡献就会变成相反数（这个元素的贡献变成相反数后不会再通过操作改变贡献）。因此经过\(\frac{k+1}{2}\)次操作之后，会有\(\frac{k+1}{2}\)个元素的贡献变成相反数。
因此，如果我们要让贡献之和最大，只需要将\([a_1,a_2,...,a_k]\)中最小的\(\frac{k+1}{2}\)个元素取相反数即可。
具体实现中，我们可以开两个优先队列。\(k\)从\(1\)枚举到\(n\)的过程中，队列1储存较小的\(\frac{k+1}{2}\)个元素，队列2储存剩下较大的元素。对于每个\(k\)，答案即为队列2元素之和减去队列1的元素之和。
#include<bits/stdc++.h>
#define pt printf(">>>")
#define mid (((l)+(r))/2)
using namespace std;
typedef long long ll;
const ll N=1e6+10,inf=1e18+10,mod=1e9+7;
ll n,q,a[N],dp[N];
int main(){
int T;
cin >> T;
while(T--){
cin >> n >> q;
for(ll i=1;i<=n;i++)cin >> a[i];
priority_queue<ll> que1;
priority_queue<ll,vector<ll>,greater<ll> > que2;
que1.push(-inf);
que2.push(a[1]);
que2.push(inf);
ll sum1=0,sum2=a[1];
for(ll i=1;i<=n;i+=2){
dp[i]=sum2-sum1;
if(i<n){
if(a[i+1]<=que1.top())que1.push(a[i+1]),sum1+=a[i+1];
else que2.push(a[i+1]),sum2+=a[i+1];
if(a[i+2]<=que1.top())que1.push(a[i+2]),sum1+=a[i+2];
else que2.push(a[i+2]),sum2+=a[i+2];
while(que1.size()<i/2+1+1){
ll v=que2.top();que2.pop();
que1.push(v);
sum1+=v,sum2-=v;
}
while(que1.size()>i/2+1+1){
ll v=que1.top();que1.pop();
que2.push(v);
sum1-=v,sum2+=v;
}
}
}
while(q--){
ll k;
cin >> k;
cout << dp[k] << ' ';
}
cout << endl;
}
return 0;
}