2025年小树311_森林小道

原题链接

森森开了一家快递公司，叫森森快递。因为公司刚刚开张，所以业务路线很简单，可以认为是一条直线上的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

输出样例：

样例提示：我们选择执行最后两张订单，即把5公斤货从城市4运到城市2，并且把2公斤货从城市4运到城市5，就可以得到最大运输量7公斤。

题解
由题意可知道，应该先选择最小且在最左边的区间，然后查看区间的最小值，然后讲区间整体减去最小值即可

#include

#define x first

#define y second

#define send string::npos

#define lowbit(x) (x&(-x))

#define left(x) x<<1

#define right(x) x<<1|1

using namespace std;

typedef long long ll;

typedef pair PII;

typedef struct Node * pnode;

const int N = 2e5 + 10;

const int M = 3 * N;

const int INF = 0x3f3f3f3f;

const ll LINF = 0x3f3f3f3f3f3f3f3f;

const int Mod = 1e9;

struct { 

   

    int l,r;

    ll v;

    ll add;

}tr[4 * N];

ll a[N];

vectorp;

void push_up(int u){ 

   

    tr[u].v = min(tr[left(u)].v + tr[left(u)].add,tr[right(u)].v + tr[right(u)].add);

}

void push_down(int u){ 

   

    if(tr[u].add){ 

   

        tr[u].v += tr[u].add;

        tr[left(u)].add += tr[u].add;

        tr[right(u)].add += tr[u].add;

        tr[u].add = 0;

    }

}

void build(int l,int r,int u){ 

   

    if(l == r)tr[u] = { 

   l,r,a[l],0};

    else{ 

   

        tr[u] = { 

   l,r,0,0};

        int mid = (l + r) >> 1;

        build(l,mid,left(u));

        build(mid + 1,r,right(u));

        push_up(u);

    }

}

void modify(int l,int r,ll x,int u){ 

   

    if(tr[u].l >= l && tr[u].r <= r)tr[u].add += x;

    else { 

   

        push_down(u);   //修改的时候也必须push_down

        int mid = (tr[u].l + tr[u].r) >> 1;

        if(l <= mid)modify(l,r,x,left(u));

        if(r > mid)modify(l,r,x,right(u));

        push_up(u);

    }

}

ll query(int l,int r,int u){ 

   

    if(tr[u].l >= l && tr[u].r <= r)return tr[u].v + tr[u].add;

    else{ 

   

        push_down(u);

        ll v = LINF;

        int mid = (tr[u].l + tr[u].r) >> 1;

        if(l <= mid)v = query(l,r,left(u));

        if(r > mid)v = min(v,query(l,r,right(u)));

        push_up(u);

        return v;

    }

}

bool cmp(const PII &a,const PII &b){ 

   

    if(a.y != b.y)return a.y < b.y;

    else return a.x < b.x;

}

int main(){ 

   

    int n,m,x,y;

    cin>>n>>m;

    for(int i = 0;i < n - 1;i ++)cin>>a[i];

    build(0,n - 2,1);

    for(int i = 0;i < m;i ++){ 

   

        cin>>x>>y;

        if(x > y)swap(x,y);

        p.push_back({ 

   x,y});

    }

    sort(p.begin(),p.end(),cmp);        //贪心

    ll res = 0;

    for(int i = 0;i < p.size();i ++){ 

   

        ll m = query(p[i].x,p[i].y - 1,1);

        modify(p[i].x,p[i].y - 1,-m,1);

        res += m;

    }

    printf("%lld\n",res);

    return 0;

}

2025年小树311_森林小道

相关推荐