题解：P15609 [ICPC 2021 Jakarta R] Greedy Knapsack

· · 题解

这里给一个能在洛谷和 qoj 通过的假做法，有兴趣可以卡。

考虑每个物品实际上是一个函数复合，直接平衡树有交合并硬维护即可，虽然是假的但是跑的飞快。

具体就是每次先把 w-1 的点求出来，然后后面部分拉出来，下标整体 -w 权值整体 +v，然后和前面部分有交合并，要把相同下标的缩成一个。

:::success[点击查看参考代码]

#include<bits/stdc++.h>
#define TIME chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count()
#define rep(i,l,r) for(int qwp=(r),i=(l);i<=qwp;i++)
#define per(i,r,l) for(int qwp=(l),i=(r);i>=qwp;i--)
using namespace std;
namespace ax_by_c{
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> pii;
constexpr ll llinf=3e18;
constexpr int N=1e5+5;
inline ll frll(){ll n=0;char c=getchar();while(c<'0'||'9'<c)c=getchar();while('0'<=c&&c<='9')n=n*10+c-48,c=getchar();return n;}
void wrll(ll x){if(x>9)wrll(x/10);putchar(x%10+48);}
mt19937_64 rng(TIME);
struct DS1{
    struct node{int ls,rs;ll p,v,mxv,pz,vz;ull pri;}tr[N];
    int idx,rt;
    inline void Init(){idx=rt=0,tr[0].mxv=-llinf;}
    inline int newnd(ll p,ll v){tr[++idx]={0,0,p,v,v,0,0,rng()};return idx;}
    inline void pu(int u){tr[u].mxv=max({tr[tr[u].ls].mxv,tr[tr[u].rs].mxv,tr[u].v});}
    inline void pd_pz(int u,ll pz){tr[u].p+=pz,tr[u].pz+=pz;}
    inline void pd_vz(int u,ll vz){tr[u].v+=vz,tr[u].mxv+=vz,tr[u].vz+=vz;}
    inline void pd(int u){
        if(tr[u].pz)pd_pz(tr[u].ls,tr[u].pz),pd_pz(tr[u].rs,tr[u].pz),tr[u].pz=0;
        if(tr[u].vz)pd_vz(tr[u].ls,tr[u].vz),pd_vz(tr[u].rs,tr[u].vz),tr[u].vz=0;
    }
    pii spl(int u,ll p){
        if(!u)return {0,0};pd(u);
        if(tr[u].p<=p){pii t=spl(tr[u].rs,p);tr[u].rs=t.first,pu(u);return {u,t.second};}
        else{pii t=spl(tr[u].ls,p);tr[u].ls=t.second,pu(u);return {t.first,u};}
    }
    int meg(int x,int y){
        if(!x||!y)return x|y;pd(x),pd(y);
        if(tr[x].pri<tr[y].pri){tr[x].rs=meg(tr[x].rs,y);pu(x);return x;}
        else{tr[y].ls=meg(x,tr[y].ls),pu(y);return y;}
    }
    int MEG(int x,int y){
        if(!x||!y)return x|y;pd(x),pd(y);if(tr[x].pri>tr[y].pri)swap(x,y);
        if(tr[x].p==tr[y].p){tr[x].v=max(tr[x].v,tr[y].v),tr[x].ls=MEG(tr[x].ls,tr[y].ls),tr[x].rs=MEG(tr[x].rs,tr[y].rs),pu(x);return x;}
        pii t=spl(y,tr[x].p);tr[x].ls=MEG(tr[x].ls,t.first),tr[x].rs=MEG(tr[x].rs,t.second);pu(x);return x;
    }
    inline void ins(ll p,ll v){pii t=spl(rt,p-1);rt=meg(t.first,meg(newnd(p,v),t.second));}
    inline void ass(ll p){pii t=spl(rt,p-1);if(t.second)t.second=meg(newnd(p,tr[t.second].mxv),t.second);rt=meg(t.first,t.second);}
    ll dfs(int u){if(!u)return 0;pd(u);return max({dfs(tr[u].ls),tr[u].v,dfs(tr[u].rs)});}
}tr;
int n;ll m,w[N],v[N];
void slv(){
    n=frll(),m=frll();rep(i,1,n)w[i]=frll();rep(i,1,n)v[i]=frll();
    tr.Init(),tr.ins(m,0);
    rep(i,1,n){
        tr.ass(w[i]-1);pii t=tr.spl(tr.rt,w[i]-1);
        tr.pd_pz(t.second,-w[i]),tr.pd_vz(t.second,v[i]),tr.rt=tr.MEG(t.first,t.second);
    }
    wrll(tr.dfs(tr.rt)),putchar('\n');
}
void main(){
    int T=1;// T=frll();
    while(T--)slv();
}
}
int main(){
    auto _Tbe=TIME;
    // freopen("shopping.in","r",stdin);
    // freopen("shopping.out","w",stdout);
    ax_by_c::main();
    auto _Ted=TIME;
    cerr<<"\nTIME:"<<_Ted-_Tbe<<'\n';
    return 0;
}
/*
ulimit -s 524288
g++ -O2 -std=c++14 -static shopping.cpp -o shopping.exe
g++ -O2 -std=c++14 -fsanitize=address,leak,undefined shopping.cpp -o shopping.exe
./shopping.exe
*/

:::