CF802O April Fools' Problem (hard) 题解
KaisuoShutong
·
·
题解
UPD：谢谢 Futa 先森，指正了一些错误。
详细讲一下线段树模拟费用流做法。
大概会比较啰嗦，但是您会的可以自行跳过。
首先我们可以得出一个简单的费用流建图：
$i\rightarrow T_1$，流量 $1$，费用 $B_i$；
$T_1\rightarrow T_2$，流量 $K$，费用 $0$；
$i\rightarrow i+1$，流量 $inf$，费用 $0$。
好。那么直接跑肯定超时。考虑优化。
发现如果我们将选择的 $A$ 看成 $($，同时把选择的 $B$ 看成 $)$，那么最终形成的一定是一个合法的括号序列，因为每个 $B$ 的前面必须对应一个 $A$。
令左括号为 $+1$，右括号为 $-1$，做前缀和。
考虑带悔贪心，每次往里面插入一对匹配的左右括号。
此时有两种情况：
1. 选择 $()$，那么前缀和数组中 $[i,j)$ 的位置需要加 $1$；
2. 选择 $)($，那么前缀和数组中 $[i,j)$ 的位置需要减 $1$（**显然此时 $[i,j)$ 中的最小值必须大于 $0$**）；
为了维护 $2$ 条件中括号内容，我们有一个 naive 的想法即直接找出 $0$ 的位置然后线段树 pushup 一通乱搞；但这样是不行的，因为有区间减操作。
故我们转而维护：
$mn$：前缀和数组的区间最小值；
$va$：$()$ 的最小花费的位置数对；
$vb$：$)($ 的最小花费的位置数对（**满足两个位置之间的 $mn$ 大于当前线段树区间的 $mn$**）
$vc$：$)($ 的最小花费的位置数对；
其中 $vc$ 辅助更新 $vb$，$va$、$vb$ 用来更新答案。
为了辅助更新，我们可以将 $0$ 位置一同处理在线段树中，同时要求 $A_0=B_0=inf$；这样可以保证根区间的 $mn$ 一定为 $0$，从而使得 $vb$ 变成给定的定义。
协助更新，我们还需维护 $ma$、$mb$ 表示区间中 $A$ 和 $B$ 数组的最小值。
以上内容的维护都是 naive 的。但是非常不幸，仅这些内容并不能很好地维护处 $vb$。
在此之外，额外维护：
$al$，表示区间中满足前缀（$[L,al)$）点的前缀和区间最小值大于区间的 $mn$ 的位置，多个满足取 $A$ 最小的；
$bl$，表示区间中满足后缀（$[bl,R]$）点的前缀和区间最小值大于区间的 $mn$ 的位置，多个满足取 $B$ 最小的。
注意看我的开闭。
不妨做一些讨论（设 $l$ 和 $r$ 分别是当前线段树结点的两个儿子）：
1. $mn_l>mn_r$：
此时 $l$ 中任意点均可作 $B$，那么可用 $(mb_l,al_r)$、$vc_l$ 更新 $vb$。
此时 $al$、$bl$ 相应更新，具体见代码。
2. $mn_l<mn_r$：
同上理，略过。
3. $mn_l=mn_r$：
啥都不行，只能拿 $(al_l,bl_r)$ 更新 $vb$。
$al$、$bl$ 继承左右。
有啥不懂的，可以看代码。
码长文不易，点个赞吧。
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int read() {
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
return s*w;
}
const int maxn = 500010;
int A[maxn],B[maxn],tg[maxn<<2],n,K;ll ans;
struct node {
int x,y;
};
bool operator <(node x,node y) {return A[x.x]+B[x.y]<A[y.x]+B[y.y];}
struct info {
int ma,mb,al,bl,mn;
node va,vb,vc;
}c[maxn<<2];
info operator +(info x,info y) {
info z;
z.ma=A[x.ma]<A[y.ma]?x.ma:y.ma;
z.mb=B[x.mb]<B[y.mb]?x.mb:y.mb;
z.mn=min(x.mn,y.mn);
z.va=min(min(x.va,y.va),(node){x.ma,y.mb});
z.vc=min(min(x.vc,y.vc),(node){y.ma,x.mb});
z.vb=min(x.vb,y.vb);
if(x.mn>y.mn) {
z.vb=min(min(z.vb,(node){y.al,x.mb}),x.vc);
z.al=(A[x.ma]<A[y.al]?x.ma:y.al),z.bl=y.bl;
} else if(x.mn<y.mn) {
z.vb=min(min(z.vb,(node){y.ma,x.bl}),y.vc);
z.bl=(B[y.mb]<B[x.bl]?y.mb:x.bl),z.al=x.al;
} else {
z.vb=min(z.vb,(node){y.al,x.bl});
z.al=x.al,z.bl=y.bl;
}return z;
}
void tag(int k,int vl) {tg[k]+=vl,c[k].mn+=vl;}
void psp(int k) {c[k]=c[k<<1]+c[k<<1|1];}
void psd(int k) {if(tg[k]) tag(k<<1,tg[k]),tag(k<<1|1,tg[k]),tg[k]=0;}
void ins(int k,int l,int r,int p) {
if(l==r) return;int mid=l+r>>1;psd(k);
p>mid?ins(k<<1|1,mid+1,r,p):ins(k<<1,l,mid,p),psp(k);
}
void byd(int k,int l,int r) {
if(l==r) return c[k]=(info){l,l,l,0,0,(node){l,l},(node){0,0},(node){l,l}},void();
int mid=l+r>>1;byd(k<<1,l,mid),byd(k<<1|1,mid+1,r),psp(k);
}
void upd(int k,int l,int r,int L,int R,int vl) {
if(l>R||L>r) return;
if(L<=l&&r<=R) return tag(k,vl);int mid=l+r>>1;psd(k);
upd(k<<1,l,mid,L,R,vl),upd(k<<1|1,mid+1,r,L,R,vl),psp(k);
}
const int inf = 0x3f3f3f3f;
signed main() {
n=read(),K=read();
for(int i=1;i<=n;i++) A[i]=read();
for(int i=1;i<=n;i++) B[i]=read();
A[0]=B[0]=inf,byd(1,0,n);
while(K--) {
int x,y,vl;
if(c[1].va<c[1].vb) x=c[1].va.x,y=c[1].va.y,vl=+1;
else x=c[1].vb.x,y=c[1].vb.y,vl=-1;
ans+=A[x]+B[y],A[x]=B[y]=inf,ins(1,0,n,x),ins(1,0,n,y),upd(1,0,n,min(x,y),max(x,y)-1,vl);
}
cout<<ans<<'\n';
return 0;
}
```