题解 「JOISC 2019 Day2」两道料理

· · 题解

题目大意

两道料理分别要 n,m 个操作。做菜需要按顺序。第一道菜第 i 个步骤用时 a_i，如果在第 s_i 前完成得分 p_i；第二道菜第 i 个步骤用时 b_i，如果在第 t_i 前完成得分 q_i。

最大化评分。

保证 1 \le n,m, \le 10^6,1\le a_i,b_j \le 10^9,1 \le s_i,t_i \le 10^{15},|p_i|,|q_i| \le 10^9。

题解

不妨设 f(x,y) 表示第一道菜到步骤 x，第二道菜到步骤 y 的最大评分。转移都是枚举上一个位置，类似走放方格。相当于就是从 (0,0) 走到 (n,m) 的最大评分。

于是考虑把评分看成点，点 (i,s_i) 有收益当且仅当他在路径上方，(j,t_j) 在路径下方。因为不在一个边很烦，所以将答案先加上 \sum p_i，然后将点 (i,s_i) 的权值 a_{i,s_i} 设为 -p_i。

预处理个前缀和，设 s_{i,j} = \sum\limits_{x=0}^y a_{i,x}。所以有转移：

f(i,j) = \max\{ f(i,j-1) , f(i-1,j) + s_{i-1,j} \}

对一行转移分析。考虑下 f(x) 的性质，显然 f(x) 是单调的，它相当于将 f(x-1) 值加上 s(x-1) 然后取前缀最大值。

所以我们差分一下 f(x)，得到的差分数组 d(i) 一定非负。

如果我们对 d(i) 加上一个正数，那么有影响只有位置 i。

如果加上一个负数 x，若 d(i) 变成 <0，则会变成 0。接着会影响后面值。可以发现，他会是后面连续一段总和最多为 -x 的数都变成 0，所以可以用线段树二分维护。

复杂度是 \mathcal{O}((n+m) \log m)。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll N=1e6+5;
const ll inf=1e18;
struct node{
    ll x,y;
    friend bool operator < (node u,node v){
        return (u.x==v.x)?(u.y<v.y):(u.x>v.x);
    }
};
ll n,m,ans,a[N],s[N],p[N],b[N],r[N],q[N];
vector<node> vc[N];
struct tree{
    ll sum[N<<2],tag[N<<2];
    void pushup(ll k){
        sum[k]=sum[k<<1]+sum[k<<1|1];
    }
    void pushdown(ll k)
    {   if(!tag[k])return;
        sum[k<<1]=sum[k<<1|1]=0,tag[k<<1]=tag[k<<1|1]=1;
        tag[k]=0;
    }
    void modify(ll k,ll l,ll r,ll x,ll y)
    {   if(l==r){sum[k]+=y;return;}
        pushdown(k);
        ll mid=(l+r)>>1;
        if(x<=mid)modify(k<<1,l,mid,x,y);
        else modify(k<<1|1,mid+1,r,x,y);
        pushup(k);
    }
    void reset(ll k,ll l,ll r,ll x,ll y)
    {   if(x>y||l>y||r<x)return;
        if(x<=l&&r<=y){sum[k]=0,tag[k]=1;return;}
        pushdown(k);
        ll mid=(l+r)>>1;
        if(x<=mid)reset(k<<1,l,mid,x,y);
        if(y>mid)reset(k<<1|1,mid+1,r,x,y);
        pushup(k);
    }
    ll query(ll k,ll l,ll r,ll x,ll y)
    {   if(x>y||l>y||r<x)return 0;
        if(x<=l&&r<=y)return sum[k];
        pushdown(k);
        ll mid=(l+r)>>1;
        if(y<=mid)return query(k<<1,l,mid,x,y);
        if(x>mid)return query(k<<1|1,mid+1,r,x,y);
        return query(k<<1,l,mid,x,y)+query(k<<1|1,mid+1,r,x,y);
    }
    ll solve(ll k,ll l,ll r,ll x,ll y,ll pr,ll v)
    {   ll mid=(l+r)>>1,res=inf;
        if(x<=l&&r<=y)
        {   if(l==r)
            {   if(pr+sum[k]>=v)return l;
                return inf;
            }
            pushdown(k);
            if(sum[k<<1]+pr>=v)return solve(k<<1,l,mid,x,y,pr,v);
            else return solve(k<<1|1,mid+1,r,x,y,pr+sum[k<<1],v);
        }
        pushdown(k);
        if(x<=mid)res=min(res,solve(k<<1,l,mid,x,y,pr,v));
        if(y>mid)res=min(res,solve(k<<1|1,mid+1,r,x,y,pr+query(k<<1,l,mid,x,y),v));
        return res;
    }
}T;
int main()
{   //freopen("data.in", "r", stdin);
    scanf("%lld%lld",&n,&m);
    for(ll i=1;i<=n;i++)
    {   scanf("%lld%lld%lld",&a[i],&s[i],&p[i]);
        a[i]+=a[i-1],s[i]=s[i]-a[i];
    }
    for(ll i=1;i<=m;i++)
    {   scanf("%lld%lld%lld",&b[i],&r[i],&q[i]);
        b[i]+=b[i-1],r[i]=r[i]-b[i];
    }
    for(ll i=1;i<=n;i++)
    {   if(s[i]<0)continue;
        ll pos=upper_bound(b+1,b+1+m,s[i])-b;
        if(pos<=m)vc[i-1].push_back((node){-p[i],pos});
        ans+=p[i];
    }
    for(ll i=1;i<=m;i++)
    {   if(r[i]<0)continue;
        ll pos=upper_bound(a+1,a+1+n,r[i])-a;
        vc[pos-1].push_back((node){q[i],i});
    }
    for(ll i=0;i<n;i++)
    {   sort(vc[i].begin(),vc[i].end());
        for(ll j=0;j<(int)vc[i].size();j++)
        {   node v=vc[i][j];
            if(v.x>=0)T.modify(1,0,m,v.y,v.x);
            else{
                ll x=T.solve(1,0,m,v.y,m,0,-v.x);
                if(x==inf)T.reset(1,0,m,v.y,m);
                else T.modify(1,0,m,x,v.x+T.query(1,0,m,v.y,x-1)),T.reset(1,0,m,v.y,x-1);
            }
        }
    }
    ans+=T.sum[1];
    for(ll i=0;i<(int)vc[n].size();i++)ans+=vc[n][i].x;
    printf("%lld\n",ans);
    return 0;
}