LOJ#3034. 「JOISC 2019 Day2」两道料理
找出最大的\(y_{i}\)使得\(sumA_{i} + sumB_{y_i} \leq S_{i}\)
和最大的\(x_{j}\)使得\(sumA_{x_{j}} + sumB_{j} \leq T_{j}\)
然后我们相当于从\((0,0)\)走到\((n,m)\)一条路径，如果\(i,y_{i}\)在路径上或路径上方，那么就加上\(P_{i}\)，如果\(x_{j},j\)在路径上或路径下方，就加上\(Q_{j}\)
我们加上所有的\(P_{i}\)，然后把第一种点改成\(i - 1,y_{i} + 1\)，如果这种点在路径上或路径下面，我们会有\(-P_{i}\)的贡献，于是就变成了走一条路径使得路径下方的点值最大
我们在每次拐弯的时候加上这一列的值，最后还要加上\(sum_{n,m}\)
\(sum_{i,j}\)表示这个点在\(i,j\)下面的点的权值和，正下方
\(f_{i,j} = max(f_{i,j - 1},f_{i - 1,j}, + sum_{i - 1,j })\)
考虑用线段树维护整个dp数组，我们相当于从后往前遍历这一列的所有点，并维护前缀最大值的差分，如果它后面的正数能使加入一个负数的值被消掉就加，否则就把后面都改成0，如果是加一个正数就是直接加了
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('\n')
#define eps 1e-10
#define MAXN 1000005
#define ba 47
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
res = 0;T f = 1;char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 +c - '0';
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {x = -x;putchar('-');}
if(x >= 10) {
out(x / 10);
}
putchar('0' + x % 10);
}
int N,M;
int64 sa[MAXN],sb[MAXN],a[MAXN],b[MAXN],p[MAXN],q[MAXN],s[MAXN],t[MAXN],ans;
vector<pair<int,int64> > v[MAXN];
struct node {
int l,r;int64 sum;bool cov;
}tr[MAXN * 4];
void cover(int u) {
tr[u].sum = 0;tr[u].cov = 1;
}
void update(int u) {
tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
void pushdown(int u) {
if(tr[u].cov) {
cover(u << 1);
cover(u << 1 | 1);
tr[u].cov = 0;
}
}
void build(int u,int l,int r) {
tr[u].l = l;tr[u].r = r;tr[u].sum = 0;tr[u].cov = 0;
if(l == r) return;
int mid = (l + r) >> 1;
build(u << 1,l,mid);
build(u << 1 | 1,mid + 1,r);
}
void Cover(int u,int l,int r) {
if(tr[u].l == l && tr[u].r == r) {cover(u);return;}
int mid = (tr[u].l + tr[u].r) >> 1;
pushdown(u);
if(r <= mid) Cover(u << 1,l,r);
else if(l > mid) Cover(u << 1 | 1,l,r);
else {Cover(u << 1,l,mid);Cover(u << 1 | 1,mid + 1,r);}
update(u);
}
int64 Query(int u,int l,int r) {
if(tr[u].l == l && tr[u].r == r) {
return tr[u].sum;
}
int mid = (tr[u].l + tr[u].r) >> 1;
pushdown(u);
if(r <= mid) return Query(u << 1,l,r);
else if(l > mid) return Query(u << 1 | 1,l,r);
else return Query(u << 1,l,mid) + Query(u << 1 | 1,mid + 1,r);
}
void Add(int u,int pos,int64 v) {
if(tr[u].l == tr[u].r) {tr[u].sum += v;return;}
int mid = (tr[u].l + tr[u].r) >> 1;
pushdown(u);
if(pos <= mid) Add(u << 1,pos,v);
else Add(u << 1 | 1,pos,v);
update(u);
}
int64 Change(int u,int l,int r,int64 v) {
if(tr[u].l == l && tr[u].r == r) {
if(tr[u].sum <= v) {
int x = tr[u].sum;
cover(u);
return x;
}
if(tr[u].l == tr[u].r) {tr[u].sum -= v;return v;}
else {
pushdown(u);
int mid = (tr[u].l + tr[u].r) >> 1;
int64 t = Change(u << 1,l,mid,v);
if(v - t) t += Change(u << 1 | 1,mid + 1,r,v - t);
update(u);
return t;
}
}
pushdown(u);
int mid = (tr[u].l + tr[u].r) >> 1;
if(r <= mid) {
int64 x = Change(u << 1,l,r,v);
update(u);return x;
}
else if(l > mid) {
int64 x = Change(u << 1 | 1,l,r,v);
update(u);return x;
}
else {
int64 x = Change(u << 1,l,mid,v);
if(v - x) x += Change(u << 1 | 1,mid + 1,r,v - x);
update(u);return x;
}
}
void Process(int pos,int64 v) {
if(pos > M) return;
if(v >= 0) Add(1,pos,v);
else {
int64 x = Query(1,pos,M);
if(v + x <= 0) Cover(1,pos,M);
else Change(1,pos,M,-v);
}
}
void Solve() {
read(N);read(M);
for(int i = 1 ; i <= N ; ++i) {
read(a[i]);read(s[i]);read(p[i]);
sa[i] = sa[i - 1] + a[i];
}
for(int i = 1 ; i <= M ; ++i) {
read(b[i]);read(t[i]);read(q[i]);
sb[i] = sb[i - 1] + b[i];
}
for(int i = 1 ; i <= N ; ++i) {
int y = upper_bound(sb + 1,sb + M + 1,s[i] - sa[i]) - sb - 1;
if(sa[i] <= s[i]) {
if(y + 1 <= M) v[i - 1].pb(mp(y + 1,-p[i]));
//out(i - 1);space;out(y + 1);enter;
ans += p[i];
}
}
for(int i = 1 ; i <= M ; ++i) {
int x = upper_bound(sa + 1,sa + N + 1,t[i] - sb[i]) - sa - 1;
if(sb[i] <= t[i]) {
v[x].pb(mp(i,q[i]));
//out(x);space;out(i);enter;
}
}
build(1,0,M);
for(int i = 0 ; i < N ; ++i) {
sort(v[i].begin(),v[i].end(),[](pair<int,int64> a,pair<int,int64> b) {return a.fi > b.fi;});
int pre = M + 1;int64 val = 0;
for(auto t : v[i]) {
if(t.fi != pre) {
Process(pre,val);
pre = t.fi;val = 0;
}
val += t.se;
}
Process(pre,val);
}
ans += tr[1].sum;
for(auto t : v[N]) ans += t.se;
out(ans);enter;
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Solve();
}