@
目录Desciption
给定一个长度为 \(i\) 的序列 \(v_1,v_2,\dots,v_n\)，初始时所有元素的值都为 \(1\)。
对于下标 \(i\) 有 \(3\) 种操作：
- 将 \(v_1,v_2,\dots,v_i\) 的值变为 \(0\)，费用是 \(a_i\)。
- 将 \(v_i\) 的值变为 \(0\)，费用是 \(b_i\)。
- 将 \(v_i\) 的值变为 \(1\)，费用是 \(c_i\)。
有 \(q\) 次询问，每次询问给定一个大小为 \(m\) 的集合 \(P\)，问最少需要多少费用，使得 \(i\in P,v_i=1(1\le i\le n),j\notin P ,v_j=0(1\le j\le n)\)。
Solution
引理：在一次询问内，第一种操作最多只会进行一次。
设 \(i,j(i<j)\) 分别进行了一次操作一。
如果先在 \(j\) 进行操作一，就已经把 \(v1,\dots ,vi\) 变为 \(0\) 了，再操作是不优的。
所以遍历每一个 \(i\)，发现在 \(i\) 做操作一时，答案为 \(a_i+\sum\limits_{j=i+1,j\notin P}^n b_j+\sum\limits_{j=1,j\in P}^{i} c_j\)，这个式子可以用前缀和优化。
设 \(sum1_i=\sum\limits_{j=1}^i b_j(1\le i\le n),sum2_i=\sum\limits_{j=1}^mb_{P_j}(1\le i\le m),sum3_i=\sum\limits_{j=1}^m c_{P-j}(1\le i\le m)\)。
式子转换为 \(a_i+sum1_n-sum1_i-(sum2_m-sum2_j)+sum3_j(P_j\le i,P_{j+1}>i)\)。
此时时间复杂度为 \(O(qn)\)，需要进一步优化。
发现对于在 \(P_i\) 和 \(P_{i+1}\) 之间操作操作一（不含两端），\(j\) 是相同的，所以我们只需预处理求出 \(g_k=a_k+sum1_n-sum1_k\)，再处理出区间内 \(g\) 的最小值。可以用线段树或 ST表维护。
此时对于 \(i\)，得出 \([P_i+1,P_{i+1}-1]\) 内 \(g\) 的最小值再加上式子中其他的值即可，\([P_m+1,n]\) 也要计算。
还要计算刚好在 \(i\) 上做操作一时的值，没有操作一时的值以及没有操作二时的值，所有可能答案取最小即可。
时间复杂度 \(O(qm)\)。
Code
#include<bits/stdc++.h>
using namespace std;
#define int long long //记得开long long
int n,q;
int a[500050],b[500050],c[500050];
int p[500050];
int lg[500050],st[500050][22];
int sum1[500050],sum2[500050],sum3[500050];
int get_st(int l,int r){
if(l>r) return 100000000000;
int len=lg[r-l+1];
return min(st[l][len],st[r-(1<<(len))+1][len]);
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=2;i<=n;i++){
lg[i]=lg[i>>1]+1;
}
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
cin>>b[i];
sum1[i]=sum1[i-1]+b[i];
}
for(int i=1;i<=n;i++){
cin>>c[i];
st[i][0]=sum1[n]-sum1[i]+a[i]; //得出g值
}
for(int j=1;j<=lg[n];j++){
for(int i=1;i+(1<<j)-1<=n;i++){
st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]); //预处理ST表求区间内最小的g
}
}
cin>>q;
while(q--){
int m;
cin>>m;
for(int i=1;i<=m;i++){
cin>>p[i];
sum2[i]=sum2[i-1]+b[p[i]];
sum3[i]=sum3[i-1]+c[p[i]];
}
int ans=100000000000;
for(int i=1;i<=m;i++){
ans=min(ans,min(get_st(p[i-1]+1,p[i]-1)-sum2[m]+sum2[i-1]+sum3[i-1],a[p[i]]+sum1[n]-sum1[p[i]]-(sum2[m]-sum2[i])+sum3[i])); //min内第一个数是取区间，第二个数是刚好取pi
}
ans=min(ans,sum1[n]-sum2[m]); //没有操作一
ans=min(ans,get_st(p[m]+1,n)+sum3[m]); //没有操作二
cout<<ans<<endl;
}
return 0;
}