BZOJ 5326 [JSOI]博弈 (模拟费用流 线段树)

题目链接

/JudgeOnline/problem.php?id=5326

题解

终于成为第8个A掉这题的人……orz tzw神仙早我6小时

本以为这东西常数巨大，没想到跑得还挺快，bzoj上不到5s就过了。

神仙题。

首先第一步转化就相当神仙: 把数组按后手的优先级从高到低定序，原题的条件等价于先手要选出一些数，使得对于每个长度为\(i\)的前缀，选出的数都不超过\(\lceil \frac{x}{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_pairusing 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;}