A30294. 森森快递
题目描述
森森快递
题目描述
森森开了一家快递公司，叫森森快递。因为公司刚刚开张，所以业务路线很简单，可以认为是一条直线上的 N 个城市，这些城市从左到右依次从 0 到(N-1 )编号。由于道路限制，第 i 号城市（i=0, … , N-2） 与第( i+1 )号城市中间往返的运输货物重量在同一时刻不能超过 Ci 公斤。
公司开张后很快接到了 Q 张订单，其中 j 张订单描述了某些指定的货物要从 Sj 号城市运输到 Tj号城市。这里我们简单地假设所有货物都有无限货源，森森会不定时地挑选其中一部分货物进行运输。安全起见，这些货物不会在中途卸货。
为了让公司整体效益更佳，森森想知道如何安排订单的运输，能使得运输的货物重量最大且符合道路的限制？ 要注意的是，发货时间有可能是任何时刻，所以我们安排订单的时候，必须保证共用同一条道路的所有货车的总重量不超载。例如我们安排 1 号城市到 4 号城市以及 2 号城市到 4 号城市两张订单的运输，则这两张订单的运输同时受 2-3 以及 3-4 两条道路的限制，因为两张订单的货物可能会同时在这些道路上运输。
时间限制： 5000 内存限制： 262144
输入
输入在第一行给出两个正整数 N 和 Q（2 ≤ N ≤ 1 0 5 , 1 ≤ Q ≤ 1 0 5 ） ，表示总共的城市数
以及订单数量。第二行给出(N-1 )个数，顺次表示相邻两城市间的道路允许的最大运货重量 C i （i=0, … , N-2） 。题目保证每个 Ci是不超过 231 的非负整数。接下来 Q 行，每行给出一张订单的起始及终止运输城市编号。题目 保证所有编号合法，并且不存在起点和终点重合的情况。
输出
在一行中输出可运输货物的最大重量。
样例输入
10 6
0 7 8 5 2 3 1 9 10
0 9
1 8
2 7
6 3
4 5
4 2
样例输出
7
提示
样例提示： 我们选择执行最后两张订单，即把 5 公斤货从城市 4 运到城市 2，并且把 2 公斤货从城市 4 运到城市 5，就可以得到最大运输量 7 公斤。
参考答案
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define x first
#define y second
struct node{
int l,r;
ll mn,lazy;
}tr[100010*4];
int n,q,arr[100010];
vector<pii> Q;
bool cmp(pii a,pii b)
{
return a.y!=b.y?a.y<b.y:a.x<b.x;
}
void pushup(int u)
{
tr[u].mn=min(tr[u<<1].mn,tr[u<<1|1].mn);
}
void pushdown(int u)
{
tr[u<<1].lazy+=tr[u].lazy,tr[u<<1|1].lazy+=tr[u].lazy;
tr[u<<1].mn+=tr[u].lazy,tr[u<<1|1].mn+=tr[u].lazy;
tr[u].lazy=0;
}
void build(int u,int l,int r)
{
tr[u].l=l,tr[u].r=r;
if(l==r) {
tr[u].mn=arr[l];
} else {
int mid=l+r>>1;
build(u<<1,l,mid),build(u<<1|1,mid+1,r);
pushup(u);
}
}
ll query(int u,int l,int r)
{
if(tr[u].l>=l&&tr[u].r<=r) return tr[u].mn;
int mid=tr[u].l+tr[u].r>>1;
ll res=1e18;
pushdown(u);
if(l<=mid) res=query(u<<1,l,r);
if(r>mid) res=min(res,query(u<<1|1,l,r));
return res;
}
void modify(int u,ll add,int l,int r)
{
if(tr[u].l>=l&&tr[u].r<=r) {
tr[u].mn+=add;
tr[u].lazy+=add;
} else {
pushdown(u);
int mid=tr[u].l+tr[u].r>>1;
if(l<=mid) modify(u<<1,add,l,r);
if(r>mid) modify(u<<1|1,add,l,r);
pushup(u);
}
}
int main()
{
ios::sync_with_stdio(false),cin.tie(0);
cin>>n>>q;
for(int i=1;i<n;i++) cin>>arr[i];
while(q--) {
int a,b;
cin>>a>>b;
if(a>b) swap(a,b);
Q.push_back({a,b});
}
sort(Q.begin(),Q.end(),cmp);
build(1,1,n-1);
ll ans=0;
for(auto [a,b]:Q) {
ll res=query(1,a+1,b);
if(res>0) {
ans+=res;
modify(1,-res,a+1,b);
}
}
cout<<ans<<'\n';
return 0;
}