这道题在比赛时先花了一个小时理解好题意才打了一个 \(70\) 分的 \(O(n^2)\) 暴力。下午刚起床，有点困，还没进入状态，打得挺慢。
具体地，会发现操作实际上是在这个长度为 \(n\) 的序列找一个点 \(i\)，将 \([0,i]\) 通过操作 \(1\) 全变 \(0\)，设 \(x=\displaystyle\sum_{k\in P}(k≤i)×c_k\)，\(y=\displaystyle\sum_{k=i+1}^{n}b_i-\displaystyle\sum_{k\in P}(k>i)×b_k\)，说人话就是 \(x\) 表示把前面已经统一为 \(0\) 的区间再把一些值变回 \(1\) 使得区间 \([0,i]\) 满足限制的代价，\(y\) 表示后面没有统一变为 \(0\) 的区间把一些值变为 \(0\) 使得区间 \([i+1,n+1]\) 满足限制的代价，那么该操作的总代价为 \(a_i+x+y\)，考虑直接枚举 \(i\)，边扫边维护，对于每个 \(i\)，\(O(1)\)求出来然后答案取 \(min\)，总复杂度 \(O(nq)\)，可拿到 \(70\) 分。
#include<bits/stdc++.h>
#define ll long long
#define N 500001
using namespace std;
ll n,a[N],b[N],c[N],q,m,p[N],tr[N<<2],sumb,ans;
int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)cin>>b[i],sumb+=b[i];
for(int i=1;i<=n;i++)cin>>c[i];
cin>>q;
while(q--){ll sumc=0,sum=sumb;
cin>>m,ans=1000000000000000;
for(int i=1;i<=m;i++)cin>>p[i],sum-=b[p[i]];
for(int i=0,j=1;i<=n;i++){
if(j<=m&&i>=p[j])sumc+=c[p[j]],j++;
else sum-=b[i];
ans=min(ans,a[i]+sumc+sum);
}
cout<<ans<<'\n';
}
}
考虑优化，这道题我第一眼线段树，但一开始脑子抽了，打了暴力后才想到怎么维护，花了 \(30\) 分钟调出来。整道题花了我一个半小时，感觉打得有点慢。
考虑 \(v_i\) 和 \(v_{i+1}\) 之间，发现 \([v_i,v_{i+1})\) 区间中任意取的 \(a\) ，加的 \(x\) 是相等的。
那么我们可以对于每个 \([l,r]\)，线段树维护 \(\displaystyle\min_{l≤i≤r}a_i\) 。
但我们发现虽然 \([v_i,v_{i+1})\) 之间加的 \(x\) 是相同的，但是 \(y\) 不相同，这样维护的线段树不能确保能找到总代价最小的值。
我们能不能用线段树维护 \(\displaystyle\min_{l≤i≤r}a_i+y\) 呢？我们发现只需要开一个关于 \(b\) 的后缀树组 \(sumb\)，因为我们只需要维护区间 \([v_i,v_{i+1})\) 中 \(y\) 的相对大小。所以可以线段树维护 \(\displaystyle\min_{l≤i≤r}a_i+sumb_i\)。区间查询 \([v_i,v_{i+1})\) 后只需再减去 \(sumb\) 多加上的 b，时间复杂度\(O(logn\sum m)\)。
#include<bits/stdc++.h>
#define ll long long
#define N 500001
using namespace std;
ll n,a[N],b[N],c[N],q,m,p[N],tr[N<<2],sumb[N],ans;
void build(ll rt,ll l,ll r){if(l==r){tr[rt]=a[l]+sumb[l];return;}
ll mid=(r+l)>>1;
build(rt<<1,l,mid),build(rt<<1|1,mid+1,r);
tr[rt]=min(tr[rt<<1],tr[rt<<1|1]);
}
ll ask(ll rt,ll l,ll r,ll x,ll y){if(x<=l&&r<=y){return tr[rt];}
ll mid=(r+l)>>1,minn=1000000000000000;
if(mid>=x)minn=min(minn,ask(rt<<1,l,mid,x,y));
if(mid<y)minn=min(minn,ask(rt<<1|1,mid+1,r,x,y));
return minn;
}
int main(){//freopen("reserve.in","r",stdin),freopen("reserve.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)cin>>b[i];
for(int i=1;i<=n;i++)cin>>c[i];
for(int i=n;i>=0;i--)sumb[i]=sumb[i+1]+b[i+1];
cin>>q,build(1,0,n);
while(q--){ll sumc=0,sum=0;
cin>>m,ans=1000000000000000;
for(int i=1;i<=m;i++)cin>>p[i],sum+=b[p[i]];
p[m+1]=n+1;
for(int i=0;i<=m;i++){ll x=p[i],y=p[i+1]-1,res=ask(1,0,n,x,y);
res-=(sum-=b[p[i]]),sumc+=c[p[i]];
ans=min(ans,res+sumc);
}
cout<<ans<<'\n';
}
}
最后贴一张我的提交记录：
