模拟费用流巨大板子题。
我们考虑到费用流模型非常好建，同时我们需要发掘一下这个费用流模型的性质。
考虑到如果我们同时存在向上的反向边（费用为 (-1) ），向下的正向边（费用为 (1) ），根据费用流算法的原则，这里我们必然贪心选择费用为 (-1) 的边，也就是说，我们不可能同时存在两个方向的边其反向边都存在流量。这样的话我们就可以开一个数组记录一下每一条边是向上存在多少流量还是向下存在多少流量，直接通过这个流量来计算费用。
然后就每一个点暴力维护子树中费用最小的洞，查询的时候每一个点暴跳，然后暴力修改流量就行了。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const int INF=1e9+7;
int n,m,a[N];long long res=0;
int flow[N],dis[N],pos[N];
int up(int u){return (flow[u]>=0)?1:-1;}
int down(int u){return (flow[u]<=0)?1:-1;}
void update(int u){
if(a[u]) dis[u]=0,pos[u]=u;else dis[u]=INF;
if((u<<1)<=n&&dis[u<<1]+down(u<<1)<dis[u])
dis[u]=dis[u<<1]+down(u<<1),pos[u]=pos[u<<1];
if((u<<1|1)<=n&&dis[u<<1|1]+down(u<<1|1)<dis[u])
dis[u]=dis[u<<1|1]+down(u<<1|1),pos[u]=pos[u<<1|1];
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
for(int i=n;i>=1;--i) update(i);
for(int i=1,x;i<=m;++i){
scanf("%d",&x);
int dist=INF,posi=0,lca=0,tmp=0,now=x;
while(now){
if(dis[now]+tmp<dist){
dist=dis[now]+tmp;
posi=pos[now],lca=now;
}
tmp+=up(now),now>>=1;
}
res+=dist,printf("%lld ",res),a[posi]--;
while(x>lca) flow[x]++,update(x),x>>=1;
while(posi>lca) flow[posi]--,update(posi),posi>>=1;
while(lca) update(lca),lca>>=1;
}
return printf("
"),0;
}
/*
还在想前 $k$ 只老鼠怎么维护，还以为要闵可夫斯基和（其实也是用不了的）。发现这里满
足树高是 $log_2n$ 的，直接暴力跳就行了。
我们考虑模拟费用流就是类似于反悔贪心的过程，在这里也是适用的。
我们就考虑每一个点维护其向下的距离最短的若干个食物（带权的，表示数量）。
我们考虑之前的黑白点的做法，但是此时如果我们考虑的是一只一只老鼠加进去的话我们可能
在执行过程中出现新的老鼠？
-------------------------------------------------------------------------
我们考虑树高是 $log_2n$ 级别的，这意味着我们可以暴力模拟费用流。
实际上我们对于一条边，我们需要知道的是其流向，如果其即存在正向的流量，有存在反向的
流量，无论从贪心角度考虑还是模拟的费用流角度考虑，都是直接选择 `cost=-1` 的反向边。
*/