【CCCC】L3-017 森森快递 (30分)，线段树rmq模板+贪心排序

problem

L3-017 森森快递 (30分)
森森开了一家快递公司，叫森森快递。因为公司刚刚开张，所以业务路线很简单，可以认为是一条直线上的N个城市，这些城市从左到右依次从0到(N−1)编号。由于道路限制，第i号城市（i=0,⋯,N−2）与第(i+1)号城市中间往返的运输货物重量在同一时刻不能超过C
​i
​​ 公斤。

公司开张后很快接到了Q张订单，其中j张订单描述了某些指定的货物要从S
​j
​​ 号城市运输到T
​j
​​ 号城市。这里我们简单地假设所有货物都有无限货源，森森会不定时地挑选其中一部分货物进行运输。安全起见，这些货物不会在中途卸货。

为了让公司整体效益更佳，森森想知道如何安排订单的运输，能使得运输的货物重量最大且符合道路的限制？要注意的是，发货时间有可能是任何时刻，所以我们安排订单的时候，必须保证共用同一条道路的所有货车的总重量不超载。例如我们安排1号城市到4号城市以及2号城市到4号城市两张订单的运输，则这两张订单的运输同时受2-3以及3-4两条道路的限制，因为两张订单的货物可能会同时在这些道路上运输。

输入格式：
输入在第一行给出两个正整数N和Q（2≤N≤10
​5
​​ , 1≤Q≤10
​5
​​ ），表示总共的城市数以及订单数量。

第二行给出(N−1)个数，顺次表示相邻两城市间的道路允许的最大运货重量C
​i
​​ （i=0,⋯,N−2）。题目保证每个C
​i
​​ 是不超过2
​31
​​ 的非负整数。

接下来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公斤。

• 一条直线上n个点，相邻两点间运货数不超过ci
• 对于q张从点a到点b的订单，求最大运货重量。
• n,q<1e5

solution

【搜索】

• 对于每张订单，最大重量为订单经过路线的最小ci值。
• 从q张中选取任意张，每次判断是否冲突即可搜索.
• 复杂度O（n*2^q）,因为n,q都是1e5,显然会超时，考虑其他做法。

【贪心+RMQ线段树】

• 题目模型：把直线看做是序列，所有(a,b)可以看做是一个个区间，区间（a,b）最大运货量，为所有小区间（载货量ci）取最小。选中一个区间（订单q）后，区间内每一段都减去这个最小值（无法再运输这些），我们求能运输的最大量（即减去值总和的最大值）。
• 首先求区间内最小是个RMQ模板，减去最小值是区间修改，这些用线段树维护。
• 那如何选择区间呢，想象一下，每次取完一个小区间（运输货物），大区间内会多出一些0值，然后覆盖这些端点且未被选取的线段就会失效。所以考虑贪心的：使这些0值对剩下的线段产生的影响最小。每次尽可能地选取右端点在最左边的线段，这样会使产生的0值尽可能在最左边，而使剩下的线段尽可能的在右边。实现上就是先把区间存下来，然后排个序。
• 最后一个点WA的，，注意，数据范围要开longlong，，然后最大初始值用1<<60，1e9是不够的。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5+10;

struct seg{int x, y;}sg[maxn];
bool cmp(seg a, seg b){return a.y!=b.y?a.y<b.y:a.x<b.x;}

LL rmq[maxn<<2], tag[maxn<<2], c[maxn];
#define lch p<<1
#define rch p<<1|1
void pushdown(int p){
	if(tag[p]){
		tag[lch] += tag[p], tag[rch]+=tag[p];
		rmq[lch] += tag[p], rmq[rch]+=tag[p];
		tag[p] = 0;
	}
}
void pushup(int p){
	rmq[p] = min(rmq[lch], rmq[rch]); 
}
void build(int p, int l, int r){
	tag[p] = 0;
	if(l==r){
		rmq[p] = c[l];
		return ;
	}else{
		int m = l+r>>1;
		build(lch,l,m);
		build(rch,m+1,r);
		pushup(p);
	}
}
void update(int p, int l, int r, int L, int R, int v){
	if(l>R || r<L)return ;
	if(L<=l && r<=R){
		rmq[p] += v;  tag[p] += v;
		return ;
	}
	pushdown(p);
	int mid = l+r>>1;
	update(lch,l,mid,L,R,v);
	update(rch,mid+1,r,L,R,v);
	pushup(p);
}
LL query(int p, int l, int r, int L, int R){
	if(l>R || r<L)return (1ll<<60);
	if(L<=l && r<=R)return rmq[p];
	pushdown(p);
	LL mid = l+r>>1, ans = 1ll<<60;
	ans = min(ans, query(lch,l,mid,L,R));
	ans = min(ans, query(rch,mid+1,r,L,R));
	return ans;
}

int main(){
	int n, q;
	cin>>n>>q;
	for(int i = 1; i < n; i++)
		cin>>c[i];
	build(1,1,n-1); //1-(n-1)号城市分别对应i与i+1的边
	for(int i = 1; i <= q; i++){
		cin>>sg[i].x>>sg[i].y;
		if(sg[i].x>sg[i].y)swap(sg[i].x,sg[i].y);
	}
	sort(sg+1,sg+q+1,cmp);
	LL ans = 0;
	for(int i = 1; i <= q; i++){
		//cout<<sg[i].x+1<<" "<<sg[i].y<<" ";
		LL res = query(1,1,n-1,sg[i].x+1,sg[i].y);//因为编号从0开始，所以x+1。
		//cout<<res<<"\n";
		ans += res;
		if(res)update(1,1,n-1,sg[i].x+1,sg[i].y,-res);
	}
	cout<<ans<<endl;
	return 0;
}


  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
  
67
  
68
  
69
  
70
  
71
  
72
  
73
  
74
  
75
  
76
  
77
  
78
 

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/109121680