团体程序设计天梯赛 L3-017 森森快递 (30分)（线段树区间更新）

题目链接：

L3-017 森森快递 (30分)

思路：

题意可以理解为按一定顺序选取这些线段，每选取一个线段，求出该区间最小值，然后区间内都减去这个最小值，依次取下一个线段，我们需要求减去值的总和的最大值；
想象一下，每次选取完一段有效线段后，总区间内将会出现1或多个0值，这将导致其它覆盖这些端点的且未选取线段会失效（即选取了区间最小值为0，即不能运输货物）；
我们采用贪心的思想，使这些0值对剩下的线段产生的影响最小；
可以采取的一种思路就是每次尽可能地选取右端点在最左边的线段，这样会使产生的0值尽可能在最左边，而使剩下的线段尽可能的在右边；
其中涉及到区间最小值、区间更新，使用带有lazy-tag的线段树可以快速处理；

代码：

#include<bits/stdc++.h>

using namespace std;

inline int read() {
	int x = 0; char c;
	while(c = getchar(), c < '0' || c > '9');
	while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return x;	
}

typedef long long ll;
const int maxn = 1e5 + 5;
ll rmq[maxn << 2], tag[maxn << 2];
void push_up(int rt) { rmq[rt] = min(rmq[rt << 1], rmq[rt << 1 | 1]); }
void push_down(int rt) {
	if(tag[rt]) {
		tag[rt << 1] += tag[rt], tag[rt << 1 | 1] += tag[rt];
		rmq[rt << 1] += tag[rt], rmq[rt << 1 | 1] += tag[rt];
		tag[rt] = 0;
	}
}
#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
void build(int l, int r, int rt) {
	tag[rt] = 0;
	if(l == r) { rmq[rt] = read(); return; }
	int mid = (l + r) >> 1;
	build(lson), build(rson);
	push_up(rt);
}
void update(int a, int b, ll c, int l, int r, int rt) {
	if(a <= l && b >= r) { rmq[rt] += c; tag[rt] += c; return; }
	push_down(rt);
	int mid = (l + r) >> 1;
	if(a <= mid) update(a, b, c, lson);
	if(b > mid) update(a, b, c, rson);
	push_up(rt);	
}
ll query(int a, int b, int l, int r, int rt) {
	if(a <= l && b >= r) return rmq[rt];
	push_down(rt);
	int mid = (l + r) >> 1;
	ll ans = 1ll << 60;
	if(a <= mid) ans = min(ans, query(a, b, lson));
	if(b > mid) ans = min(ans, query(a, b, rson));
	return ans;
}
struct seg { 
	int x, y;
	bool operator < (seg & a) const { return y < a.y; }
}a[maxn];
int main() {
#ifdef MyTest
	freopen("Sakura.txt", "r", stdin);
#endif
	int n = read(), q = read();
	build(1, n - 1, 1);
	for(int i = 0; i < q; ++i) { 
		a[i].x = read(), a[i].y = read();
		if(a[i].x > a[i].y) swap(a[i].x, a[i].y);
	}
	sort(a, a + q);
	ll ans = 0;
	for(int i = 0; i < q; ++i) {
		ll res = query(a[i].x + 1, a[i].y, 1, n - 1, 1);
		ans += res;
		if(res) update(a[i].x + 1, a[i].y, -res, 1, n - 1, 1);
	}
	cout << ans;
	return 0;	
}