BZOJ3267/3272 KC采花/Zgg吃东西（线段树）

BZOJ3267/3272 KC采花/Zgg吃东西（线段树）

　　直接维护选k个子段时的最优解似乎也可以做，然而复杂度是O(nk²logn)，显然跑不过。

　　考虑一种费用流做法。序列里每个点拆成入点和出点，源连入汇连出，入点和出点间连流量1费用a_i的边，相邻点出点向入点连流量1费用0的边，整体限流k。

　　直接跑当然还不如暴力。观察一下这个做法是在干啥：每次选择费用最大的一段，然后利用反向边将这一段的费用取反。

　　这个做法看起来非常贪心（不过费用流本质上也挺贪心的），不过看起来确实是对的。当然从贪心角度就完全不会证了。

　　于是考虑利用这种做法维护。那么线段树维护区间最大子段和和最小子段和，取反时交换，剩下的是基本操作了。

#include<iostream> 
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int read()
{int x=0,f=1;char c=getchar();while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f;
}
#define N 100010
int n,m,a[N];
struct data{int L,R,max,maxl,maxr,min,minl,minr,sum,rmax,rmaxid,rmin,rminid,lmax,lmaxid,lmin,lminid,rev;
}tree[N<<2],q[22];
data merge(data a,data b)
{data v=0;u.L=a.L,u.R=b.R;u.sum=a.sum+b.sum;if (a.lmax>a.sum+b.lmax) u.lmax=a.lmax,u.lmaxid=a.lmaxid;else u.lmax=a.sum+b.lmax,u.lmaxid=b.lmaxid;if (a.lmin<a.sum+b.lmin) u.lmin=a.lmin,u.lminid=a.lminid;else u.lmin=a.sum+b.lmin,u.lminid=b.lminid;if (b.rmax>b.sum&#ax) u.rmax&#axid&#axid;ax=b.sum&#axid&#axid;if (b.rmin<b.sum&#in) u.rmin&#inid&#inid;in=b.sum&#inid&#inid;u.max&#ax+b.lmax;u.maxl&#axid;u.maxr=b.lmaxid;u.min&#in+b.lmin;u.minl&#inid;u.minr=b.lminid;if (a.max>u.max) u.max=a.max,u.maxl=a.maxl,u.maxr=a.maxr;if (a.min<u.min) u.min=a.min,u.minl=a.minl,u.minr=a.minr;if (b.max>u.max) u.max=b.max,u.maxl=b.maxl,u.maxr=b.maxr;if (b.min<u.min) u.min=b.min,u.minl=b.minl,u.minr=b.minr;return u;
}
void work(int k)
{tree[k].rev^=1;tree[k].sum=-tree[k].sum;swap(tree[k].max,tree[k].min);tree[k].max=-tree[k].max,tree[k].min=-tree[k].min;swap(tree[k].maxl,tree[k].minl);swap(tree[k].maxr,tree[k].minr);swap(tree[k].lmax,tree[k].lmin);tree[k].lmax=-tree[k].lmax,tree[k].lmin=-tree[k].lmin;swap(tree[k].lmaxid,tree[k].lminid);swap(tree[k].rmax,tree[k].rmin);tree[k].rmax=-tree[k].rmax,tree[k].rmin=-tree[k].rmin;swap(tree[k].rmaxid,tree[k].rminid);
}
void down(int k){work(k<<1),work(k<<1|1),tree[k].rev=0;}
void build(int k,int l,int r)
{tree[k].L=l,tree[k].R=r;if (l==r){tree[k].sum=tree[k].max=tree[k].min=tree[k].rmax=tree[k].rmin=tree[k].lmax=tree[k].lmin=a[l];tree[k].maxl=tree[k].maxr=tree[k].minl=tree[k].minr=tree[k].rmaxid=tree[k].rminid=tree[k].lmaxid=tree[k].lminid=l;return;}int mid=l+r>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r);tree[k]=merge(tree[k<<1],tree[k<<1|1]);
}
void rev(int k,int l,int r)
{if (tree[k].L==l&&tree[k].R==r) {work(k);return;}if (tree[k].rev) down(k);int mid=tree[k].L+tree[k].R>>1;if (r<=mid) rev(k<<1,l,r);else if (l>mid) rev(k<<1|1,l,r);else rev(k<<1,l,mid),rev(k<<1|1,mid+1,r);tree[k]=merge(tree[k<<1],tree[k<<1|1]);
}
void modify(int k,int p,int x)
{if (tree[k].L==tree[k].R){tree[k].sum=tree[k].max=tree[k].min=tree[k].rmax=tree[k].rmin=tree[k].lmax=tree[k].lmin=x;tree[k].rev=0;return;}if (tree[k].rev) down(k);int mid=tree[k].L+tree[k].R>>1;if (p<=mid) modify(k<<1,p,x);else modify(k<<1|1,p,x);tree[k]=merge(tree[k<<1],tree[k<<1|1]);
}
data query(int k,int l,int r)
{if (tree[k].L==l&&tree[k].R==r) return tree[k];if (tree[k].rev) down(k);int mid=tree[k].L+tree[k].R>>1;if (r<=mid) return query(k<<1,l,r);else if (l>mid) return query(k<<1|1,l,r);else return merge(query(k<<1,l,mid),query(k<<1|1,mid+1,r));
}
int main()
{
#ifndef ONLINE_JUDGEfreopen("bzoj3272.in","r",stdin);freopen("bzoj3272.out","w",stdout);const char LL[]="%I64dn";
#elseconst char LL[]="%lldn";
#endifn=read();for (int i=1;i<=n;i++) a[i]=read();m=read();build(1,1,n);while (m--){int op=read();if (op){int l=read(),r=read(),k=read(),ans=0;for (int i=1;i<=k;i++){q[i]=query(1,l,r);if (q[i].max>0) ans+=q[i].max,rev(1,q[i].maxl,q[i].maxr);else {k=i-1;break;}}for (int i=1;i<=k;i++)rev(1,q[i].maxl,q[i].maxr);printf("%dn",ans);}else{int x=read(),y=read();modify(1,x,y);}}return 0;
}

转载于:.html