题解：AT_joisc2019_e ふたつの料理 (Two Dishes)

· · 题解

Solution

令 a_x 和 b_x 分别为 A 和 B 中完成第 x 个步骤需要的时间，s_x 和 t_x 为限制的时间，p_x 和 q_x 为代价。

考虑这样一个暴力 DP：设 f_{x,y} 表示 A 做了前 x 个步骤，B 做了前 y 个步骤的答案最大是多少。

先对 a 和 b 做一下前缀和，转移就是 f_{x,y}=\max(f_{x-1,y}+[a_x+b_y\le s_x]p_x,f_{x,y-1}+[a_x+b_y\le s_y]q_y)。然后考虑以 x 为阶段，考虑 f 数组的变化。

具体来讲就是每次先转移 y（就是把 x-1 到 x 间的 \text{B} 步骤加进去），再完成 A 中 x 这个步骤。对于完成 A 中 x 这个步骤，就相当于进行一次后缀加，对于 y 的转移，对于每个合法的 x 都进行操作显然是不好做的，我们考虑转化为前面那种形式，我们先求出 a 中第一个大于 t_y-b_y 的位置 x，限制就等价于如果制作 x 前已经制作了 y，那么就会加上这个代价，我们把这个东西挂到 x 上。现在每次转移 y 就相当于进行前缀 max，转移 x 就是进行这些后缀加操作。

然后考虑如果每次进行一次后缀加然后立刻进行前缀 max 怎么做，我们可以用一个 set 维护所有差分不为 0 的位置，然后对于一次操作 (val,pos) 就不断找到 pos 后面第一个差分大于 0 的位置，判断这个位置减去 val 后是否大于前面的值（就是加上 val 后差分是否大于 0），如果大于就直接加上然后退出，否则这个值就应该变为前面的值（此时差分等于 0，就直接把这个位置删掉），然后再把 val 加上这个位置差分的值（因为删掉这个位置后，后面位置的实际值应该是差分的前缀和再加上这个位置的差分值）。

对于相邻两次前缀 max 间有多次后缀加的情况，我们只需要先加正数再加负数即可。然后因为操作总数不超过 n+m，所以插入总数也不超过 n+m，因此这个做法的时间复杂度是均摊 O((n+m)\log n)。

Code

//when you use vector or deque,pay attention to the size of it.
//by OldDirverTree
#include<bits/stdc++.h>
//#include<atcoder/all>
#define P pair<int,int>
#define int long long
#define mid (l+r>>1)
using namespace std;
//using namespace atcoder;
//using mint=modint998244353;
const int N=1e6+1;
vector<P> C[N]; map<int,int> f;
int n,m,ans,a[N],b[N],s[N],t[N],p[N],q[N];

struct custom_hash
{
    static uint64_t splitmix64(uint64_t x) {
        x+=0x9e3779b97f4a7c15;
        x=(x^(x>>30) )*0xbf58476d1ce4e5b9;
        x=(x^(x>>27) )*0x94d049bb133111eb;
        return x^(x>>31);
    }
    size_t operator() (uint64_t x) const {
        static const uint64_t FIXED_RANDOM=chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x+FIXED_RANDOM);
    }
};
int read() {
    int x=0; bool _=true; char c=0;
    while (!isdigit(c) ) _&=(c!='-'),c=getchar();
    while (isdigit(c) ) x=x*10+(c&15),c=getchar();
    return _?x:-x;
}
main()
{
    n=read(),m=read();
    for (int i=1;i<=n;i++) a[i]=a[i-1]+read(),s[i]=read(),p[i]=read();
    for (int i=1;i<=m;i++) b[i]=b[i-1]+read(),t[i]=read(),q[i]=read();
    for (int i=1;i<=n;i++) if (s[i]>=a[i]) {
        int pos=upper_bound(b+1,b+m+1,s[i]-a[i])-b;
        if (pos<=m) C[i].push_back({-p[i],pos}); ans+=p[i];
    }
    for (int i=1;i<=m;i++) if (t[i]>=b[i]) {
        int pos=upper_bound(a+1,a+n+1,t[i]-b[i])-a;
        if (pos<=n) C[pos].push_back({q[i],i}); else ans+=q[i];
    }
    for (int i=1;i<=n;i++)
    {
        for (auto [val,pos]:C[i]) if (val>0) f[pos]+=val;
        for (auto [val,pos]:C[i]) if (val<0) {
            for (auto it=f.lower_bound(pos);val<=0&&it!=f.end();it=f.erase(it) )
            pos=it->first,val+=it->second; if (val>0) f[pos]+=val;
        }
    }
    for (auto [x,y]:f) ans+=y;
    return !printf("%lld",ans);
}