真是迟了好久，开始以为这个就不写辣，然而今天突然意识有一些模糊，印象有一点浅，就当复习一下
什么？四倍经验？传送门？太麻烦了不放懒
先弄个超级源，然后拆点，A−>A′，向A连容量为1费用为0的边，A−>A′连容量为1费用为权值的边，然后所有A′向超级汇连边，对于相邻的A,B，A′−>B连容量1费用0的边，题目就转化成了增广k的费用流问题
考虑线段树优化，也就是区间最大子串，模拟增广过程，每次找到最大子串将这个区间取反，做k次，如果一次增广ans为0那就停下
然而事情并没有那么简单，因为要取反所以要记下该最大子串的左右端点，以为只要维护最大子串就足够了吗？naive!因为要取反。。所以取反后的子串就是原来的最小子串_(:зゝ∠)_，所以还要记最小子串，这样算下来一共16个标记，我不知道有没有更简洁的做法。。总之跑的慢是事实
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 | #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 100010const 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,rstruct 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内存不够，于是就使一使
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 | #include<cstring>#include<cstdio>#include<algorithm>using namespace std;#define S 100000char 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 longconst 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,rstruct 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)
