L3-2 森森快递 （30 分)（贪心+线段树/分块）

题目链接：https://pintia.cn/problem-sets/1108203702759940096/problems/1108204121661857798

题目大意：

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

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

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

具体思路：首先对区间的右端点进行排序，先处理短的区间，再去处理长的区间，这样就能保证是最大了。其实就是区间查询和区间修改。

作死用分块打的区间查询和区间修改，有一个两分的样例就是A不了。。以后这种区间修改还是用线段树吧，，

分块代码：

 #include<bits/stdc++.h>

 using namespace std;

 # define ll long long

 const ll inf =0x3f3f3f3f3f3f3f3f;

 const int maxn= 3e6+;

 ll a[maxn];

 struct node

 {

     ll st;

     ll ed;

     bool friend operator < (node t1,node t2)

     {

         return t1.ed<t2.ed;

     }

 } q[maxn];

 ll vis[maxn];

 ll belong[maxn];

 ll l[maxn],r[maxn];

 ll  add[maxn];

 ll sum[maxn];

 ll  n,m;

 void build()

 {

     ll block=(ll)sqrt(n-1ll);

     for(ll i=; i<n; i++)

         belong[i]=i/block+1ll;

     ll tot=(n-)/block;

     if((n-)%block)

         tot++;

     for(ll i=; i<=tot; i++)

     {

         l[i]=(i-)*block+1ll;

         r[i]=(i)*block;

     }

     r[tot]=n-;

     for(ll i=; i<=tot; i++)

     {

         sum[i]=inf;

         for(ll  j=l[i]; j<=r[i]; j++)

         {

             sum[i]=min(vis[j],sum[i]);

         }

     }

 }

 ll ask(ll st,ll ed)

 {

     ll ans=inf;

     if(belong[st]==belong[ed])

     {

         for(ll i=st; i<=ed; i++)

         {

             ans=min(ans,vis[i]+add[belong[st]]);

         }

         return ans;

     }

     for(ll i=st; i<=r[belong[st]]; i++)

         ans=min(ans,vis[i]+add[belong[st]]);

     for(ll i=l[belong[ed]]; i<=ed; i++)

         ans=min(ans,vis[i]+add[belong[ed]]);

     for(ll i=belong[st]+; i<belong[ed]; i++)

         ans=min(ans,sum[i]+add[i]);

     return ans;

 }

 void  up(ll st,ll ed,ll val)

 {

     if(belong[st]==belong[ed])

     {

         for(ll i=st; i<=ed; i++)

         {

             vis[i]+=val;

             sum[belong[st]]=min(sum[belong[st]],vis[i]);

         }

         return ;

     }

     for(ll i=st; i<=r[belong[st]]; i++)

     {

         vis[i]+=val;

         sum[belong[st]]=min(sum[belong[st]],vis[i]);

     }

     for(ll i=l[belong[ed]]; i<=ed; i++)

     {

         vis[i]+=val;

         sum[belong[ed]]=min(sum[belong[ed]],vis[i]);

     }

     for(ll i=belong[st]+; i<belong[ed]; i++)

     {

         add[i]+=val;

     }

 }

 signed  main()

 {

     // cout<<inf<<endl;

     scanf("%lld %lld",&n,&m);

     for(ll i=; i<n; i++)

         scanf("%lld",&vis[i]);

     sort(q+,q+m+);

     build();

     ll st,ed;

     for(ll i=; i<=m; i++)

     {

         scanf("%lld %lld",&q[i].st,&q[i].ed);

         q[i].st++;

         q[i].ed++;

         if (q[i].st > q[i].ed)

             swap(q[i].st, q[i].ed);

     }

     sort(q+,q+m+);

     ll sum=;

     for(ll i=; i<=m; i++)

     {

         ll minn;

         minn=ask(q[i].st,q[i].ed-);

         sum+=minn;

         up(q[i].st,q[i].ed-,-minn);

     }

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

     return ;

 }

线段树代码：

 #include<bits/stdc++.h>

 using namespace std;

 # define ll long long

 # define lson l,m,rt<<

 # define rson m,r,rt<<|

 const ll inf =0x3f3f3f3f3f3f3f;

 const int maxn= 3e6+;

 struct node

 {

     ll st;

     ll ed;

     bool friend operator < (node t1,node t2)

     {

         return t1.ed<t2.ed;

     }

 } q[maxn];

 ll tree[maxn<<],lazy[maxn<<];

 void up(ll rt)

 {

     tree[rt]=min(tree[rt<<],tree[rt<<|]);

 }

 void down(int rt)

 {

     tree[rt<<]+=lazy[rt];

     tree[rt<<|]+=lazy[rt];

     lazy[rt<<]+=lazy[rt];

     lazy[rt<<|]+=lazy[rt];

     lazy[rt]=;

 }

 void build(ll l,ll r,ll rt)

 {

     if(l+==r)

     {

         scanf("%lld",&tree[rt]);

         return ;

     }

     ll m=(l+r)>>;

     build(lson);

     build(rson);

     up(rt);

 }

 ll ask(ll L,ll R,ll l, ll r,ll rt)

 {

     if(R<=l||L>=r)

         return inf ;

     if(L<=l&&R>=r)

     {

         return tree[rt];

     }

     ll m=(l+r)>>1ll;

     down(rt);

     return min(ask(L,R,lson),ask(L,R,rson));

 }

 void  update(ll L,ll R,ll l,ll r,ll rt,ll val)

 {

     if(R<=l||L>=r)

         return ;

     if(L<=l&&R>=r)

     {

         tree[rt]+=val;

         lazy[rt]+=val;

         return ;

     }

     ll m=(l+r)>>;

     down(rt);

     update(L,R,lson,val);

     update(L,R,rson,val);

     up(rt);

 }

 int  main()

 {

     ll n,m;

     // cout<<inf<<endl;

     scanf("%lld %lld",&n,&m);

     build(,n,);

     ll st,ed;

     for(ll i=; i<=m; i++)

     {

         scanf("%lld %lld",&q[i].st,&q[i].ed);

         q[i].st++;

         q[i].ed++;

         if (q[i].st > q[i].ed)

             swap(q[i].st, q[i].ed);

     }

     sort(q+,q+m+);

     ll sum=;

     for(ll i=; i<=m; i++)

     {

         ll minn;

         minn=ask(q[i].st,q[i].ed,,n,);

         sum+=minn;

         update(q[i].st,q[i].ed,,n,,-minn);

     }

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

     return ;

 }

L3-2 森森快递 （30 分)（贪心+线段树/分块）的相关教程结束。