CF601E A Museum Robbery 题解

hzoi_Shadow · 2025-01-01 16:53:41 · 题解

题目传送门

前置知识

线段树与离线询问

解法

普通的回退背包无法处理本题中的删除操作，考虑线段树分治后转化为只进行添加的背包。

具体实现时可以对每个深度开一个背包的转移数组，时间复杂度为 O(nk \log q+qk)，可以接受。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define ull unsigned long long
#define sort stable_sort 
#define endl '\n'
const ll mod=1000000007,base=10000019;
ll st[15010],ed[15010],v[30010],w[30010],f[18][1010],jc[1010],ans[30010],k;
struct SMT
{
    struct SegmentTree
    {
        vector<ll>info;
    }tree[120010];
    #define lson(rt) (rt<<1)
    #define rson(rt) (rt<<1|1)
    void update(ll rt,ll l,ll r,ll x,ll y,ll id)
    {
        if(x<=l&&r<=y)
        {
            tree[rt].info.push_back(id);
            return;
        }
        ll mid=(l+r)/2;
        if(x<=mid)
        {   
            update(lson(rt),l,mid,x,y,id);
        }
        if(y>mid)
        {
            update(rson(rt),mid+1,r,x,y,id);
        }
    }
    void solve(ll rt,ll l,ll r,ll dep)
    {
        for(ll i=1;i<=k;i++)
        {
            f[dep][i]=f[dep-1][i];
        }
        for(ll i=0;i<tree[rt].info.size();i++)
        {
            for(ll j=k;j>=w[tree[rt].info[i]];j--)
            {
                f[dep][j]=max(f[dep][j],f[dep][j-w[tree[rt].info[i]]]+v[tree[rt].info[i]]);
            }
        }
        if(l==r)
        {
            for(ll i=1;i<=k;i++)
            {
                ans[l]=(ans[l]+f[dep][i]*jc[i-1]%mod)%mod;
            }
        }
        else
        {
            ll mid=(l+r)/2;
            solve(lson(rt),l,mid,dep+1);
            solve(rson(rt),mid+1,r,dep+1);
        }
    }
}T;
int main()
{
// #define Isaac
#ifdef Isaac
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
#endif
    ll n,m,pd,x,tim=0,i;
    cin>>n>>k;
    for(i=1;i<=n;i++)
    {
        cin>>v[i]>>w[i];
        st[i]=1;
        ed[i]=-1;
    }
    cin>>m;
    for(i=1;i<=m;i++)
    {
        cin>>pd;
        if(pd==1)
        {
            n++;
            cin>>v[n]>>w[n];
            st[n]=tim+1;
            ed[n]=-1;
        }
        if(pd==2)
        {
            cin>>x;
            ed[x]=tim;
        }
        if(pd==3)
        {
            tim++;
        }
    }
    for(i=1;i<=n;i++)
    {
        ed[i]=(ed[i]==-1)?tim:ed[i];
        if(st[i]<=ed[i])
        {
            T.update(1,1,tim,st[i],ed[i],i);
        }
    }
    for(i=0;i<=k-1;i++)
    {
        jc[i]=(i==0)?1:jc[i-1]*base%mod;
    }
    T.solve(1,1,tim,1);
    for(i=1;i<=tim;i++)
    {
        cout<<ans[i]<<endl;
    }
    return 0;
}