自动搬运

查看原文

来自洛谷，原作者为

	meyi 明日黄花

搬运于2025-08-24 22:52:06，当前版本为作者最后更新于2023-10-30 13:55:12，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先发现对于 $1\le i,j\le m$，若 $\lfloor\frac{m}{i}\rfloor=\lfloor\frac{m}{j}\rfloor$，则 $i$ 和 $j$ 可以看作是一个等价类。由整数分块的思想可知等价类是一段区间 $[i,j]$，且对于正整数 $k$，若 $i\times k\le m$，则 $[i\times k,j\times k]$ 是另一个等价类的子区间。由于本题的限制只有乘积 $\le m$，所以一个等价类内的数可以看作是同一个数，也即值域大小降为了 $O(\sqrt V)$。

考虑如何朴素地求出答案，设 $f_{i,j}$ 表示已经考虑了前 $i$ 个可重集，当前的乘积所在的等价类是 $j$，设 $mul_{j,k}$ 表示等价类 $j$ 乘上常数 $k$ 后得到的等价类，那么选取元素有转移 $f_{i,j}+s_{i+1,x}\rightarrow f_{i+1,mul_{j,m_{i+1,x}}}$，不选元素有转移 $f_{i,j}\rightarrow f_{i+1,j}$，直接线性转移即可，时间复杂度 $O(tot\times q\sqrt V)$。

然后你发现这个东西本质是个背包，把物品塞进去的顺序是没有影响的，所以直接分治，每次求出跨过当前分治中心的询问的答案，合并左子区间的后缀和右子区间的前缀即可。时间复杂度 $O((tot\log n+q)\sqrt V)$。

代码：

#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
#define ALL(v) v.begin(),v.end()
#define For(i,_) for(int i=0,i##end=_;i<i##end;++i) // [0,_)
#define FOR(i,_,__) for(int i=_,i##end=__;i<i##end;++i) // [_,__)
#define Rep(i,_) for(int i=(_)-1;i>=0;--i) // [0,_)
#define REP(i,_,__) for(int i=(__)-1,i##end=_;i>=i##end;--i) // [_,__)
typedef long long ll;
typedef unsigned long long ull;
#define V vector
#define pb push_back
#define pf push_front
#define qb pop_back
#define qf pop_front
#define eb emplace_back
typedef pair<int,int> pii;
typedef pair<ll,int> pli;
#define fi first
#define se second
const int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}},inf=0x3f3f3f3f,mod=1e9+7;
const ll infl=0x3f3f3f3f3f3f3f3fll;
template<class T>inline bool ckmin(T &x,const T &y){return x>y?x=y,1:0;}
template<class T>inline bool ckmax(T &x,const T &y){return x<y?x=y,1:0;}
int init=[](){return cin.tie(nullptr)->sync_with_stdio(false),0;}();
int main(){
	int t_case=1;
//	scanf("%d",&t_case);
	while(t_case--){
		int m,n;
		scanf("%d%d",&n,&m);
		V<int>id(m+1);
		id[0]=-1;
		FOR(i,1,m+1){
			int j=m/(m/i);
			FOR(k,i,j+1)id[k]=id[i-1]+1;
			i=j;
		}
		V<int>can(id[m]+1);
		V<V<int>>mul(id[m]+1);
		FOR(i,1,m+1){
			int div=m/i,j=m/div;
			assert(id[div]==id[m/j]);
			can[id[i]]=id[div];
			mul[id[i]].resize(div+1);
			For(k,div+1){
				assert(id[i*k]==id[j*k]);
				mul[id[i]][k]=id[i*k];
			}
			i=j;
		}
		V<V<pii>>b(n);
		for(auto &i:b){
			int x;
			scanf("%d",&x);
			i.resize(x);
			for(pii &j:i)scanf("%d%d",&j.fi,&j.se);
		}
		int t;
		scanf("%d",&t);
		V<int>ans(t);
		V<pii>q(t);
		for(pii &i:q)scanf("%d%d",&i.fi,&i.se),--i.fi,--i.se;
		V<V<int>>f(n,V<int>(id[m]+1));
		function<void(int,int,const V<int>&,int)>solve=[&](int l,int r,const V<int> &a,int k){
			if(a.size()){
				if(l==r){
					int mx=0;
					for(pii &i:b[l])ckmax(mx,i.fi);
					for(int i:a)ans[i]=mx;
				}
				else{
					int mid=l+r>>1,ql=mid+1,qr=mid;
					V<int>al,_a,ar;
					for(int i:a){
						if(q[i].se<=mid)al.pb(i);
						else if(q[i].fi>mid)ar.pb(i);
						else _a.pb(i),ckmin(ql,q[i].fi),ckmax(qr,q[i].se);
					}
					solve(l,mid,al,-ql-1),solve(mid+1,r,ar,qr+1);
					for(int i:_a)For(j,id[m]+1)ckmax(ans[i],f[q[i].fi][j]+f[q[i].se][can[j]]);
				}
			}
			if(k<0){
				REP(i,-k-1,r+1){
					if(i==r){
						fill(ALL(f[i]),0);
						for(pii &j:b[i])ckmax(f[i][id[j.se]],j.fi);
					}
					else{
						f[i]=f[i+1];
						for(pii &j:b[i])For(k,can[id[j.se]]+1)ckmax(f[i][mul[k][j.se]],f[i+1][k]+j.fi);
					}
					For(j,id[m])ckmax(f[i][j+1],f[i][j]);
				}
			}
			if(k>0){
				FOR(i,l,k){
					if(i==l){
						fill(ALL(f[i]),0);
						for(pii &j:b[i])ckmax(f[i][id[j.se]],j.fi);
					}
					else{
						f[i]=f[i-1];
						for(pii &j:b[i])For(k,can[id[j.se]]+1)ckmax(f[i][mul[k][j.se]],f[i-1][k]+j.fi);
					}
					For(j,id[m])ckmax(f[i][j+1],f[i][j]);
				}
			}
		};
		V<int>tmp(t);
		iota(ALL(tmp),0);
		solve(0,n-1,tmp,0);
		for(int i:ans)printf("%d\n",i);
	}
	return 0;
}