k-Maximum Subsequence Sum(线段树,巨多懒标记)

题目

CF

$1\le n,m\le 10^5,|a_i|\le 500,1\le k\le 20$

思路

很神奇。。。
我们考虑网络流建图大概是这样:

但是这样不仅点多，而且每次还要重新做，会T掉
但是我们模拟增广过程会发现我们每次选择最长路后将所选区间的边权取反后又求最长路，这给了我们启发，(我觉得这道题想不到网络流简直不可做)
我们知道线段树是可以求区间最值的，于是我们维护很多一些信息就可以了（不多，才18个）

$l,r,sum$ ：左右端点，区间和
$lazy$：取反标记
$maxs,maxsl,maxsr$： 区间最大和,区间最大和的左右端点
$mins,minsl,minsr$： 区间最小和,区间最小和的左右端点
$maxl,maxlp$： 区间最大前缀和,以及前缀和右端点
$minl,minlp$ ：区间最小前缀和,以及前缀和右端点
$maxr,maxrp$： 区间最大后缀和,以及后缀和左端点
$minr,minrp$： 区间最小后缀和,以及后缀和左端点
维护好这些信息就可以有求区间最值，边权取反的操作了，说白了就是用线段树来实现网络流加速(利用序列有连续性的性质)

思考

//#pragma GCC optimize(2)
#include<set>
#include<map>
#include<stack>
#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include<climits>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define LL long long
using namespace std;
int read(){
    bool f=0;int x=0;char c=getchar();while(c<'0'||'9'<c){
    if(c=='-')f=1;c=getchar();}while('0'<=c&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();return !f?x:-x;
}
#define lch (rt<<1)
#define rch (rt<<1|1)
#define MAXN 100000
#define INF 0x3f3f3f3f
namespace SegmentTree{
    struct node{
    int l,r,sum;bool lazy;//取反标记int maxs,maxsl,maxsr;//区间最大和,区间最大和的左右端点int mins,minsl,minsr;//区间最小和,区间最小和的左右端点int maxl,maxlp;//区间最大前缀和,以及前缀和右端点int minl,minlp;//区间最小前缀和,以及前缀和右端点int maxr,maxrp;//区间最大后缀和,以及后缀和左端点int minr,minrp;//区间最小后缀和,以及后缀和左端点friend node operator + (node A,node B){
    node C={
    A.l,B.r,A.sum+B.sum,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},tmp;if(max(A.maxs,B.maxs)>A.maxr+B.maxl){
    tmp=(A.maxs>B.maxs?A:B);C.maxs=tmp.maxs,C.maxsl=tmp.maxsl,C.maxsr=tmp.maxsr;}else C.maxs=A.maxr+B.maxl,C.maxsl=A.maxrp,C.maxsr=B.maxlp;if(min(A.mins,B.mins)<A.minr+B.minl){
    tmp=(A.mins<B.mins?A:B);C.mins=tmp.mins,C.minsl=tmp.minsl,C.minsr=tmp.minsr;}else C.mins=A.minr+B.minl,C.minsl=A.minrp,C.minsr=B.minlp;if(A.sum+B.maxl>A.maxl)C.maxl=A.sum+B.maxl,C.maxlp=B.maxlp;else C.maxl=A.maxl,C.maxlp=A.maxlp;if(A.sum+B.minl<A.minl)C.minl=A.sum+B.minl,C.minlp=B.minlp;else C.minl=A.minl,C.minlp=A.minlp;if(B.sum+A.maxr>B.maxr)C.maxr=B.sum+A.maxr,C.maxrp=A.maxrp;else C.maxr=B.maxr,C.maxrp=B.maxrp;if(B.sum+A.minr<B.minr)C.minr=B.sum+A.minr,C.minrp=A.minrp;else C.minr=B.minr,C.minrp=B.minrp;return C;}}tree[5*MAXN+5];inline void re(register int &x){
    x=-x;}void Reverse(int rt){
    re(tree[rt].sum);swap(tree[rt].maxs,tree[rt].mins);re(tree[rt].maxs),re(tree[rt].mins);swap(tree[rt].maxsl,tree[rt].minsl);swap(tree[rt].maxsr,tree[rt].minsr);swap(tree[rt].maxl,tree[rt].minl);re(tree[rt].maxl),re(tree[rt].minl);swap(tree[rt].maxlp,tree[rt].minlp);swap(tree[rt].maxr,tree[rt].minr);re(tree[rt].maxr),re(tree[rt].minr);swap(tree[rt].maxrp,tree[rt].minrp);tree[rt].lazy^=1;return ;}void PushUp(int rt){
    bool f=tree[rt].lazy;tree[rt]=tree[lch]+tree[rch];tree[rt].lazy=f;return ;}void PushDown(int rt){
    if(!tree[rt].lazy) return ;Reverse(lch),Reverse(rch),tree[rt].lazy=0;return ;}void Build(int rt,int L,int R){
    if(L==R){
    int x=read();tree[rt]=(node){
    L,R,x,0,x,L,L,x,L,L,x,L,x,L,x,L,x,L};return ;}tree[rt].lazy=0;int Mid=(L+R)>>1;Build(lch,L,Mid),Build(rch,Mid+1,R);PushUp(rt);return ;}void Modify1(int rt,int p,int x){
    if(tree[rt].l==tree[rt].r){
    tree[rt]=(node){
    p,p,x,tree[rt].lazy,x,p,p,x,p,p,x,p,x,p,x,p,x,p};return ;}PushDown(rt);int Mid=(tree[rt].l+tree[rt].r)>>1;if(p<=Mid) Modify1(lch,p,x);else Modify1(rch,p,x);PushUp(rt);}void Modify2(int rt,int qL,int qR){
    if(qL<=tree[rt].l&&tree[rt].r<=qR){
    Reverse(rt);return ;}PushDown(rt);int Mid=(tree[rt].l+tree[rt].r)>>1;if(qL<=Mid) Modify2(lch,qL,qR);if(Mid+1<=qR) Modify2(rch,qL,qR);PushUp(rt);return ;}node Query(int rt,int qL,int qR){
    if(qL<=tree[rt].l&&tree[rt].r<=qR)return tree[rt];PushDown(rt);int Mid=(tree[rt].l+tree[rt].r)>>1;if(qR<=Mid) return Query(lch,qL,qR);else if(Mid+1<=qL) return Query(rch,qL,qR);return Query(lch,qL,qR)+Query(rch,qL,qR);}
}
using namespace SegmentTree;
int ord[30][2];
int main(){
    int n=read();Build(1,1,n);int q=read();for(int t=1;t<=q;t++){
    int opt=read();if(opt==1){
    int l=read(),r=read(),k=read();int cnt=0,ans=0;for(int i=1;i<=k;i++){
    node Q=Query(1,l,r);if(Q.maxs<=0) break;ans+=Q.maxs;ord[++cnt][0]=Q.maxsl,ord[cnt][1]=Q.maxsr;Modify2(1,ord[cnt][0],ord[cnt][1]);}for(int i=1;i<=cnt;i++)Modify2(1,ord[i][0],ord[i][1]);printf("%d\n",ans);}else{
    int i=read(),val=read();Modify1(1,i,val);}}return 0;
}

思考

网络流表现思想很多，一定要注意积累，这道题就是反映了费用流的基本原理，没有别的
以后线段树区间合并时可以采用结构体重定义的方法，简单而便捷