4
11
2016
0

[bzoj]3272&3502&3638&3267: Cf172 k-Maximum Subsequence Sum

真是迟了好久,开始以为这个就不写辣,然而今天突然意识有一些模糊,印象有一点浅,就当复习一下

什么?四倍经验?传送门?太麻烦了不放


先弄个超级源,然后拆点,$A->A'$,向$A$连容量为$1$费用为$0$的边,$A->A'$连容量为$1$费用为权值的边,然后所有$A'$向超级汇连边,对于相邻的$A,B$$A'->B$连容量$1$费用$0$的边,题目就转化成了增广$k$的费用流问题

考虑线段树优化,也就是区间最大子串,模拟增广过程,每次找到最大子串将这个区间取反,做$k$次,如果一次增广$ans$$0$那就停下

然而事情并没有那么简单,因为要取反所以要记下该最大子串的左右端点,以为只要维护最大子串就足够了吗?$naive!$因为要取反。。所以取反后的子串就是原来的最小子串_(:зゝ∠)_,所以还要记最小子串,这样算下来一共$16$个标记,我不知道有没有更简洁的做法。。总之跑的慢是事实

#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define nc() getchar()
inline int read(){
	int f=1,x=0;char ch=nc();for(;(ch<'0'||ch>'9')&&(ch!='-');ch=nc());
	if(ch=='-')ch=nc(),f=-1;for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x*f;
}
#define N 100010
const int oo=1<<30;
int i,j,k,m,n,x[21],y[21],a[N],f,cnt,l,r,L,R,V,ans;
#define lson k<<1,l,m
#define rson k<<1|1,m+1,r
struct tree{
	int xls,xrs,nls,nrs,mxs,mns,mxl,mnl,mxr,mnr,s,pnrs,pxrs,pnls,pxls;bool flg;
	inline void nw(){xls=xrs=mxs=-oo,nls=nrs=mns=oo,mxl=mnl=mxr=mnr=pnrs=pnls=pxls=pxrs=flg=s=0;}
	inline void sap(){
		flg^=1,swap(xls,nls),swap(xrs,nrs),swap(mxs,mns),swap(mxl,mnl),swap(mxr,mnr),swap(pnrs,pxrs),swap(pnls,pxls);
		s*=-1,xls*=-1,nls*=-1,xrs*=-1,nrs*=-1,mxs*=-1,mns*=-1;
	}
}T[N<<2],z;
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
inline int mx(int&o,int a,int b,int pl,int pr){return a>b?(o=pl,a):(o=pr,b);}
inline int Mx(int&l,int&r,int a,int b,int pal,int par,int pbl,int pbr){return a>b?(l=pal,r=par,a):(l=pbl,r=pbr,b);}
inline int mn(int&o,int a,int b,int pl,int pr){return a<b?(o=pl,a):(o=pr,b);}
inline int Mn(int&l,int&r,int a,int b,int pal,int par,int pbl,int pbr){return a<b?(l=pal,r=par,a):(l=pbl,r=pbr,b);}
inline tree operator+(const tree&l,const tree&r){
	if(l.mxl==0)return r;if(r.mxl==0)return l;tree f;f.flg=0;
	f.s=l.s+r.s,f.xls=mx(f.pxls,l.xls,l.s+r.xls,l.pxls,r.pxls);
	f.xrs=mx(f.pxrs,r.xrs,l.xrs+r.s,r.pxrs,l.pxrs);
	f.mxs=Mx(f.mxl,f.mxr,l.mxs,r.mxs,l.mxl,l.mxr,r.mxl,r.mxr);
	f.mxs=Mx(f.mxl,f.mxr,f.mxs,l.xrs+r.xls,f.mxl,f.mxr,l.pxrs,r.pxls);
	f.nls=mn(f.pnls,l.nls,l.s+r.nls,l.pnls,r.pnls);
	f.nrs=mn(f.pnrs,r.nrs,l.nrs+r.s,r.pnrs,l.pnrs);
	f.mns=Mn(f.mnl,f.mnr,l.mns,r.mns,l.mnl,l.mnr,r.mnl,r.mnr);
	f.mns=Mn(f.mnl,f.mnr,f.mns,l.nrs+r.nls,f.mnl,f.mnr,l.pnrs,r.pnls);return f;
}
void build(int k,int l,int r){
	T[k].nw();if(l==r){T[k]=(tree){a[l],a[l],a[l],a[l],a[l],a[l],l,l,l,l,a[l],l,l,l,l,0};return;}
	int m=l+r>>1;build(lson),build(rson),T[k]=T[k<<1]+T[k<<1|1];
}
#define down(k) (T[k<<1].sap(),T[k<<1|1].sap(),T[k].flg=0)
void change(int k,int l,int r){
	if(l==L&&r==L){T[k]=(tree){V,V,V,V,V,V,l,l,l,l,V,l,l,l,l,0};return;}
	if(T[k].flg)down(k);int m=l+r>>1;
	if(L<=m)change(lson);else change(rson);
	T[k]=T[k<<1]+T[k<<1|1];
}
tree ask(int k,int l,int r){
	if(l>=L&&r<=R)return T[k];
	if(T[k].flg)down(k);int m=l+r>>1;tree ans;ans.nw();
	if(L<=m)ans=ask(lson);if(R>m)ans=ans+ask(rson);return ans;
}
void reverse(int k,int l,int r,int L,int R){
	if(l>=L&&r<=R){T[k].sap();return;}
	if(T[k].flg)down(k);int m=l+r>>1;
	if(L<=m)reverse(lson,L,R);if(R>m)reverse(rson,L,R);T[k]=T[k<<1]+T[k<<1|1];
}
int main(){
	for(n=read(),i=1;i<=n;++i)a[i]=read();
	for(build(1,1,n),m=read();m--;){
		if(f=read()){
			L=read(),R=read(),k=read(),cnt=ans=0;
			while(k--){
				z=ask(1,1,n);if(z.mxs<=0)break;
				ans+=z.mxs,x[++cnt]=z.mxl,y[cnt]=z.mxr;
				reverse(1,1,n,x[cnt],y[cnt]);
			}
			printf("%d\n",ans);
			for(;cnt;--cnt)reverse(1,1,n,x[cnt],y[cnt]);
		}else L=read(),V=read(),change(1,1,n);
	}
}

