P9744 「KDOI-06-S」消除序列
题解
记错时间错过模拟赛的 sb 来也。
题目中的最关键信息就是 \(a_i,b_i,c_i\ge 0\)，这意味着多做无用的操作一定不优，所以有：
-
结论 \(1\)：优先进行 \(1\) 操作。
这是因为我们不管我们在 \(1\) 操作前做什么操作都会被其推平覆盖，是无用操作。 -
结论 \(2\)：最多只进行一次 \(1\) 操作。
也是显然的，我们一定会保留范围最广的一次 \(1\) 操作，这样其他 \(1\) 操作都是无用操作。
到这里，一个显然的想法就出现了：枚举 \(1\) 操作的 \(i\)，并通过前后缀和快速计算其他操作的最小代价。
然而这会是 \(O(nq)\) 的，难以通过。
观察数据范围里出现了一个神奇的东西：\(\sum m\)，所以我们的目标是推出一个单次询问复杂度带 \(m\) 的算法。
然后我们开始小小的推一波式子：设 \(1\) 操作的位置 \(i\) 满足 \(p_j\le i<p_{j+1}\)，那么易知此时的代价为 \(a_i+\sum_{k=i+1}^n b_k+\sum_{k=1}^j c_{p_k}-\sum_{k=j+1}^m b_{p_k}\)。
对于同样的 \(j\)，后面的 \(\sum_{k=1}^j c_{p_k}-\sum_{k=j+1}^m b_{p_k}\) 贡献一定，所以我们只要快速求出区间中前两项的最小值，刚好，前两项只与 \(i\) 有关，所以我们可以使用 ST 表或线段树来解决。
最后再考虑一下不使用 \(1\) 操作的情况即可。
复杂度 \(O(\sum m\log n)\)。
代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read() {
int s=0,m=0;char ch=getchar();
while(!isdigit(ch)) {if(ch=='-')m=1;ch=getchar();}
while( isdigit(ch)) s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
return m?-s:s;
}
int n,q,a[500005],b[500005],c[500005];
int p[500005],prec[500005],sufb[500005];
struct Sparse_Table {
int st[500005][25];
void init(int n,int v[]) {
memset(st,0x3f,sizeof(st));
for(int i=1;i<=n;i++) st[i][0]=v[i];
for(int j=1;(1<<j)<=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]);
}
int query(int l,int r) {
if(l>r) return INT_MAX;
int k=log2(r-l+1);
return min(st[l][k],st[r-(1<<k)+1][k]);
}
} st;//ST 表
signed main() {
cin>>n;
for(int i=1;i<=n;i++)
a[i]=read();
for(int i=1;i<=n;i++)
b[i]=read();
for(int i=1;i<=n;i++)
c[i]=read();
int sum=0;
for(int i=n;i;i--)
a[i]+=sum,sum+=b[i];
st.init(n,a);
cin>>q;
while(q--) {
int m=read();
for(int i=1;i<=m;i++)
p[i]=read();
prec[0]=sufb[m+1]=0;
for(int i=1;i<=m;i++)
prec[i]=prec[i-1]+c[p[i]];
for(int i=m;i;i--)
sufb[i]=sufb[i+1]+b[p[i]];
int ans=sum-sufb[1];//不使用 1 操作
ans=min(ans,st.query(1,p[1]-1)-sufb[1]);//第一段
for(int i=1;i<m;i++)
ans=min(ans,st.query(p[i],p[i+1]-1)+prec[i]-sufb[i+1]);
ans=min(ans,st.query(p[m],n)+prec[m]);//最后一段
printf("%lld\n",ans);
}
return 0;
}