PAT-GPLT L3-017 森森快递（贪心 + 线段树）

链接：

https://www.patest.cn/contests/gplt/L3-017

题意：

给出直线上的N个顶点，(N-1)条边的限制值（每对相邻的顶点之间都有一条边），以及Q个区间（给出起始顶点编号以及终止顶点编号）。
每个区间都可以为该区间的所有边加上一个附加值，所有区间在某条边上所累加的附加值不能超过这条边的限制值。
问：所有区间的附加值总和最大是多少？

分析：

先按终点编号（将原来起点与终点编号较大的作为终点编号）从小到大排序，然后贪心选择：
顺序考虑每一个区间，用线段树快速找到该区间的最小值，然后更新该区间。
最后所有区间能找到的最小值总和就是答案。
至于为什么要按终点编号从小到大排序，而不是按起点编号从小到大排序，或按区间长度从小到大排序，看一下下面的测试数据就明白了。
不过这道题目说每个限制值是不超过2的31次方的非负整数，为什么偏要 long long 才能过呢？

代码：

 #include <cstdio>

 #include <algorithm>

 using namespace std;

 typedef long long int LLI;

 const LLI INF = 0x3f3f3f3f3f3f3f3f;

 const int UP = 1e5 + ;

 struct SEGMENT_TREE_NODE {

     LLI v, m; //值，标记

 } st[UP<<];

 struct REGION {

     int L, R;

     bool operator < (const REGION& that) const {

         return R < that.R;

     }

 } reg[UP];

 void build(int root, int L, int R){

     st[root].m = ;

     if(L +  == R){

         scanf("%lld", &st[root].v);

         return;

     }

     int M = L + (R - L) / ;

     build(root*+, L, M);

     build(root*+, M, R);

     st[root].v = min(st[root*+].v, st[root*+].v);

 }

 void push_down(int root){

     if(!st[root].m) return;

     st[root*+].v += st[root].m;

     st[root*+].v += st[root].m;

     st[root*+].m += st[root].m;

     st[root*+].m += st[root].m;

     st[root].m = ;

 }

 LLI query(int root, int L, int R, int AL, int AR){

     if(AR <= L || AL >= R) return INF;

     if(AL <= L && R <= AR) return st[root].v;

     push_down(root);

     int M = L + (R - L) / ;

     return min(query(root*+, L, M, AL, AR), query(root*+, M, R, AL, AR));

 }

 void update(int root, int L, int R, int AL, int AR, LLI v){

     if(AR <= L || AL >= R) return;

     if(AL <= L && R <= AR){

         st[root].v += v;

         st[root].m += v;

         return;

     }

     push_down(root);

     int M = L + (R - L) / ;

     update(root*+, L, M, AL, AR, v);

     update(root*+, M, R, AL, AR, v);

     st[root].v = min(st[root*+].v, st[root*+].v);

 }

 int main(){

     int n, q;

     scanf("%d%d", &n, &q);

     build(, , --n);

     for(int i = ; i < q; i++){

         scanf("%d%d", &reg[i].L, &reg[i].R);

         if(reg[i].L > reg[i].R) swap(reg[i].L, reg[i].R);

     }

     sort(reg, reg + q);

     LLI ans = ;

     for(int i = ; i < q; i++){

         LLI v = query(, , n, reg[i].L, reg[i].R);

         ans += v;

         if(v) update(, , n, reg[i].L, reg[i].R, -v);

     }

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

     return ;

 }

测试数据：

input1:

5 3
5 3 3 1
4 1
1 3
3 4

output1:

4

input2:

5 3
3 9 9 1
3 1
2 0
2 4

output2:

10

PAT-GPLT L3-017 森森快递（贪心 + 线段树）的相关教程结束。