$3502$要开$long$ $long$,然后!$F*k$内存不够,于是就使一使

#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define S 100000
char bf[S],*p1=bf,*p2=bf;
#define nc() (p1==p2&&(p2=(p1=bf)+fread(bf,1,S,stdin),p2==p1)?-1:*p1++)
inline int read(){
	int f=1,x=0;char ch=nc();for(;(ch<'0'||ch>'9')&&(ch!='-');ch=nc());
	if(ch=='-')ch=nc(),f=-1;for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x*f;
}
#define N 1000010
#define ll long long
const int oo=1<<30;
int i,j,k,m,n,a[N],f,cnt,l,r,L,R,V;ll ans;
#define lson k<<1,l,m
#define rson k<<1|1,m+1,r
struct tree{
	ll xls,xrs,nls,nrs,mxs,mns;int mxl,mnl,mxr,mnr;ll s;int pnrs,pxrs,pnls,pxls;bool flg;
	inline void nw(){xls=xrs=mxs=-oo,nls=nrs=mns=oo,mxl=mnl=mxr=mnr=pnrs=pnls=pxls=pxrs=flg=s=0;}
	inline void sap(){
		flg^=1,swap(xls,nls),swap(xrs,nrs),swap(mxs,mns),swap(mxl,mnl),swap(mxr,mnr),swap(pnrs,pxrs),swap(pnls,pxls);
		s*=-1,xls*=-1,nls*=-1,xrs*=-1,nrs*=-1,mxs*=-1,mns*=-1;
	}
}T[N*2+200000],z;
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
inline ll mx(int&o,ll a,ll b,int pl,int pr){return a>b?(o=pl,a):(o=pr,b);}
inline ll Mx(int&l,int&r,ll a,ll b,int pal,int par,int pbl,int pbr){return a>b?(l=pal,r=par,a):(l=pbl,r=pbr,b);}
inline ll mn(int&o,ll a,ll b,int pl,int pr){return a<b?(o=pl,a):(o=pr,b);}
inline ll Mn(int&l,int&r,ll a,ll b,int pal,int par,int pbl,int pbr){return a<b?(l=pal,r=par,a):(l=pbl,r=pbr,b);}
inline tree operator+(const tree&l,const tree&r){
	if(l.mxl==0)return r;if(r.mxl==0)return l;tree f;f.flg=0;
	f.s=l.s+r.s,f.xls=mx(f.pxls,l.xls,l.s+r.xls,l.pxls,r.pxls);
	f.xrs=mx(f.pxrs,r.xrs,l.xrs+r.s,r.pxrs,l.pxrs);
	f.mxs=Mx(f.mxl,f.mxr,l.mxs,r.mxs,l.mxl,l.mxr,r.mxl,r.mxr);
	f.mxs=Mx(f.mxl,f.mxr,f.mxs,l.xrs+r.xls,f.mxl,f.mxr,l.pxrs,r.pxls);
	f.nls=mn(f.pnls,l.nls,l.s+r.nls,l.pnls,r.pnls);
	f.nrs=mn(f.pnrs,r.nrs,l.nrs+r.s,r.pnrs,l.pnrs);
	f.mns=Mn(f.mnl,f.mnr,l.mns,r.mns,l.mnl,l.mnr,r.mnl,r.mnr);
	f.mns=Mn(f.mnl,f.mnr,f.mns,l.nrs+r.nls,f.mnl,f.mnr,l.pnrs,r.pnls);return f;
}
void build(int k,int l,int r){
	if(l==r){T[k]=(tree){a[l],a[l],a[l],a[l],a[l],a[l],l,l,l,l,a[l],l,l,l,l,0};return;}
	int m=l+r>>1;build(lson),build(rson),T[k]=T[k<<1]+T[k<<1|1];
}
#define down(k) (T[k<<1].sap(),T[k<<1|1].sap(),T[k].flg=0)
tree ask(int k,int l,int r){
	if(l>=L&&r<=R)return T[k];
	if(T[k].flg)down(k);int m=l+r>>1;tree ans;ans.nw();
	if(L<=m)ans=ask(lson);if(R>m)ans=ans+ask(rson);return ans;
}
void reverse(int k,int l,int r,int L,int R){
	if(l>=L&&r<=R){T[k].sap();return;}
	if(T[k].flg)down(k);int m=l+r>>1;
	if(L<=m)reverse(lson,L,R);if(R>m)reverse(rson,L,R);T[k]=T[k<<1]+T[k<<1|1];
}
int main(){
	for(n=read(),k=read(),i=1;i<=n;++i)a[i]=read();
	build(1,1,n),L=1,R=n;
	while(k--){
		z=ask(1,1,n);if(z.mxs<=0)break;
		ans+=z.mxs,reverse(1,1,n,z.mxl,z.mxr);
	}
	printf("%lld\n",ans);
}

 

$loading...$

Category: bzoj | Tags: 线段树优化费用流 | Read Count: 585

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com