题目链接：https://pintia.cn/problem-sets/1108203702759940096/problems/1108204121661857798
题目大意：
森森开了一家快递公司，叫森森快递。因为公司刚刚开张，所以业务路线很简单，可以认为是一条直线上的N个城市，这些城市从左到右依次从0到(编号。由于道路限制，第i号城市（,）与第(号城市中间往返的运输货物重量在同一时刻不能超过Ci公斤。
公司开张后很快接到了Q张订单，其中j张订单描述了某些指定的货物要从Sj号城市运输到Tj号城市。这里我们简单地假设所有货物都有无限货源，森森会不定时地挑选其中一部分货物进行运输。安全起见，这些货物不会在中途卸货。
为了让公司整体效益更佳，森森想知道如何安排订单的运输，能使得运输的货物重量最大且符合道路的限制？要注意的是，发货时间有可能是任何时刻，所以我们安排订单的时候，必须保证共用同一条道路的所有货车的总重量不超载。例如我们安排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 ;
}