题目大意
给定一个长为n的序列,维护两种操作:
1.单点修改
2.在[l,r]这段区间中取k个互不相交的子段,使子段之和最大.
(n leq 50000,k leq 20)
题解
四倍经验.(但我的写法太丑过不了3502)
我们可以很简单地构建出一个最大费用最大流模型
把每个点拆点,然后S,T分别连接即可
但是这道题n达到50000,直接上费用流绝对T的不要不要的
我们想一下这样费用流的时候都在干什么
每次找出一个费用最大的区间...把答案加上费用之和...把所有的费用取反...
我们发现我们可以用线段树维护这个过程!
支持最大子段和查询和反转操作
所以我们维护一个最大子段和和最小子段和即可！！
啥？好像好要维护取到最大子段和和最小子段和时的端点？
啥？要维护从左端点的开始的最大子段和和从右端点开始的最大子段和？
好麻烦啊。。。估计是我写丑了...所以3502才被卡空间了...
Code
#include <cstdio>
#include <cstring>
#include <algorithm>
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<b ? a:b;}
const int maxn = 100010;
const int inf = 0x3f3f3f3f;
struct Node{
int mx,lmx,rmx,lx,rx,plx,prx;
int mn,lmn,rmn,ln,rn,pln,prn;
int sum,rev;
Node(){
mx = lmx = rmx = -inf;
mn = lmn = rmn = inf;
sum = lx = rx = ln = rn = rev = 0;
}
inline void set(int x,int p){
rev = 0;mx = lmx = rmx = mn = lmn = rmn = sum = x;
lx=rx=plx=prx=ln=rn=pln=prn = p;
}
inline void reve(){
swap(mx,mn);swap(lmn,lmx);swap(rmn,rmx);
swap(lx,ln);swap(rx,rn);swap(plx,pln);swap(prx,prn);
mx = -mx;mn = -mn;
lmn = -lmn;lmx = -lmx;
rmx = -rmx;rmn = -rmn;
sum = -sum;rev ^= 1;
}
Node friend operator + (const Node &l,const Node &r){
Node c;
c.sum = l.sum + r.sum;
c.lmx = max(l.lmx,l.sum+max(r.lmx,0));
c.rmx = max(r.rmx,r.sum+max(l.rmx,0));
c.mx = max(max(l.mx,r.mx),max(l.rmx+max(0,r.lmx),max(l.rmx,0)+r.lmx) );
if(c.lmx == l.lmx) c.plx = l.plx;
else c.plx = r.plx;
if(c.rmx == r.rmx) c.prx = r.prx;
else c.prx = l.prx;
if(c.mx == l.mx) c.lx = l.lx,c.rx = l.rx;
else if(c.mx == r.mx) c.lx = r.lx,c.rx = r.rx;
else if(c.mx == l.rmx+r.lmx)c.lx = l.prx,c.rx = r.plx;
c.lmn = min(l.lmn,l.sum+min(r.lmn,0));
c.rmn = min(r.rmn,r.sum+min(l.rmn,0));
c.mn = min(min(l.mn,r.mn),min(l.rmn+min(0,r.lmn),min(l.rmn,0)+r.lmn) );
if(c.lmn == l.lmn) c.pln = l.pln;
else c.pln = r.pln;
if(c.rmn == r.rmn) c.prn = r.prn;
else c.prn = l.prn;
if(c.mn == l.mn) c.ln = l.ln,c.rn = l.rn;
else if(c.mn == r.mn) c.ln = r.ln,c.rn = r.rn;
else if(c.mn == l.rmn+r.lmn) c.ln = l.prn,c.rn = r.pln;
}
}T[maxn<<2];
int a[maxn];
inline void pushdown(int rt,int l,int r){
if(T[rt].rev == 0) return;
T[rt].rev = 0;
if(l == r) return;
T[rt<<1].reve();T[rt<<1|1].reve();
}
void build(int rt,int l,int r){
if(l == r){
T[rt].set(a[l],l);
return;
}int mid = l+r >> 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
",spfa(l,r,k));
}
}
getchar();getchar();
return 0;
}