L3-017. 森森快递
Standard
森森开了一家快递公司，叫森森快递。因为公司刚刚开张，所以业务路线很简单，可以认为是一条直线上的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
输出样例：
7
样例提示：我们选择执行最后两张订单，即把5公斤货从城市4运到城市2，并且把2公斤货从城市4运到城市5，就可以得到最大运输量7公斤。
题意： 题意很恶心人 ， 就是给你 n 个点 n-1 个段 和每个段的负重 你要求出 这些段 在任意时刻的最大负重量。
思路： 类似于 求 最大不相交覆盖。 但是这里并不是真的不能覆盖 ，只是需要贪心的去求 给出的m 个区间的 中的最小值
如果最小值等于 0 那么就一定不能再向这一段区间上加 重量， 所以 这个题的关键是 1 贪心的枚举给出的区间 2 快速的求出区间的最小值 （当然用线段树比较快 ）
代码：
#include<bits/stdc++.h>
#define N 100005
using namespace std;
typedef long long ll;
struct node
{
int l,r;
ll val;
int lazy;
ll tag;
}tree[N<<2];
ll dis[N];
struct node1
{
int l,r;
}reg[N];
int n,m;
bool cmp(node1 a,node1 b)
{
return a.r<b.r;
}
void push_up(int i)
{
tree[i].val=min(tree[i<<1].val,tree[i<<1|1].val);
return ;
}
void push_down(int i)
{
tree[i].lazy=0;
tree[i<<1].lazy=tree[i<<1|1].lazy=1;
ll tag=tree[i].tag;
tree[i].tag=0;
tree[i<<1].tag+=tag;
tree[i<<1|1].tag+=tag;
tree[i<<1].val+=tag;
tree[i<<1|1].val+=tag;
return ;
}
void build(int i,int l,int r)
{
tree[i].lazy=0;
tree[i].tag=0;
tree[i].l=l; tree[i].r=r;
tree[i].val=0;
if(l==r)
{
tree[i].val=dis[l];
return ;
}
int mid=(l+r)>>1;
build(i<<1,l,mid);
build(i<<1|1,mid+1,r);
push_up(i);
return ;
}
ll query(int i,int l,int r)
{
if(tree[i].l==l&&tree[i].r==r)
{
return tree[i].val;
}
if(tree[i].lazy) push_down(i);
push_up(i);
int mid=(tree[i].l+tree[i].r)>>1;
if(r<=mid)
{
return query(i<<1,l,r);
}
else if(l>mid)
{
return query(i<<1|1,l,r);
}
else
{
return min( query(i<<1,l,mid) ,query(i<<1|1,mid+1,r ) );
}
}
void update(int i,int l,int r,int num)
{
if(tree[i].l==l&&tree[i].r==r)
{
tree[i].val+=num;
if(l!=r)
{
tree[i].lazy=1;
tree[i].tag+=num;
}
return ;
}
if(tree[i].lazy) push_down(i);
int mid=(tree[i].l+tree[i].r)>>1;
if(r<=mid)
{
update(i<<1,l,r,num);
}
else if(l>mid)
{
update(i<<1|1,l,r,num);
}
else
{
update(i<<1,l,mid,num);
update(i<<1|1,mid+1,r,num);
}
push_up(i);
//printf("%d %d %d %lld \n",i,tree[i].l,tree[i].r,tree[i].val);
}
int main()
{
cin>>n>>m;
for(int i=1;i<n;i++) scanf("%lld",&dis[i]);
build(1,1,n-1);
for(int i=0;i<m;i++)
{
cin>>reg[i].l>>reg[i].r;
if(reg[i].l>reg[i].r) swap(reg[i].l,reg[i].r);
}
sort(reg,reg+m,cmp);
/*
for(int i=0;i<m;i++) cout<<reg[i].l<<" "<<reg[i].r<<endl;
*/
ll ans=0;
for(int i=0;i<m;i++)
{
ll num=query(1,reg[i].l+1,reg[i].r);
//printf(" %d %d num : %lld\n",reg[i].l+1,reg[i].r,num);
if(num>0){
ans+=num;
update(1,reg[i].l+1,reg[i].r,-num);
}
}
cout<<ans<<endl;
return 0;
}