![BZOJ 5326 [JSOI2017]博弈 (模拟费用流、线段树)](https://image.shishitao.com:8440/aHR0cHM6Ly9ia3FzaW1nLmlrYWZhbi5jb20vdXBsb2FkL2NoYXRncHQtcy5wbmc%2FIQ%3D%3D.png?!?w=700&webp=1 "BZOJ 5326 [JSOI2017]博弈 (模拟费用流、线段树)")
题目链接
https://www.lydsy.com/JudgeOnline/problem.php?id=5326
题解
终于成为第8个A掉这题的人……orz tzw神仙早我6小时
本以为这东西常数巨大，没想到跑得还挺快，bzoj上不到5s就过了。
神仙题。
首先第一步转化就相当神仙: 把数组按后手的优先级从高到低定序，原题的条件等价于先手要选出一些数，使得对于每个长度为\(i\)的前缀，选出的数都不超过\(\lceil \frac{i}{2}\rceil\)个。
然后显然可以认为一开始的收益是\(-\sum^{n}_{i=1} b_i\), 每选一个\(i\)会得到\(a_i+b_i\)的收益，最大化总收益。
后面有三种理解方式：
(1) 直接用贪心理解。易证这个贪心满足拟阵，直接按\(a+b\)从大到小排序，能选就选即可。
(2) 模拟费用流。从源点往每个点\(i (1\le i\le n)\)连\((1,a_i+b_i)\), 从每个点\(i\)向\(i+1\)连\((\lceil \frac{i}{2}\rceil,0)\)，汇点即为\(n+1\)号点。
(3) 另一种模拟费用流，转化成老鼠进洞模型。考虑在\(1,3,5,7,9...\)位置各放一只老鼠，此外在每个位置上都视为有一个洞，老鼠只能往右走。
这样就可以单次处理\(O(n\log n)\).
（我能说我理解这点东西就花了四个小时吗……）
然后考虑如何支持修改。
下面以第二种方式理解，其余方式本质上完全相同。
一次增广时我们就要找最长路，因为从\(i\)向\(i+1\)的边的代价都是\(0\), 所以就是要找所有满足到汇点的边都有剩余容量且未增广的点中\(a_i+b_i\)最大的。
增广之后，我们要把这条边到汇点的流量全部\(-1\).
一次修改相当于先删边再加边。
假设删除的是从源点到点\(x\)的边，若该边目前已被增广，那么我们要退回去，减去它的答案，同时所有后面的横向边容量\(+1\)；否则直接删除即可。
删除之后我们最好保证答案依然最优，于是尝试增广（重复刚才提到的增广一次的过程）。
添加的时候比较麻烦，因为如果增广该边的话可能需要替掉至多一条边（莫名觉得很像最小生成树，也许是拟阵的通性？）
所以首先判断在不替掉任何边的情况下是否可以直接增广，如果可以的话直接增广，否则我们找到一个点\(y\)满足\(y\)是\(x\)到汇点路径上第一个\(0\)之前的\(a_i+b_i\)最小的点\(i\), 判断用\(x\)替代\(y\)是否更优，更优则替代。
以上所有操作均可用线段树维护（我写了三棵线段树，单点/区间修改、维护最大/最小值及其位置，三棵线段树分别维护已增广的点、未增广的点和横边），时间复杂度\(O(n\log n)\).
代码
因为我写了三棵线段树，所以码长约6KB……
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<utility>
#include<cassert>
#define llong long long
#define pli pair<llong,int>
#define pii pair<int,int>
#define mkpr make_pair
using namespace std;
void read(int &x)
{
int f=1;x=0;char s=getchar();
while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
x*=f;
}
const int N = 1e5;
const llong INF = 10000000000ll;
struct Element
{
llong a,b; int id;
bool operator <(const Element &arg) const {return b>arg.b || (b==arg.b && id<arg.id);}
} a[N+3];
llong c[N+3];
int w[N+3];
bool flow[N+3];
int id[N+3];
llong ans;
int n,q;
struct SegmentTree1 //maximum with no flow
{
pli sgt[(N<<2)+3];
void update(pli &x,pli y) {if(y.first>x.first) {x = y;}}
void pushup(int u)
{
sgt[u] = mkpr(0,0);
update(sgt[u],sgt[u<<1]);
update(sgt[u],sgt[u<<1|1]);
}
void build(int u,int le,int ri,llong a[])
{
if(le==ri) {sgt[u] = mkpr(a[le],le); return;}
int mid = (le+ri)>>1;
build(u<<1,le,mid,a);
build(u<<1|1,mid+1,ri,a);
pushup(u);
}
void modify(int u,int le,int ri,int pos,llong x)
{
if(le==ri) {sgt[u] = mkpr(x,pos); return;}
int mid = (le+ri)>>1;
if(pos<=mid) modify(u<<1,le,mid,pos,x);
else modify(u<<1|1,mid+1,ri,pos,x);
pushup(u);
}
pli querymax(int u,int le,int ri,int lb,int rb)
{
if(le>=lb && ri<=rb) {return sgt[u];}
int mid = (le+ri)>>1; pli ret = mkpr(0,0);
if(lb<=mid) update(ret,querymax(u<<1,le,mid,lb,rb));
if(rb>mid) update(ret,querymax(u<<1|1,mid+1,ri,lb,rb));
return ret;
}
} sgt1;
struct SegmentTree2 //minimum with flow
{
pli sgt[(N<<2)+3];
void update(pli &x,pli y) {if(y.first<x.first) x = y;}
void pushup(int u)
{
sgt[u] = mkpr(INF,0);
update(sgt[u],sgt[u<<1]);
update(sgt[u],sgt[u<<1|1]);
}
void build(int n) {for(int i=0; i<=(n<<2); i++) sgt[i].first = INF;}
void modify(int u,int le,int ri,int pos,llong x)
{
if(le==ri) {sgt[u] = mkpr(x,pos); return;}
int mid = (le+ri)>>1;
if(pos<=mid) modify(u<<1,le,mid,pos,x);
else modify(u<<1|1,mid+1,ri,pos,x);
pushup(u);
}
pli querymin(int u,int le,int ri,int lb,int rb)
{
if(le>=lb && ri<=rb) {return sgt[u];}
int mid = (le+ri)>>1; pli ret = mkpr(INF,0);
if(lb<=mid) update(ret,querymin(u<<1,le,mid,lb,rb));
if(rb>mid) update(ret,querymin(u<<1|1,mid+1,ri,lb,rb));
return ret;
}
} sgt2;
struct SegmentTree3 //minimum flow
{
struct SgTNode
{
pii x; int tag;
SgTNode() {x = mkpr(n,0); tag = 0;}
} sgt[(N<<2)+3];
void update(pii &x,pii y)
{
if(y.first<x.first) {x = y;}
else if(y.first==x.first && y.second<x.second) {x = y;}
}
void pushdown(int u)
{
int tag = sgt[u].tag;
if(tag)
{
sgt[u<<1].x.first+=tag; sgt[u<<1].tag+=tag;
sgt[u<<1|1].x.first+=tag; sgt[u<<1|1].tag+=tag;
sgt[u].tag = 0;
}
}
void pushup(int u)
{
sgt[u].x = mkpr(INF,0);
update(sgt[u].x,sgt[u<<1].x);
update(sgt[u].x,sgt[u<<1|1].x);
}
void build(int u,int le,int ri,int a[])
{
if(le==ri) {sgt[u].x = mkpr(a[le],le); return;}
int mid = (le+ri)>>1;
build(u<<1,le,mid,a);
build(u<<1|1,mid+1,ri,a);
pushup(u);
}
void addval(int u,int le,int ri,int lb,int rb,int x)
{
if(le>=lb && ri<=rb) {sgt[u].tag += x; sgt[u].x.first += x; return;}
pushdown(u);
int mid = (le+ri)>>1;
if(lb<=mid) addval(u<<1,le,mid,lb,rb,x);
if(rb>mid) addval(u<<1|1,mid+1,ri,lb,rb,x);
pushup(u);
}
pii querymin(int u,int le,int ri,int lb,int rb)
{
if(le>=lb && ri<=rb) {return sgt[u].x;}
pushdown(u);
int mid = (le+ri)>>1; pii ret = mkpr(n,0);
if(lb<=mid) {update(ret,querymin(u<<1,le,mid,lb,rb));}
if(rb>mid) {update(ret,querymin(u<<1|1,mid+1,ri,lb,rb));}
pushup(u);
return ret;
}
int query(int u,int le,int ri)
{
if(sgt[u].x.first>0) return le;
else if(le==ri) return le+1;
pushdown(u);
int mid = (le+ri)>>1,ret;
if(sgt[u<<1|1].x.first>0) ret = query(u<<1,le,mid);
else ret = query(u<<1|1,mid+1,ri);
pushup(u);
return ret;
}
} sgt3;
void augment()
{
int pos = sgt3.query(1,1,n);
if(pos<=n)
{
pli aug = sgt1.querymax(1,1,n,pos,n);
if(aug.first>0)
{
ans += c[aug.second];
sgt1.modify(1,1,n,aug.second,0);
sgt2.modify(1,1,n,aug.second,c[aug.second]);
sgt3.addval(1,1,n,aug.second,n,-1);
flow[aug.second] = true;
}
}
}
int main()
{
scanf("%d",&n);
for(int i=1; i<=n; i++) scanf("%lld",&a[i].a);
for(int i=1; i<=n; i++) scanf("%lld",&a[i].b),a[i].id = i;
sort(a+1,a+n+1);
for(int i=1; i<=n; i++) id[a[i].id] = i;
for(int i=1; i<=n; i++) c[i] = a[i].a+a[i].b;
for(int i=1; i<=n; i++) ans -= a[i].b;
for(int i=1; i<=n; i++) w[i] = (i+1)>>1;
sgt1.build(1,1,n,c);
sgt2.build(n);
sgt3.build(1,1,n,w);
for(int i=1; i<=((n+1)>>1); i++)
{
augment();
}
printf("%lld\n",ans);
scanf("%d",&q);
while(q--)
{
int u; llong x; scanf("%d%lld",&u,&x); u = id[u];
if(flow[u])
{
ans -= c[u];
sgt3.addval(1,1,n,u,n,1);
sgt2.modify(1,1,n,u,INF);
augment();
flow[u] = false;
}
else
{
sgt1.modify(1,1,n,u,0);
}
c[u] = x+a[u].b;
pii tmp = sgt3.querymin(1,1,n,u,n);
if(tmp.first>0)
{
ans += c[u];
sgt2.modify(1,1,n,u,c[u]);
sgt3.addval(1,1,n,u,n,-1);
flow[u] = true;
}
else
{
pli tmp2 = sgt2.querymin(1,1,n,1,tmp.second);
if(tmp2.first<INF && c[u]>c[tmp2.second])
{
sgt3.addval(1,1,n,tmp2.second,n,1);
sgt3.addval(1,1,n,u,n,-1);
sgt1.modify(1,1,n,tmp2.second,c[tmp2.second]);
sgt2.modify(1,1,n,tmp2.second,INF);
sgt2.modify(1,1,n,u,c[u]);
ans -= c[tmp2.second];
ans += c[u];
flow[tmp2.second] = false;
flow[u] = true;
}
else
{
sgt1.modify(1,1,n,u,c[u]);
}
}
printf("%lld\n",ans);
}
return 0;
}