题目大意
给定一个长为n的序列,维护两种操作:
1.单点修改 2.在[l,r]这段区间中取k个互不相交的子段,使子段之和最大.\(n \leq 50000,k \leq 20\)
题解
四倍经验.(但我的写法太丑过不了3502)
我们可以很简单地构建出一个最大费用最大流模型 把每个点拆点,然后S,T分别连接即可 但是这道题n达到50000,直接上费用流绝对T的不要不要的 我们想一下这样费用流的时候都在干什么 每次找出一个费用最大的区间...把答案加上费用之和...把所有的费用取反... 我们发现我们可以用线段树维护这个过程! 支持最大子段和查询和反转操作 所以我们维护一个最大子段和和最小子段和即可！！ 啥？好像好要维护取到最大子段和和最小子段和时的端点？ 啥？要维护从左端点的开始的最大子段和和从右端点开始的最大子段和？ 好麻烦啊。。。估计是我写丑了...所以3502才被卡空间了...Code
#include#include #include using namespace std;typedef long long ll;inline void read(int &x){ x=0;char ch;bool flag = false; while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true; while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;}inline int cat_max(const int &a,const int &b){return a>b ? a:b;}inline int cat_min(const int &a,const int &b){return a > 1; build(rt<<1,l,mid);build(rt<<1|1,mid+1,r); T[rt] = T[rt<<1] + T[rt<<1|1];}void modify(int rt,int l,int r,int pos,int val){ if(l == r){ T[rt].set(val,l); return; } int mid = l+r >> 1; pushdown(rt,l,r); if(pos <= mid) modify(rt<<1,l,mid,pos,val); else modify(rt<<1|1,mid+1,r,pos,val); T[rt] = T[rt<<1] + T[rt<<1|1];}Node query(int rt,int l,int r,int L,int R){ if(L <= l && r <= R) return T[rt]; int mid = l+r >> 1; pushdown(rt,l,r); if(R <= mid) return query(rt<<1,l,mid,L,R); if(L > mid) return query(rt<<1|1,mid+1,r,L,R); return query(rt<<1,l,mid,L,R) + query(rt<<1|1,mid+1,r,L,R);}void rever(int rt,int l,int r,int L,int R){ if(L <= l && r <= R){T[rt].reve();return;} int mid = l+r >> 1; pushdown(rt,l,r); if(L <= mid) rever(rt<<1,l,mid,L,R); if(R > mid) rever(rt<<1|1,mid+1,r,L,R); T[rt] = T[rt<<1] + T[rt<<1|1];}struct seg{ int l,r; seg(int l=0,int r=0){this->l=l;this->r=r;}}sta[22];int top,n;inline int spfa(int l,int r,int num){ top = 0;int ret = 0; while(num--){ Node x = query(1,1,n,l,r); if(x.mx < 0) break; sta[++top] = seg(x.lx,x.rx); ret += x.mx; rever(1,1,n,x.lx,x.rx); } while(top){ rever(1,1,n,sta[top].l,sta[top].r); --top; } return ret;}int main(){ read(n); for(int i=1;i<=n;++i) read(a[i]); build(1,1,n); int m;read(m); int op,l,r,k; while(m--){ read(op);read(l);read(r); if(op == 0){ modify(1,1,n,l,r); }else{ read(k); printf("%d\n",spfa(l,r,k)); } } getchar();getchar(); return 0;}