https://pintia.cn/problem-sets/994805046380707840/exam/problems/994805047638999040
大意是在一条直线上,有N个从0..N-1编号的城市,每个城市之间的道路有最大负载ai,现在有M张从i城到j城的运货订单,假设每个城市的货物无限,问在某一时刻,如何安排订单的运输，能使得运输的货物重量最大且符合道路的限制？
分析：开始想到的是按照区间长度依次操作 因为小区间对别的区间的影响可能性要小一些 但是这样做是错误的 就算影响小一些 但是仍然可能有
正确的做法是 按照第一关键字右端点从小到大 第二关键字左端点从大到小排序
为什么？
首先,这是一个区间调度问题,性质如同问:有许多项工作,每个工作有起始结束时间,目标是尽可能多的选择工作,问最多可参与几项工作? 工作结束得越早,那么之后可选择的工作自然越多. 这道题是一样的,货物的终点站越靠左,那么留出了越多道路给后面的订单. 这里是贪心的思想.
然后就线段树区间修改区间最小值即可
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
typedef struct node{
int l, r;
ll minn, f;
bool operator < (const node x) const {
if(x.r != r)
return x.r > r;
else
return x.l < l;
}
}node;
node tree[maxn<<2];
node ans[maxn];
ll minn;
void down(int k){
if(tree[k].f){
tree[k<<1].f += tree[k].f;
tree[k<<1|1].f += tree[k].f;
tree[k<<1].minn -= tree[k].f;
tree[k<<1|1].minn -= tree[k].f;
tree[k].f = 0;
}
}
void build(int k, int l, int r){
tree[k].l = l, tree[k].r = r;
if(l == r){
scanf("%lld", &tree[k].minn);
return;
}
int mid = (l+r)>>1;
build(k<<1, l, mid);
build(k<<1|1, mid+1, r);
tree[k].minn = min(tree[k<<1].minn, tree[k<<1|1].minn);
}
void query(int k, int l, int r, int cl, int cr){
if(l >= cl && r <= cr){
minn = min(minn, tree[k].minn);
return;
}
down(k);
int mid = (l+r)>>1;
if(cl <= mid) query(k<<1, l, mid, cl, cr);
if(cr > mid) query(k<<1|1, mid+1, r, cl ,cr);
}
void swap(int &x, int &y){
int t = x; x = y; y = t;
}
void updata(int k, int l, int r, int cl, int cr, ll c){
if(l >= cl && r <= cr){
tree[k].f += c;
tree[k].minn -= c;
return;
}
down(k);
int mid = (l+r)>>1;
if(cl <= mid) updata(k<<1, l, mid, cl, cr, c);
if(cr > mid) updata(k<<1|1, mid+1, r, cl, cr, c);
tree[k].minn = min(tree[k<<1].minn, tree[k<<1|1].minn);
}
int n, q;
int main(){
int a, b;
scanf("%d %d", &n, &q);
build(1, 1, n-1);
for(int i = 0; i < q; ++ i){
scanf("%d %d", &a, &b);
if(a > b) swap(a, b);
ans[i].l = a+1;
ans[i].r = b;
}
sort(ans, ans+q);
ll sum = 0;
for(int i = 0; i < q; ++ i){
minn = 1e18;
query(1, 1, n-1, ans[i].l, ans[i].r);
sum += minn;
updata(1, 1, n-1, ans[i].l, ans[i].r, minn);
}
printf("%lld\n", sum);
return 0;
}