JOISC2019 ふたつの料理 / Two Dishes / 两道料理

好题！

考虑一个暴力 DP：\(f(i,j)\) 表示前 \(i\) 个 \(A\)，前 \(j\) 个 \(B\)，最大价值。将 \(a,b\) 前缀和。令 \(A_i=S_i-a_i\)，\(B_j\) 同理，那么式子化成 \(f(i,j)=\max \{f(i-1,j)+[b_j\le A_i],f(i,j-1)+[a_i\le B_j]\}\)。我们考虑记录 \(p_i=\max_j s.t. b_j\le A_i\)，\(q_i\) 同理。钦定 \(j +\) 为右，\(i+\) 为下，即我们考虑向右走一步时，只有在 \((i,p_i)\) 之下时才会有贡献；考虑向下走一步时，只有在 \((q_j,j)\) 之上时才会右贡献。我们把所有 \(p\) 的贡献先加上然后取反，这样就能变成只有在点上面才能有贡献了。我们相当于就是要最大化路径覆盖的点之和。即假设我们的路径可以用一些 \((i,s_i)\) 表示，那么 \((x_u,y_u)\) （\((x_u,y_u)=(i-1,p_i+1)\) 或 \((q_i,i)\)）产生贡献当且仅当 \(s_{x_u}\ge y_u\)。也就是说我们 \(i+1\) 的时候，会加上目前的点的左侧的贡献，即设 \(t_{i,j}\) 表示 \((i,[1,j])\) 的点的贡献和，那么稍微修改一下 \(f\) 的定义，使 \(f\) 不记录当前行的点的贡献，于是 \(f_{i,j}=\max \{f_{i,j-1},f_{i-1,j}+t_{i-1,j}\}\)。我们把 \(f_{i,j-1}\) 展开来，可以得到 \(f_{i,j}=\max_{k\le j} \{f_{i-1,k}+t_{i-1,k}\}\)，相当于每一个 \((i-1,*)\) 的贡献点都会让一个后缀加，然后我们最后再给 \(f_i\) 做一次前缀 max 操作。我们考虑 \(f\) 的差分数组 \(g\)，那么 \((i-1,j)\) 的贡献点的贡献为使 \(g_j\) 加上一个值，做前缀 max 操作相当于从右往左扫，然后遇到负数就和后面的正数去干成零。于是我们需要维护一个支持单点修改和区间赋 \(0\) 的线段树。

当然实际上可以均摊复杂度然后直接用一个 set 维护，属于是数据结构做傻了。

#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define fi first
#define se second
#define eb emplace_back
#define popc __builtin_popcount
#define sgn(x) ((x)&1?-1:1)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vp;
typedef unsigned long long ull;
typedef long double ld;

int read() {
    int x=0,w=1; char c=getchar(); 
    while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
    while(isdigit(c)) {x=x*10+c-'0'; c=getchar();}
    return x*w;
}

const int N=1e6+9;
int n,m,a[N],b[N],s[N],t[N],p[N],q[N],A[N],B[N],P[N],Q[N],sum;
vp g[N];

