题意
有 A,B 两家工厂，A 工厂第 \(i\) 天能花费 \(a_i\) 将零级产品加工成一级产品，B 工厂第 \(i\) 天能花费 \(b_i\) 将一级产品加工成二级产品，且一天之内 A 工厂加工出来的一级产品可以直接投入到 B 工厂进行再加工。假设最初有足够多的零级产品，求加工出来 \(k\) 件二级产品的最小代价。
\(n\le 5\times10^5,a_i,b_i\le10^9\)
分析
首先看起来就很像匹配，而且很像括号序列匹配。所以可以很容易的写出一个费用流模型：
- \(S\rightarrow i(1,a_i)\)
- \(i\rightarrow T'(1,b_i)\)
- \(T'\rightarrow T(k,0)\)
- \(i\rightarrow i+1(\infty,0)\)
这数据范围肯定过不去。由于是费用流模型，所以有凸性，可以 wqs 二分结合反悔贪心求解（类似于选出若干个左括号和右括号形成匹配的最小代价），时间复杂度 \(O(n\log^2n)\)。
但是可以使用模拟费用流做到 \(O(n\log n)\)。
手玩一下可以发现每一点流量的可能路径只有一种：\(S\rightarrow i\rightarrow j\rightarrow T\)，如果 \(i\le j\) 则没有其他限制，如果 \(i>j\) 则需要满足 \(j\rightarrow i\) 之间有反悔边存在，形式化的说，有一个数组 \(s\)，每次 \(i\le j\) 就对 \([i,j)\) 区间加 1，每次 \(i>j\) 就对 \([j,i)\) 区间减 1，\(i>j\) 需要满足 \([j,i)\) 区间最小值大于 0。
第一种情况很容易用线段树维护。考虑第二种情况，由于是区间加减，正常情况下我们需要存储值为每一个数的信息，这样肯定爆炸了，但是我们可以对于一个区间只考虑其大于区间内最小值的那些数的答案，这些是更容易用线段树维护的（此时改变一个节点的区间最小值不改变其区间内的其他信息），且可以合并，由于维护的是 \(1\sim n\) 之间的边，将边放到左端点考虑，那么 \(n\) 这个点显然不会有值，最小值就恒为 \(0\)，保证了正确性。
维护这个东西只需要维护区间 \(a,b\) 最小值、区间情况一最小数对，区间情况二最小数对，区间情况二没有限制最小数对（最小值改变后会用到），后缀最后一个大于最小值的位置的后缀最小值，前缀第一个等于最小值的位置的前缀最小值，具体操作见代码。
点击查看代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<map>
#include<unordered_map>
#include<vector>
#include<queue>
#include<stack>
#include<bitset>
#include<set>
#include<array>
#include<tuple>
#include<ctime>
#include<random>
#include<cassert>
#include<chrono>
#define x1 xx1
#define y1 yy1
#define IOS ios::sync_with_stdio(false)
#define ITIE cin.tie(0)
#define OTIE cout.tie(0)
#define PY puts("Yes")
#define PN puts("No")
#define PW puts("-1")
#define P0 puts("0")
#define P__ puts("")
#define PU puts("--------------------")
#define mp make_pair
#define fi first
#define se second
#define gc getchar
#define pc putchar
#define pb emplace_back
#define un using namespace
#define il inline
#define all(x) x.begin(),x.end()
#define mem(x,y) memset(x,y,sizeof x)
#define popc __builtin_popcountll
#define rep(a,b,c) for(int a=(b);a<=(c);++a)
#define per(a,b,c) for(int a=(b);a>=(c);--a)
#define reprange(a,b,c,d) for(int a=(b);a<=(c);a+=(d))
#define perrange(a,b,c,d) for(int a=(b);a>=(c);a-=(d))
#define graph(i,j,k,l) for(int i=k[j];i;i=l[i].nxt)
#define lowbit(x) ((x)&-(x))
#define lson(x) ((x)<<1)
#define rson(x) ((x)<<1|1)
//#define double long double
//#define int long long
//#define int __int128
using namespace std;
using i64=long long;
using u64=unsigned long long;
using pii=pair<int,int>;
template<typename T1,typename T2>inline void ckmx(T1 &x,T2 y){x=x>y?x:y;}
template<typename T1,typename T2>inline void ckmn(T1 &x,T2 y){x=x<y?x:y;}
inline auto rd(){int qwqx=0,qwqf=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')qwqf=-1;ch=getchar();}while(ch>='0'&&ch<='9'){qwqx=(qwqx<<1)+(qwqx<<3)+ch-48;ch=getchar();}return qwqx*qwqf;
}
template<typename T>inline void write(T qwqx,char ch='\n'){if(qwqx<0){qwqx=-qwqx;putchar('-');}int qwqy=0;static char qwqz[40];while(qwqx||!qwqy){qwqz[qwqy++]=qwqx%10+48;qwqx/=10;}while(qwqy--){putchar(qwqz[qwqy]);}if(ch)putchar(ch);
}
bool Mbg;
const int mod=998244353;
template<typename T1,typename T2>inline void adder(T1 &x,T2 y){x+=y,x=x>=mod?x-mod:x;}
template<typename T1,typename T2>inline void suber(T1 &x,T2 y){x-=y,x=x<0?x+mod:x;}
const int maxn=5e5+5,inf=0x3f3f3f3f,Inf=0x7fffffff;
const long long llinf=0x3f3f3f3f3f3f3f3f;
int n,k,a[maxn],b[maxn];
//0 i<=j 1 i>j
//m0 i<=j的最小对 m10 i>j的最小对，没限制 m11 i>j最小对，有限制
//na 前缀第一个=min的 nb 后缀最后一个>min的
struct node{pii m0,m10,m11;int ma,mb,mn,na,nb;
}d[maxn<<2];
il int calc(int x,int y){return (x==-1||y==-1)?Inf:a[x]+b[y];}
il int calca(int x){return x==-1?Inf:a[x];}
il int calcb(int x){return x==-1?Inf:b[x];}
il node operator+(node x,node y){node res;res.ma=calca(x.ma)<calca(y.ma)?x.ma:y.ma,res.mb=calcb(x.mb)<calcb(y.mb)?x.mb:y.mb;res.mn=min(x.mn,y.mn),res.na=x.na,res.nb=y.nb;if(res.mn<x.mn)x.nb=x.mb;if(res.mn<y.mn)y.na=y.ma;if(res.mn<x.mn)res.na=calca(x.ma)<calca(y.na)?x.ma:y.na;if(res.mn<y.mn)res.nb=calcb(y.mb)<calcb(x.nb)?y.mb:x.nb;res.m0=calc(x.m0.fi,x.m0.se)<calc(y.m0.fi,y.m0.se)?x.m0:y.m0;if(calc(x.ma,y.mb)<calc(res.m0.fi,res.m0.se))res.m0=mp(x.ma,y.mb);res.m10=calc(x.m10.fi,x.m10.se)<calc(y.m10.fi,y.m10.se)?x.m10:y.m10;if(calc(y.ma,x.mb)<calc(res.m10.fi,res.m10.se))res.m10=mp(y.ma,x.mb);res.m11=calc(x.m11.fi,x.m11.se)<calc(y.m11.fi,y.m11.se)?x.m11:y.m11;if(calc(y.na,x.nb)<calc(res.m11.fi,res.m11.se))res.m11=mp(y.na,x.nb);if(res.mn<x.mn&&calc(x.m10.fi,x.m10.se)<calc(res.m11.fi,res.m11.se))res.m11=x.m10;if(res.mn<y.mn&&calc(y.m10.fi,y.m10.se)<calc(res.m11.fi,res.m11.se))res.m11=y.m10;return res;
}
int tag[maxn<<2];
#define mid ((l+r)>>1)
il void pu(int p){d[p]=d[lson(p)]+d[rson(p)];
}
il void pt(int p,int v){d[p].mn+=v,tag[p]+=v;
}
il void pd(int p){if(tag[p]){pt(lson(p),tag[p]),pt(rson(p),tag[p]);tag[p]=0;}
}
void bd(int l=1,int r=n,int p=1){if(l==r){d[p].ma=d[p].mb=d[p].na=l,d[p].mn=0,d[p].m0=mp(l,l),d[p].m10=d[p].m11=mp(-1,-1),d[p].nb=-1;return;}bd(l,mid,lson(p)),bd(mid+1,r,rson(p));pu(p);
}
void upd(int ll,int rr,int v,int l=1,int r=n,int p=1){if(ll<=l&&r<=rr)return pt(p,v);pd(p);if(ll<=mid)upd(ll,rr,v,l,mid,lson(p));if(rr>mid)upd(ll,rr,v,mid+1,r,rson(p));pu(p);
}
void mdfa(int x,int l=1,int r=n,int p=1){if(l==r)return d[p].ma=d[p].na=-1,d[p].m0=d[p].m10=d[p].m11=mp(-1,-1),void();pd(p);x<=mid?mdfa(x,l,mid,lson(p)):mdfa(x,mid+1,r,rson(p));pu(p);
}
void mdfb(int x,int l=1,int r=n,int p=1){if(l==r)return d[p].mb=d[p].nb=-1,d[p].m0=d[p].m10=d[p].m11=mp(-1,-1),void();pd(p);x<=mid?mdfb(x,l,mid,lson(p)):mdfb(x,mid+1,r,rson(p));pu(p);
}
#undef mid
il pii Min(pii x,pii y){return calc(x.fi,x.se)<calc(y.fi,y.se)?x:y;
}
inline void solve_the_problem(){n=rd(),k=rd();rep(i,1,n)a[i]=rd();rep(i,1,n)b[i]=rd();i64 ans=0;bd();rep(_,1,k){
// write(_);
// write(d[1].m0.fi,32),write(d[1].m0.se,32),write(calc(d[1].m0.fi,d[1].m0.se));
// write(d[1].m11.fi,32),write(d[1].m11.se,32),write(calc(d[1].m11.fi,d[1].m11.se));assert(!d[1].mn);pii nw=Min(d[1].m0,d[1].m11);ans+=calc(nw.fi,nw.se);mdfa(nw.fi),mdfb(nw.se);if(nw.fi<=nw.se){if(nw.fi<nw.se)upd(nw.fi,nw.se-1,1);}else{upd(nw.se,nw.fi-1,-1);}}write(ans);
}
bool Med;
signed main(){
// freopen("in.in","r",stdin);fprintf(stderr,"%.3lfMB\n",(&Mbg-&Med)/1048576.0);int _=1;while(_--)solve_the_problem();
}
/**/