题目分析：
（可能是刚做完毒瘤 Ynoi 的原因，看这个 4k 的线段树感觉好简单）
可以看一下这个查询的操作，最多 \(k\) 个不重线段的和的最大值，这个东西大概是网络流的经典题吧。
具体做法就是 \(S\) 向 \(i\) 连流量为 \(1\) 费用为 \(0\) 的边，\(i\) 向 \(T\) 连流量为 \(1\) 费用为 \(0\) 的边，\(i\) 向 \(i+1\) 连流量为 \(1\) 费用为 \(a_i\) 的边。这样我们每次多一点流量，就意味着多选择一个区间，因为区间必然不可能相互包含。
我们费用流其实每次就是找一个最优的增广路然后去增广啊，而一条增广路也就必然对应了一段区间，如果增广路包含之前选择过的点其实就是意味着走反向边。也就是说，如果我们先选择了 \([1,3]\) 然后选择了 \([3,5]\)，那么我们实际选择的区间就是 \([1,2]\) 和 \([4,5]\)。
那么这个题的思路就很清晰了。每次最优的增广路其实就是意味着区间最大子段和，而选择一条增广路就意味着区间取反，就很好维护了。
代码：
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
struct sgement{
int l,r,sum;
};
sgement operator + (sgement a,sgement b){
return {a.l,b.r,a.sum + b.sum};
}
bool operator < (sgement a,sgement b){
return a.sum < b.sum;
}
struct node{
sgement sum,lmx,rmx,mx,lmn,rmn,mn;
}t[4 * N];
bool tag[4*N];
int a[N];
node merge(node a,node b){
node c;
c.sum = a.sum + b.sum;
c.lmx = max(a.lmx,a.sum + b.lmx);
c.rmx = max(b.rmx,a.rmx + b.sum);
c.mx = max(max(a.mx,b.mx),a.rmx + b.lmx);
c.lmn = min(a.lmn,a.sum + b.lmn);
c.rmn = min(b.rmn,a.rmn + b.sum);
c.mn = min(min(a.mn,b.mn),a.rmn + b.lmn);
return c;
}
void rever(int now){
t[now].sum.sum = -t[now].sum.sum;
t[now].mx.sum = -t[now].mx.sum;
t[now].mn.sum = -t[now].mn.sum;
t[now].lmx.sum = -t[now].lmx.sum;
t[now].rmx.sum = -t[now].rmx.sum;
t[now].lmn.sum = -t[now].lmn.sum;
t[now].rmn.sum = -t[now].rmn.sum;
swap(t[now].mx,t[now].mn);swap(t[now].lmx,t[now].lmn);swap(t[now].rmx,t[now].rmn);
tag[now] ^= 1;
}
void pushdown(int now){
if(tag[now]){
rever(now<<1);rever(now<<1|1);
tag[now] = false;
}
}
void rev(int now,int now_l,int now_r,int l,int r){
if(l <= now_l && r >= now_r){
rever(now);
return;
}
pushdown(now);
int mid = (now_l + now_r)>>1;
if(l <= mid) rev(now<<1,now_l,mid,l,r);
if(r > mid) rev(now<<1|1,mid+1,now_r,l,r);
t[now] = merge(t[now<<1],t[now<<1|1]);
}
void modify(int now,int now_l,int now_r,int pos,int val){
if(now_l == now_r){
t[now].sum.sum = val;
t[now].lmx.sum = max(val,0);t[now].rmx.sum = max(val,0);t[now].mx.sum = max(val,0);
t[now].lmn.sum = min(val,0);t[now].rmn.sum = min(val,0);t[now].mn.sum = min(val,0);
return;
}
pushdown(now);
int mid = (now_l + now_r)>>1;
if(pos <= mid) modify(now<<1,now_l,mid,pos,val);
if(pos > mid) modify(now<<1|1,mid+1,now_r,pos,val);
t[now] = merge(t[now<<1],t[now<<1|1]);
}
node query(int now,int now_l,int now_r,int l,int r){
if(l <= now_l && r >= now_r) return t[now];
pushdown(now);
int mid = (now_l + now_r)>>1;
if(r <= mid) return query(now<<1,now_l,mid,l,r);
if(l > mid) return query(now<<1|1,mid+1,now_r,l,r);
return merge(query(now<<1,now_l,mid,l,r),query(now<<1|1,mid+1,now_r,l,r));
}
void build(int now,int now_l,int now_r){
if(now_l == now_r){
t[now].sum = {now_l,now_l,a[now_l]};
t[now].lmx = {now_l,now_l,max(a[now_l],0)};
t[now].rmx = {now_l,now_l,max(a[now_l],0)};
t[now].mx = {now_l,now_l,max(a[now_l],0)};
t[now].lmn = {now_l,now_l,min(a[now_l],0)};
t[now].rmn = {now_l,now_l,min(a[now_l],0)};
t[now].mn = {now_l,now_l,min(a[now_l],0)};
return;
}
int mid = (now_l + now_r)>>1;
build(now<<1,now_l,mid);build(now<<1|1,mid+1,now_r);
t[now] = merge(t[now<<1],t[now<<1|1]);
}
int main(){
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int n;scanf("%d",&n);
for(int i=1; i<=n; i++) scanf("%d",&a[i]);
build(1,1,n);
int m;scanf("%d",&m);
for(int i=1; i<=m; i++){
int opt;scanf("%d",&opt);
if(opt == 0){
int x,y;scanf("%d%d",&x,&y);
modify(1,1,n,x,y);
}
else{
int l,r,k;scanf("%d%d%d",&l,&r,&k);
int ans = 0;
vector<node> v;
while(k--){
node p = query(1,1,n,l,r);
if(p.mx.sum <= 0) break;
v.push_back(p);
ans += p.mx.sum;
rev(1,1,n,p.mx.l,p.mx.r);
}
for(auto i : v) rev(1,1,n,i.mx.l,i.mx.r);
v.clear();
printf("%d\n",ans);
}
}
return 0;
}