思维妙妙题。
赛时的错误做法：
-
找到每个点往后进位变优的位置，最多 \(O(\log)\) 个；
-
然后从前往后能变优就变优，往后贪心进位。
hack 数据：
0
1
3
3 5 100
2 1 0
2 2
输出：100
这样子由于 \(1\) 到 \(2\) 不优，而 \(1\) 到 \(3\) 个数不够，所以导致无法进位到 \(3\)。
所以加强一下贪心策略。
用若干二元组 \(a_j=(c_j,v_j)\) 表示在当前的第 \(i\) 位，可以【最多 \(c_j\) 次】付出【前 \(i\) 位 \(v_j\) 的代价】换一个【 \(i\) 位的 \(1\)】。
注：此时已经使得 \(a_j\) 关于 \(v_j\) 升序，保证贪心顺序。
然后考虑共有那些操作：
-
从第 \(i\) 位到第 \(i+1\) 位，第 \(i\) 位的 \(x_i\) 个 \(1\) 可以变成 \(1\) 个第 \(i+1\) 位的 \(1\)，贪心的每次用前 \(x_i\) 个合并成一个即可。
-
插入 \((c_i,v_i)\)，为了保证单调性，发现如果 \((c,v)\) 满足 \(v<v_i\)，那么是可以使用该操作获得 \(v_i-v\) 的收益，所以把所有 \(v<v_i\) 的合并掉，并把 \((c,v)\) 加入开头即可。
注：此时需要把 \(c_i\leftarrow c_i+c\)。
这样的复杂度最坏可以到达 \(O(n^2)\)，而且这样合并之后的 \(v\) 会非常大，然而这样的 \((c,v)\) 却没有任何作用，所以新增一个操作：把序列末位 \(v>10^9\) 的二元组弹掉。
只需用 deque 维护即可，时间复杂度：\(O(n\log n)\)。
代码
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=2e5+10,INF=1e9,mod=998244353;
int T,n,a[N],b[N],c[N];
struct zj{
ll cnt,val;
};
void get(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=n;i++)scanf("%d",&b[i]);
for(int i=1;i<n;i++)scanf("%d",&c[i]);
deque<zj>q;
int ans=0;
auto merge=[&](int x){
ll cnt=0,val=0;
deque<zj>p;
for(zj t:q){
if(cnt+t.cnt<x)cnt+=t.cnt,val+=t.cnt*t.val;
else{
p.push_back({1,val+(x-cnt)*t.val});
t.cnt-=x-cnt,cnt=0;
if(t.cnt>=x)p.push_back({t.cnt/x,t.val*x});
cnt=t.cnt%x,val=cnt*t.val;
}
}
q.swap(p);
};
auto reduce=[&](){
for(;!q.empty()&&q.back().val>INF;q.pop_back());
};
auto insert=[&](zj x){
for(;!q.empty()&&q.front().val<x.val;q.pop_front()){
ans=(ans+(x.val-q.front().val)*q.front().cnt)%mod;
x.cnt+=q.front().cnt;
}
q.push_front(x);
};
for(int i=1;i<=n;i++){
reduce();
ans=(ans+1ll*b[i]*a[i])%mod;
insert({b[i],a[i]});
if(i<n&&c[i]>1)merge(c[i]);
}
printf("%d\n",ans);
}
int main(){
freopen(".in","r",stdin);
//freopen(".out","w",stdout);
for(scanf("%*d%d",&T);T--;)get();
return 0;
}