【杂题】[BZOJ3272] ZGG吃东西【线段树】【贪心】

【杂题】[BZOJ3272] ZGG吃东西【线段树】【贪心】

Description

给定长度为n的序列A
m组询问，每次询问 l , r , k l,r,k l,r,k，表示在区间 [ l , r ] [l,r] [l,r]内选出至多k个不重叠的子段的最大和
n , m ≤ 100000 , k ≤ 20 n,mleq 100000,kleq 20 n,m≤100000,k≤20

Solution

五倍经验链接：
【BZOJ2288】【POJ Challenge】生日礼物
【BZOJ3267】KC采花
【BZOJ3272】Zgg吃东西
【BZOJ3502】【PA2012】Tanie linie
【BZOJ3638】k-Maximum Subsequence Sum

我们考虑可撤销贪心
每次贪心的选出区间内的最大子段，然后将这一段的贡献设为负的，以后再选到重复的就会撤销掉。

形式化的，我们循环K次，每次取区间内的最大子段，然后将这一段的权值取反，那么这一段的数下次再选到就相当于撤销了，不会有影响。

这样为什么是对的呢

考虑一种费用流做法
对于每个数，拆成入点和出点，源点向入点连(1,0)（容量为1，费用为0），出点向汇点连(1,0)
入点向出点连(1,a[i])，且每个数的出点向下一个数的入点连(1,0)，跑最大费用流，增广K次即可（或者增广路费用已经为负）

对于每一次增广，实际上就是找到区间内最大子段，然后费用会取反
因此这样是没有问题的。

用线段树维护区间最大子段，由于要支持取反所以还要维护最小子段，对于一个区间还要维护前缀最大/小子段和后缀最大/小子段以便合并。

Code

线段树维护子段是真恶心…

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fod(i,a,b) for(int i=a;i>=b;--i)
#define N 100005
#define M 200005
using namespace std;
int t[M][2],mx[M],mi[M],n1,n,a[N],d[N],da[N][2],lf[M],rt[M],lz[M];
struct node
{int lx[3],li[3],rx[3],ri[3],mx[3],mi[3],sm;
}tr[M];
void upd(int *x,int *y)
{fo(j,0,2) x[j]=y[j];
}
void inv(int k)
{swap(tr[k].lx,tr[k].li),swap(tr[k].rx,tr[k].ri),swap(tr[k].mx,tr[k].mi),tr[k].sm=-tr[k].sm;tr[k].lx[0]=-tr[k].lx[0],tr[k].rx[0]=-tr[k].rx[0],tr[k].li[0]=-tr[k].li[0],tr[k].ri[0]=-tr[k].ri[0],tr[k].mi[0]=-tr[k].mi[0],tr[k].mx[0]=-tr[k].mx[0];	
}
void down(int k)
{if(lz[k]<0){inv(t[k][0]),inv(t[k][1]);lz[t[k][0]]=-lz[t[k][0]],lz[t[k][1]]=-lz[t[k][1]];}lz[k]=1;
}
node merge(node x,node y)
{node z;,x.mx),upd(z.mi,x.mi);z.sm=x.sm+y.sm;int l=x.lx[1],mid&#[2],r&#[2];[0]&[0]) ,y.mx);[0]&[0]+y.lx[0]) z.mx[0]&#[0]+y.lx[0],z.mx[1]&#[1],z.mx[2]=y.lx[2];if(z.mi[0]>y.mi[0]) upd(z.mi,y.mi);if(z.mi[0]>x.ri[0]+y.li[0]) z.mi[0]=x.ri[0]+y.li[0],z.mi[1]=x.ri[1],z.mi[2]=y.li[2];upd(z.lx,x.lx),upd(z.li,x.li),upd(z.ri,y.ri),,y.rx);if(x.sm+y.lx[0]>=z.lx[0]) z.lx[0]=x.sm+y.lx[0],z.lx[2]=y.lx[2];if(x.sm+y.li[0]<=z.li[0]) z.li[0]=x.sm+y.li[0],z.li[2]=y.li[2];if(y.sm&#[0]>&#[0]) z.rx[0]=y.sm&#[0],z.rx[1]&#[1];if(y.sm+x.ri[0]<=z.ri[0]) z.ri[0]=y.sm+x.ri[0],z.ri[1]=x.ri[1];return z;
}
void up(int k)
{tr[k]=merge(tr[t[k][0]],tr[t[k][1]]);
}
void ins(int k,int l,int r,int x)
{if(l==r) tr[k]=(node){{a[l],l,l},{a[l],l,l},{a[l],l,l},{a[l],l,l},{a[l],l,l},{a[l],l,l},a[l]};else{int mid=(l+r)>>1;down(k);if(x<=mid) ins(t[k][0],l,mid,x);else ins(t[k][1],mid+1,r,x);up(k);}
}
void build(int k,int l,int r)
{lz[k]=1;if(l==r) {tr[k]=(node){{a[l],l,l},{a[l],l,l},{a[l],l,l},{a[l],l,l},{a[l],l,l},{a[l],l,l},a[l]};return;}int mid=(l+r)>>1;build(t[k][0]=++n1,l,mid);build(t[k][1]=++n1,mid+1,r);up(k);
}
void rev(int k,int l,int r,int x,int y)
{if(x>y||x>r||y<l) return;if(x<=l&&r<=y) {inv(k),lz[k]=-lz[k];return;}int mid=(l+r)>>1;down(k);rev(t[k][0],l,mid,x,y),rev(t[k][1],mid+1,r,x,y);up(k);
}
void query(int k,int l,int r,int x,int y)
{if(x>y||x>r||y<l) return;if(x<=l&&r<=y) {d[++d[0]]=k;return;}int mid=(l+r)>>1;down(k);query(t[k][0],l,mid,x,y),query(t[k][1],mid+1,r,x,y);
}
int main()
{cin>>n;fo(i,1,n) scanf("%d",&a[i]);n1=1;build(1,1,n);int q;cin>>q;fo(i,1,q){int p,x,y,z;scanf("%d%d%d",&p,&x,&y);if(p==0) a[x]=y,ins(1,1,n,x);else{scanf("%d",&z);int j=1,ans=0,cnt=0;fo(j,1,z){d[0]=0;query(1,1,n,x,y);node sq=tr[d[1]];fo(p,2,d[0]) sq=merge(sq,tr[d[p]]);[0]<=0) break;	da[++cnt][0]&#[1],da[cnt][1]&#[2];rev(1,1,n,da[cnt][0],da[cnt][1]);ans+&#[0];}printf("%dn",ans);fod(j,cnt,1) rev(1,1,n,da[j][0],da[j][1]);}}
}