森森开了一家快递公司，叫森森快递。因为公司刚刚开张，所以业务路线很简单，可以认为是一条直线上的N个城市，这些城市从左到右依次从0到(N−1)编号。由于道路限制，第i号城市（i=0,⋯,N−2）与第(i+1)号城市中间往返的运输货物重量在同一时刻不能超过Ci公斤。
公司开张后很快接到了Q张订单，其中j张订单描述了某些指定的货物要从Sj号城市运输到Tj号城市。这里我们简单地假设所有货物都有无限货源，森森会不定时地挑选其中一部分货物进行运输。安全起见，这些货物不会在中途卸货。
为了让公司整体效益更佳，森森想知道如何安排订单的运输，能使得运输的货物重量最大且符合道路的限制？要注意的是，发货时间有可能是任何时刻，所以我们安排订单的时候，必须保证共用同一条道路的所有货车的总重量不超载。例如我们安排1号城市到4号城市以及2号城市到4号城市两张订单的运输，则这两张订单的运输同时受2-3以及3-4两条道路的限制，因为两张订单的货物可能会同时在这些道路上运输。 输入格式：
输入在第一行给出两个正整数N和Q（2≤N≤105, 1≤Q≤105），表示总共的城市数以及订单数量。
第二行给出(N−1)个数，顺次表示相邻两城市间的道路允许的最大运货重量Ci（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<ll, ll> pa; const ll inf = (ll)1<<60; const ll N = 2e5 + 10; ll T[N<<2], lazy[N<<2]; pa ro[N]; //路线 ll n, q; bool cmp(pa x, pa y) { if(x.second != y.second) return x.second < y.second; return x.first > y.first; } void build(ll l, ll r, ll k) { if(l == r) { cin >> T[k]; return; } ll mid = l + r >> 1; build(l, mid, k << 1); build(mid + 1, r, k << 1 | 1); T[k] = min(T[k<<1], T[k<<1|1]); } void pushdown(ll k) { ll num = lazy[k]; lazy[k<<1] += num; lazy[k<<1|1] += num; T[k<<1] -= num; T[k<<1|1] -= num; lazy[k] = 0; } ll query(ll l, ll r, ll x, ll y, ll k)//l~r 0~n-2, x~y目标区间 { if(x <= l && r <= y) return T[k]; if(l > y || r < x) return inf; if(lazy[k] != 0) pushdown(k); ll mid = l + r >> 1; ll tmp = inf; if(mid >= x) tmp = min(tmp, query(l, mid, x, y, k << 1)); if(mid < y) tmp = min(tmp, query(mid + 1, r, x, y, k << 1|1)); T[k] = min(T[k<<1], T[k<<1|1]); return tmp; } void update(ll l, ll r, ll x, ll y, ll k, ll num) { if(x <= l && r <= y) { T[k] -= num; lazy[k] += num; return; } if(lazy[k] != 0) pushdown(k); ll mid = l + r >> 1; if(mid >= x) update(l, mid, x, y, k << 1, num); if(mid < y) update(mid + 1, r, x, y, k << 1|1, num); T[k] = min(T[k<<1], T[k<<1|1]); } int main() { cin >> n >> q; build(0, n - 2, 1); for(ll i = 0; i < q; i++) { cin >> ro[i].first >> ro[i].second; if(ro[i].first > ro[i].second) swap(ro[i].first, ro[i].second); ro[i].second -= 1; } sort(ro, ro + q, cmp); ll ans = 0; for(ll i = 0; i < q; i++) { ll x = query(0, n - 2, ro[i].first, ro[i].second, 1); if(x != 0) { ans += x; update( 0, n - 2, ro[i].first, ro[i].second, 1, x); } } cout << ans << endl; return 0; }