题解 P9818 游戏王

meyi · 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;
}