CF1682F MCMF?
题意：
费用流，其实bushi
给你长为\(n\)的序列\(a\),\(b\)。\(a\)单增，\(b\)有正有负。
\(q\)次询问\([l,r]\)，保证\(\sum\limits_{i=l}^rb_i=0\)，将区间\([l,r]\)中每个值当节点，\(b_i<0\)的连S,\(b_i>0\)的连T,容量为\(abs(b_i)\)。两两点连边，容量为inf，费用为\(abs(a_i-a_j)\)。问最小费用最大流。
思路：
显然有一个感性的贪心思路：每次尽量会去抵消前面最近的需要抵消的流量，抵消后自己剩余的留量就留给后面抵消。这样就可以从前枚举\(l~r\)，考虑每个点贡献对前面流单位流量贡献\(a_i\),后面\(-a_i\)
关键是前后分别流多少？
令\(s_i\)为\(b_i\)求前缀和。
- \(b_i<0\)时
1.\(s_{i-1}-s_{l-1}<=0\) 即 \(s_{l-1}>=s_{i-1}\) :全部贡献给后面，贡献\(-a_i*b_i\)
2.\(0
3.\(s_{i-1}-s_{l-1}>=-b_i\) 即 \(s_{l-1}<=s_{i}\) \(a_i*b_i\) - \(b_i>0\)时
第一、三种情况和前面是一样的，第二种情况变号……
发现询问跟\(i\)和\(s_{l}\)有关，如果用主席树处理好了每个\(i\)的贡献，记录一个版本，具体修改三次区间修改即可，操作2要维护两个值（关于/不关于\(s_{l-1}\)）。这样询问，直接\(rt_{l-1}\)到\(rt_r\)版本差分单点查询。
ps.不建议写，非常卡空间，官方有更好写的树状数组写法，也可以离线线段树，当然我是为了练主席树。
code:
#include
using namespace std;
typedef long long ll;
const int N=2e5+5;
const int M=1e7+5e6;
const int mod=1e9+7;
int m,n,rt[N],q;
ll sum[N],s[N],a[N],b[N],val[N];
struct segment {
int nd,p,q,ls[M],rs[M],va[M],vab[M];
ll w1,w2,part;
void Update(int &x,int l,int r,int lst) {
if(x<=part){x=++nd;if(lst){ls[x]=ls[lst],rs[x]=rs[lst];va[x]=va[lst],vab[x]=vab[lst];}}
if(p<=l&&r<=q) {if(w1)va[x]=(va[x]+w1)%mod;vab[x]=(vab[x]+w2)%mod;return;}
int mid=(l+r)>>1;
if(p<=mid)Update(ls[x],l,mid,ls[lst]);
if(q>mid)Update(rs[x],mid+1,r,rs[lst]);
}
void Query(int x,int y,int l,int r) {
// printf("!x=%d y=%d [%d,%d] w1=%lld w2=%lld\n",x,y,l,r,va[y]-va[x],vab[y]-vab[x]);
w1=(w1+va[y]-va[x])%mod;w2=(w2+vab[y]-vab[x])%mod;
if(l==r) {return;}
int mid=(l+r)>>1;
(p<=mid)?Query(ls[x],ls[y],l,mid):Query(rs[x],rs[y],mid+1,r);
}
void init() {
for(int i=1;i<=n;i++) {
part=nd;
// printf("i=%d ~~~\n",i);
int opt=(b[i]<0)?-1:1,l,r;
if(opt<0) {l=s[i],r=s[i-1];}
else {l=s[i-1],r=s[i];}
w1=-a[i]*b[i]%mod,w2=0,p=0,q=l,Update(rt[i],1,m,rt[i-1]);
w1=a[i]*b[i]%mod,w2=0,p=r,q=m,Update(rt[i],1,m,rt[i-1]);
if(r-l<=1)continue;
w1=-opt*(sum[i-1]+sum[i])*a[i]%mod,w2=2*opt*a[i]%mod,p=l+1,q=r-1,Update(rt[i],1,m,rt[i-1]);
}
}
}S;
void in_puts() {
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++) {scanf("%lld",&a[i]);}
for(int i=1;i<=n;i++) {scanf("%lld",&b[i]);s[i]=sum[i]=val[i]=s[i-1]+b[i];sum[i]%=mod;}
sort(val,val+1+n);
m=unique(val,val+1+n)-val;
for(int i=0;i<=n;i++) {s[i]=lower_bound(val,val+m,s[i])-val+1;}
}
int main() {
in_puts();
S.init();
for(int i=1;i<=q;i++) {
int l,r;scanf("%d%d",&l,&r);
S.w1=S.w2=0,S.p=s[l-1];S.Query(rt[l-1],rt[r],1,m);
ll ans=S.w2*sum[l-1]+S.w1;
printf("%lld\n",(ans%mod+mod)%mod);
}
return 0;
}