Skip to content

L3-017 森森快递

Statement

Metadata

  • 作者: 俞勇
  • 单位: 上海交通大学
  • 代码长度限制: 16 KB
  • 时间限制: 400 ms
  • 内存限制: 64 MB

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

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

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

输入格式

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

第二行给出(N-1)个数，顺次表示相邻两城市间的道路允许的最大运货重量C_i（i=0, \cdots , 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公斤。

Solution

#include <bits/stdc++.h>
using namespace std;

#define db double
#define ll long long
#define INF 0x3f3f3f3f
#define N 100010
#define fi first
#define se second
#define pii pair<int, int>
int n, q;
ll c[N];

namespace SEG {
struct node {
    ll Min, lazy;
    node() {}
    node(ll Min, ll lazy) : Min(Min), lazy(lazy) {}
    void init() {
        Min = lazy = 0;
    }
    void add(ll x) {
        Min += x;
        lazy += x;
    }
    node operator+(const node &other) const {
        node res;
        res.init();
        res.Min = min(Min, other.Min);
        return res;
    }
} a[N << 2];
void build(int id, int l, int r) {
    a[id].init();
    if (l == r) {
        a[id].Min = c[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(id << 1, l, mid);
    build(id << 1 | 1, mid + 1, r);
    a[id] = a[id << 1] + a[id << 1 | 1];
}
void pushdown(int id) {
    if (!a[id].lazy)
        return;
    ll &x = a[id].lazy;
    a[id << 1].add(x);
    a[id << 1 | 1].add(x);
    x = 0;
}
void update(int id, int l, int r, int ql, int qr, ll v) {
    if (l >= ql && r <= qr) {
        a[id].add(v);
        return;
    }
    int mid = (l + r) >> 1;
    pushdown(id);
    if (ql <= mid)
        update(id << 1, l, mid, ql, qr, v);
    if (qr > mid)
        update(id << 1 | 1, mid + 1, r, ql, qr, v);
    a[id] = a[id << 1] + a[id << 1 | 1];
}
ll query(int id, int l, int r, int ql, int qr) {
    if (l >= ql && r <= qr)
        return a[id].Min;
    int mid = (l + r) >> 1;
    pushdown(id);
    ll res = (ll)1e18;
    if (ql <= mid)
        res = min(res, query(id << 1, l, mid, ql, qr));
    if (qr > mid)
        res = min(res, query(id << 1 | 1, mid + 1, r, ql, qr));
    return res;
}
}  // namespace SEG
pii a[N];

int main() {
    //	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    while (scanf("%d%d", &n, &q) != EOF) {
        for (int i = 1; i < n; ++i) scanf("%lld", c + i);
        ll res = 0;
        int l, r;
        SEG::build(1, 1, n - 1);
        for (int i = 1; i <= q; ++i) scanf("%d%d", &a[i].fi, &a[i].se);
        for (int i = 1; i <= q; ++i) {
            int &l = a[i].fi, &r = a[i].se;
            if (l > r)
                swap(l, r);
            ++l;
        }
        sort(a + 1, a + 1 + q, [&](pii a, pii b) {
            return a.se < b.se;
        });
        for (int i = 1; i <= q; ++i) {
            int l = a[i].fi, r = a[i].se;
            ll x = SEG::query(1, 1, n - 1, l, r);
            // cout << x << endl;
            res += x;
            SEG::update(1, 1, n - 1, l, r, -x);
        }
        printf("%lld\n", res);
    }
    return 0;
}
Last update: May 4, 2022
Back to top