namespace SegT {
    int ls[N<<1],rs[N<<1],tag[N<<1],s[N<<1],tot=1;
    void build(int p,int l,int r) {
        if(l==r) return; int mid=l+r>>1;
        build(ls[p]=++tot,l,mid), build(rs[p]=++tot,mid+1,r);
    }
    void psd(int p) {
        tag[ls[p]]=tag[rs[p]]=1, s[ls[p]]=s[rs[p]]=0, tag[p]=0;
    }
    void add(int p,int l,int r,int x,int y) {
        //if(p==1) cout<<"ADD "<<x<<" "<<y<<endl;
        if(l==r) {s[p]+=y; return;} int mid=l+r>>1; if(tag[p]) psd(p);
        if(x<=mid) add(ls[p],l,mid,x,y); else add(rs[p],mid+1,r,x,y);
        s[p]=s[ls[p]]+s[rs[p]];
    }
    void mdf(int p,int l,int r,int x,int y) {
        //if(p==1) cout<<"MDF "<<x<<" "<<y<<endl;
        if(l==r) {s[p]=y; return;} int mid=l+r>>1; if(tag[p]) psd(p);
        if(x<=mid) add(ls[p],l,mid,x,y); else add(rs[p],mid+1,r,x,y);
        s[p]=s[ls[p]]+s[rs[p]];
    }
    void cov(int p,int l,int r,int x,int y) {
        //if(p==1) cout<<"COV "<<x<<" "<<y<<endl;
        if(l==x&&r==y) {tag[p]=1, s[p]=0; return;}
        int mid=l+r>>1; if(tag[p]) psd(p);
        if(y<=mid) cov(ls[p],l,mid,x,y);
        else if(x>mid) cov(rs[p],mid+1,r,x,y);
        else cov(ls[p],l,mid,x,mid), cov(rs[p],mid+1,r,mid+1,y);
        s[p]=s[ls[p]]+s[rs[p]];
    }
    int qry(int p,int l,int r,int x,int y) {
        if(l==x&&r==y) return s[p];
        int mid=l+r>>1; if(tag[p]) psd(p);
        if(y<=mid) return qry(ls[p],l,mid,x,y);
        else if(x>mid) return qry(rs[p],mid+1,r,x,y);
        else return qry(ls[p],l,mid,x,mid)+qry(rs[p],mid+1,r,mid+1,y);
    }
    pii qpos(int p,int l,int r,int x,int k) {
        if(l==r) return pii(l,s[p]);
        if(l==x&&s[p]<=k) return pii(r,s[p]);
        int mid=l+r>>1; if(tag[p]) psd(p);
        if(x>mid) return qpos(rs[p],mid+1,r,x,k);
        else {
            pii r1=SegT::qpos(ls[p],l,mid,x,k);
            if(r1.se>=k) return r1;
            else {
                pii r2=SegT::qpos(rs[p],mid+1,r,mid+1,k-r1.se);
                return pii(r2.fi,r1.se+r2.se);
            }
        }
    }
}

signed main() {
    //freopen("QOJ66.in","r",stdin);
    n=read(), m=read();
    rep(i,1,n) a[i]=a[i-1]+read(), s[i]=read(), p[i]=-read(), sum-=p[i];
    rep(i,1,m) b[i]=b[i-1]+read(), t[i]=read(), q[i]=read();
    rep(i,1,n) A[i]=s[i]-a[i];
    rep(i,1,m) B[i]=t[i]-b[i];
    rep(i,1,n) P[i]=upper_bound(b,b+m+1,A[i])-b-1;
    rep(i,1,m) Q[i]=upper_bound(a,a+n+1,B[i])-a-1;
    rep(i,1,n) if(P[i]+1<=m) g[i-1].eb(pii(P[i]+1,p[i]));
    rep(i,1,m) if(Q[i]==n) sum+=q[i]; else if(Q[i]>=0) g[Q[i]].eb(pii(i,q[i]));
    rep(i,0,n) sort(g[i].begin(),g[i].end());
    SegT::build(1,0,m);
    rep(i,1,n) {
        int sz=g[i-1].size(),gg=0;
        per(j,sz-1,0) {
            gg+=g[i-1][j].se;
            if(j==0||g[i-1][j].fi!=g[i-1][j-1].fi) {
                int x=g[i-1][j].fi;
                if(x==0||gg>0) SegT::add(1,0,m,x,gg);
                else {
                    pii p=SegT::qpos(1,0,m,x,-gg);
                    int d=max(0ll,p.se+gg);
                    SegT::cov(1,0,m,x,p.fi);
                    SegT::mdf(1,0,m,p.fi,d);
                }
                gg=0;
            }
        }
    }
    int res=SegT::qry(1,0,m,0,m);
    sum+=res;
    printf("%lld\n",sum);
    return 0;
}