题目大意
给定一棵$n(n \le 10^5)$个节点的以$1$为根的有根树,第$i$个结点上有$c_i$个食物,其父亲为$\lfloor \frac{i}{2} \rfloor$
现在依次给出$m$个拉姆,依次询问前$i$个拉姆都有东西吃的最短移动距离和
依次输出这$m$次询问的答案
解题报告
如果点数很小的话,我们显然可以跑个费用流就可以了!
但这题点这么多怎么办 QwQ
那我们就手动增广!
考虑维护一个$val_i$表示以$i$为根的子树中最近的有食物的点到$i$的距离
于是我们可以花$O(\log n)$的时间暴力在树上爬一爬就可以代替费用流的SPFA
然后考虑修改沿途边的边权,因为树高是$\log n$级别的,于是我们也是暴力修改就好
最后再用更新一下受影响的$val_i$来方便下次增广就可以辣!
以前听说过手动增广的题目,不过一次都还没有写过
这次写一写感觉这货非常好玩啊!
Code
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 100009;
const int INF = 1e9;
int n,m,vout,cnt[N],pos[N];
int sur[N],val[N],cost[N];
inline int read() {
char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}
inline int LCA(int u, int v) {
for (;u!=v;u>>=1)
if (u < v) swap(u, v);
return u;
}
inline void update(int w) {
static int ls, rs, cl, cr;
if (cnt[w]) sur[w] = w, val[w] = 0;
else sur[w] = 0, val[w] = INF;
if ((ls=w<<1) <= n) {
cl = cost[ls] > 0? -1: 1;
if(val[ls] + cl < val[w]) {
val[w] = val[ls] + cl;
sur[w] = sur[ls];
}
}
if ((rs=ls|1) <= n) {
int cr = cost[rs] > 0? -1: 1;
if(val[rs] + cr < val[w]) {
val[w] = val[rs] + cr;
sur[w] = sur[rs];
}
}
}
inline void modify(int w, int p, int delta) {
while (w != p) {
cost[w] += delta;
update(w); w >>= 1;
}
}
inline int query(int w, int &ans) {
static int ret, delta; delta = 0;
for (;w;w>>=1) {
if (val[w] + delta < ans) {
ans = val[w] + delta;
ret = sur[w];
}
delta += cost[w] >= 0? 1: -1;
} return ret;
}
int main() {
n = read(); m = read();
for (int i=1;i<=n;i++) cnt[i] = read();
for (int i=1;i<=m;i++) pos[i] = read();
for (int i=n;i;i--) update(i);
for (int i=1,u,v,ans=INF;i<=m;++i,ans=INF) {
cnt[v=query(u=pos[i], ans)]--;
printf("%d\n",vout+=ans);
int lca = LCA(u, v);
modify(u, lca, 1); modify(v, lca, -1);
for (;lca;lca>>=1) update(lca);
}
return 0;
}