真是迟了好久，开始以为这个就不写辣，然而今天突然意识有一些模糊，印象有一点浅，就当复习一下
什么？四倍经验？传送门？太麻烦了不放懒
先弄个超级源，然后拆点，$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...$
评论 (0)
