Description：

给一排多米诺骨牌，朝某个方向放倒某个骨牌花费一定的费用，求用最小的费用使得所有骨牌都倒下。

$1\leqslant n\leqslant 10^7$

Solution：

首先预处理出 $lef[i]$ 和 $rig[i]$ 表示朝某个方向放倒第 $i$ 个骨牌回放到的最远一个骨牌，然后就可以 $DP$ 了，设 $f[i]$ 表示 $i$ 这个前缀的骨牌都倒了的最小花费，那么 $i$ 有两种可能，一是往左倒，二是被一个向右倒的放倒，于是开一个树状数组记录向右倒到每个位置的最小花费，那么显然只有当这个位置大于等于 $i$ 时 $i$ 会被放倒，这个也就是个后缀最小值，可以用树状数组维护，转移方程是： $$ \begin{align} &f[i]=\min(f[lef[i]-1]+cst[i],querymin(i,n))\\ &add(rig[i],f[i-1]+cst[i]) \end{align} $$

Code：

#include<bits/stdc++.h>

using namespace std;

int n,m;

#define MAXN 250010

#define MAXM 10000010

#define INF 0x3f3f3f3f3f3f3f3f

typedef long long ll;

inline ll rd()

{

	register ll res = 0,f = 1;register char c = getchar();

	while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}

	while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

	return res * f;

}

int siz[MAXN];

vector< pair<int,ll> > v[MAXN];

#define fi first

#define se second

#define R register

int l;

vector< pair<int,ll> > a;

int lef[MAXM],rig[MAXM];

ll c[MAXM];

int lowbit(int x){return x & (-x);}

void add(int p,ll x){for(R int i = p;i >= 1;i -= lowbit(i))c[i] = min(c[i],x);return;}

ll query(int p){R ll res = INF;for(R int i = p;i <= m;i += lowbit(i))res = min(res,c[i]);return res;}

ll f[MAXM];

int main()

{

	n = rd();m = rd();

	for(R int i = 1;i <= n;++i)

	{

		siz[i] = rd();v[i].resize(siz[i]);

		for(R int p = 0;p < siz[i];++p)v[i][p].fi = rd();

		for(R int p = 0;p < siz[i];++p)v[i][p].se = rd();

	}

	l = rd();

	R int id;

	R ll mul;

	memset(c,0x3f,sizeof(c));

	a.push_back(make_pair(0,0));

	for(R int i = 1;i <= l;++i)

	{

		id = rd();mul = rd();;

		for(R int p = 0;p < v[id].size();++p)

		{

			a.push_back(v[id][p]);

			a[a.size() - 1].se *= mul;

		}

	}

	for(R int i = 1;i <= m;++i)

	{

		R int j = i;

		while(j > 1 && j > i - a[i].fi + 1)j = lef[j - 1];

		lef[i] = j;

	}

	for(R int i = m;i >= 1;--i)

	{

		R int j = i;

		while(j < m && j < i + a[i].fi - 1)j = rig[j + 1];

		rig[i] = j;

	}

	for(R int i = 1;i <= m;++i)

	{

		f[i] = min(f[lef[i] - 1] + a[i].se,query(i));

		add(rig[i],f[i - 1] + a[i].se);

	}

	cout << f[m] << endl;

	return 0;

}