前言
提供一种不需要并查集的严格线性做法。
其实也差不了多少。
题目
分析
题目描述稍微有点复杂，其实我们可以直接看成是这样的问题：
给定 (m) 个多米诺骨牌，每个有高度和价值，要求推倒所有的骨牌，求最小代价。（推动的规则见题面最后一段）
显然可以考虑 dp 来做，设 (dp[i]) 表示推倒前 (i) 个骨牌需要的最小代价。
为了描述的方便，我们设 (L[i]) 表示 (i) 往左最远可以推倒的点， (R[i]) 同理。
那么转移方程其实也很好写，考虑这样的决策点 (j) ，有两种情况。
第一种：（用 (i) 推倒 ([j,i]) 区间的骨牌）
那么其实有一个显而易见的贪心就是每次直接让 (i) 在 (L[i]) 处决策：
接下来考虑第二种情况：（用 (j) 推倒 ([j,i]) 区间的骨牌）
这时我们发现，这个决策并不好做，因为即使我们求出了 (R) 数组，也需要使用数据结构维护后缀最小值，而不能做到线性复杂度。
那么接下来就是题目的性质了：
如果有 (R[j]ge i (j<i)) ，那么一定有 (R[j]ge R[i]) ！（因为 (j) 可以推倒 (i)）
根据上面的分析，我们可以得到这样的结论：
对于每一个 ([i,R[i]]) 区间，要么较小的 (i) 对应区间包含另一个，要么互不相交。
也就是对于 (i,j (i<j)) ，其区间要么是 ([i,R[i]]) 包含 ([j,R[j]]) ，要么是 (ile R[i]<jle R[j])
于是我们可以在这里考虑维护一个单调栈，按照 (dp[j-1]+cost[j]) 单调递增。
而此时，栈内的决策点也一定满足条件：(R[i]) 单调不降。（原因就是上面的性质，要么包含，不包含的直接在弹栈时弹出去了）
然后每次使用栈顶更新答案即可。（这个部分具体可以看代码最后一点的实现）
代码
#include<bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T &x){
x=0;bool f=false;char ch=getchar();
while(!isdigit(ch)){f|=ch=='-';ch=getchar();}
while(isdigit(ch)){x=x*10+(ch^48);ch=getchar();}
x=f?-x:x;
return ;
}
template<typename T>
inline void write(T x){
if(x<0) x=-x,putchar('-');
if(x>9) write(x/10);
putchar(x%10^48);
return ;
}
const int N=3e5+5,M=1e7+5;
#define PII pair<int,int>
#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define ll long long
int n,m,k,h[M],cnt;
vector<ll>a[N],b[N];
int que[M],hh=1,tt,L[M],R[M];
ll dp[M],v[M];
signed main(){
read(n),read(m);
for(register int i=1,len,x;i<=n;i++){
read(len);
for(register int j=1;j<=len;j++) read(x),a[i].pb(x);
for(register int j=1;j<=len;j++) read(x),b[i].pb(x);
}
read(k);
for(register int i=1,id,mul;i<=k;i++){
read(id),read(mul);
const int len=a[id].size();
for(register int j=0;j<len;j++) h[++cnt]=a[id][j],v[cnt]=b[id][j]*mul;
}
for(register int i=1;i<=cnt;i++){//求 L 数组
while(hh<=tt&&i-h[i]<=que[tt]-h[que[tt]]) tt--;
if(hh>tt||i-h[i]>=que[tt]) L[i]=max(1,i-h[i]+1);
else L[i]=L[que[tt]];
que[++tt]=i;
}
hh=1,tt=0;
for(register int i=cnt;i>=1;i--){//求 R 数组
while(hh<=tt&&i+h[i]>=que[tt]+h[que[tt]]) tt--;
if(hh>tt||i+h[i]<=que[tt]) R[i]=min(cnt,i+h[i]-1);
else R[i]=R[que[tt]];
que[++tt]=i;
}
tt=0;
for(register int i=1;i<=cnt;i++){//dp转移
dp[i]=dp[L[i]-1]+v[i];//第一种情况
while(tt&&R[que[tt]]<i) tt--;//查看当前状态到底是包含还是相离
if(tt) dp[i]=min(dp[i],dp[que[tt]-1]+v[que[tt]]);//如果是包含
if(!tt||dp[i-1]+v[i]<dp[que[tt]-1]+v[que[tt]]) que[++tt]=i;//如果栈内没有元素或者有更好的决策点
}
//可以发现，每时每刻其实都保证了栈内决策点的 R 一定单调不降！
write(dp[cnt]);
return 0;
}