[费用流手动增广 线段树] BZOJ 3267 KC采花 3272 Zgg吃东西 3638 Cf172 k

[费用流手动增广 线段树] BZOJ 3267 KC采花 3272 Zgg吃东西 3638 Cf172 k

费用流构图

发现这个图比较特殊，可以手动增广

就是选择一个最大和子串，然后全部取反

线段树实现

#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;inline char nc()
{static char buf[100000],*p1=buf,*p2=buf;if (p1==p2) { p2=(p1=buf)+fread(buf,1,100000,stdin); if (p1==p2) return EOF; }return *p1++;
}inline void read(int &x)
{char c=nc(),b=1;for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}const int N=100005;struct abcd{int l,r,v;abcd(int l=0,int r=0,int v=0):l(l),r(r),v(v) { }
};struct Seg{struct node{int rev,sum; int not_null;abcd Lmax,Lmin,Rmax,Rmin,Mmax,Mmin;void reverse(){rev^=1; sum=-sum;swap(Lmax,Lmin); Lmax.v=-Lmax.v; Lmin.v=-Lmin.v; swap(Rmax,Rmin); Rmax.v=-Rmax.v; Rmin.v=-Rmin.v; swap(Mmax,Mmin); Mmax.v=-Mmax.v; Mmin.v=-Mmin.v; }node(){not_null=0;}node(int pos,int x){rev=0; sum=x; not_null=1;Lmax=Lmin=Rmax=Rmin=Mmax=Mmin=abcd(pos,pos,x);}friend node operator + (const node &A,const node &B){node ret;if (!A.not_null || !B.not_null) {A.not_null?ret=A:ret=v=0; return ret;}ret.sum=A.sum+B.sum; _null=1; v=0;ret.Lmin=A.Lmin; if (A.sum+B.Lmin.v<ret.Lmin.v) ret.Lmin=abcd(A.Lmin.l,B.Lmin.r,A.sum+B.Lmin.v);ret.Lmax=A.Lmax; if (A.sum+B.Lmax.v>ret.Lmax.v) ret.Lmax=abcd(A.Lmax.l,B.Lmax.r,A.sum+B.Lmax.v);ret.Rmin=B.Rmin; if (A.Rmin.v+B.sum<ret.Rmin.v) ret.Rmin=abcd(A.Rmin.l,B.Rmin.r,A.Rmin.v+B.sum);ret.Rmax=B.Rmax; if (A.Rmax.v+B.sum>ret.Rmax.v) ret.Rmax=abcd(A.Rmax.l,B.Rmax.r,A.Rmax.v+B.sum);if (A.Mmax.v>B.Mmax.v) ret.Mmax=A.Mmax; else ret.Mmax=B.Mmax;if (A.Rmax.v+B.Lmax.v>ret.Mmax.v) ret.Mmax=abcd(A.Rmax.l,B.Lmax.r,A.Rmax.v+B.Lmax.v);if (A.Mmin.v<B.Mmin.v) ret.Mmin=A.Mmin; else ret.Mmin=B.Mmin;if (A.Rmin.v+B.Lmin.v<ret.Mmin.v) ret.Mmin=abcd(A.Rmin.l,B.Lmin.r,A.Rmin.v+B.Lmin.v);return ret;}}T[N*4];int M,TH;void pushdown(int rt){if (T[rt].rev){T[rt].rev=0;T[rt<<1].reverse();T[rt<<1|1].reverse();}}void Build(int n,int *a){for (M=1,TH=0;M<n+2;M<<=1,TH++);for (int i=1;i<=n;i++)T[M+i]=node(i,a[i]);for (int i=M-1;i;i--)T[i]=T[i<<1]+T[i<<1|1];}void Pushdown(int rt){for (int i=TH;i;i--)pushdown(rt>>i);}void Modify(int s,int x){Pushdown(s+=M);T[s]=node(s-M,x);while (s>>=1)T[s]=T[s<<1]+T[s<<1|1];}void Reverse(int s,int t){for (Pushdown(s+=M-1),Pushdown(t+=M+1);s^t^1;){if (~s&1) T[s^1].reverse();if ( t&1) T[t^1].reverse();T[s>>=1]=T[s<<1]+T[s<<1|1];T[t>>=1]=T[t<<1]+T[t<<1|1];}while (s>>=1)T[s]=T[s<<1]+T[s<<1|1];}abcd Query(int s,int t){node lret,rret;for (Pushdown(s+=M-1),Pushdown(t+=M+1);s^t^1;s>>=1,t>>=1){if (~s&1) lret=lret+T[s^1];if ( t&1) rret=T[t^1]+rret;}return (lret+rret).Mmax;}
}Seg;int ans;
int n,a[N];
int pnt,Sl[N],Sr[N];int main()
{int Q,order,x,y,K; abcd ret;freopen("t.in","r",stdin);freopen("t.out","w",stdout);read(n);for (int i=1;i<=n;i++) read(a[i]);Seg.Build(n,a);read(Q);while (Q--){read(order);if (order==0){read(x); read(y);Seg.Modify(x,y);}else if (order==1){read(x); read(y); read(K);ans=0;for (int i=1;i<=K;i++){ret=Seg.Query(x,y);if (ret.v<=0) break;ans+=ret.v;Seg.Reverse(ret.l,ret.r);Sl[++pnt]=ret.l; Sr[pnt]=ret.r;}printf("%dn",ans);while (pnt)Seg.Reverse(Sl[pnt],Sr[pnt]),pnt--;}}return 0;
}