考虑 dp。设 \(f_i\) 表示到位置 \(i\) 所需的最小花费，且第 \(i\) 个位置必选，现在要找上一个决策点 \(j\)，这个点应该要在此前所有区间的左端点的后面，才能保证这些区间能被覆盖（即确保至少一个在之前每个区间内），则 \(j\) 应满足 \(\max_{r_k<i}l_k \le j < i\)，转移方程 \(f_i=\min_{{\max_{r_k<i}l_k} \le j < i}f_j+a_i\)。左边部分将区间按右端点排序后双指针即可，转移使用单调队列即可。
实现时可以令 \(a_{n+1}=0\)，这样 \(f_{n+1}\) 可以直接作为答案输出。时间复杂度 \(O(\sum(n+m\log m))\)。
#include<iostream>
#include<cstdio>
#include<algorithm>
#define N 1000010
#define int long long
using namespace std;
int n,m,L,R,a[N],q[N],f[N];
struct line{int l,r;
}c[N];
bool cmp(line x,line y){return x.r<y.r;
}
void solve(){cin>>n;for(int i=1;i<=n;i++)cin>>a[i],f[i]=0; a[n+1]=0;cin>>m;for(int i=1;i<=m;i++)cin>>c[i].l>>c[i].r;sort(c+1,c+m+1,cmp);int j=1;int mx=0;f[1]=a[1];L=1,R=2;q[L]=0,q[R]=1;for(int i=2;i<=n+1;i++){while(j<=m&&c[j].r<i)mx=max(mx,c[j].l),j++;while(L<=R&&q[L]<mx)L++;f[i]=f[q[L]]+a[i];while(L<=R&&f[q[R]]>=f[i])R--;q[++R]=i;// cout<<q[L]<<' '<<i<<' '<<f[i]<<endl;}cout<<f[n+1]<<'\n';return;
}
signed main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T;cin>>T;while(T--)solve();return 0;
}