CF280D k-Maximum Subsequence Sum（線段樹）

傳送門：https://www.luogu.org/problemnew/show/CF280D

題面大意：

長度為 n n n的數列，支援兩種操作：

1.修改某個位置的值

2.詢問區間 [ l , r ] [l,r] [l,r]裡選出至多 k k k個不相交的子段和的最大值。 一共有 m m m個操作

解法：

暴力 d p dp dp+滾動數組（在本地卡進2s）

模拟賽的時候有人用這個方法A了

#include <bits/stdc++.h>
#define MAXN 200005
using namespace std;
inline int read() {
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9') {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9') {
        x=(x*10)+(ch-'0');
        ch=getchar();
    }
    return x*f;
}
int a[MAXN];
namespace bf{
	int dp[2][25][2];
	inline int query(int l,int r,int k){
		memset(dp,0,sizeof(dp));
		for (register int i=l;i<=r;++i){
			for (register int j=1;j<=k;++j){
				dp[i&1][j][0]=max(dp[!(i&1)][j][1],dp[!(i&1)][j][0]);
				dp[i&1][j][1]=max(dp[!(i&1)][j-1][0],dp[!(i&1)][j][1])+a[i];
				dp[i&1][j][1]=max(dp[i&1][j][1],dp[!(i&1)][j-1][0]+a[i]);
			}
		}
		int ans=-0x7fffffff;
		for (register int i=0;i<=k;++i){
			ans=max(ans,max(dp[r&1][i][1],dp[r&1][i][0]));
		}
		return ans;
	}
}
using namespace bf;
int main(){
	int n=read();
	for (register int i=1;i<=n;++i){
		a[i]=read();
	}
	int q=read();
	while (q--){
		int opr=read();
		if (opr==0){
			int i=read(),val=read();
			a[i]=val;
		}
		else {
			int l=read(),r=read(),k=read();
			printf("%d\n",query(l,r,k));
		}
	}
}
           

正解

毒瘤線段樹，維護18個值：

s u m sum sum 區間和

l , r l,r l,r 區間左右邊界

m a x s maxs maxs 最大子段和

m i n s mins mins 最小子段和

m a x s l maxsl maxsl 最大子段和左邊界

m a x s r maxsr maxsr最大子段和右邊界

m i n s l minsl minsl最小子段和左邊界

m i n s r minsr minsr最小子段和右邊界

m a x l , m i n l maxl,minl maxl,minl最大，最小字首和

m a x l p , m i n l p maxlp,minlp maxlp,minlp最大，最小字首和右端點（顯然左端點确定）

m a x r , m i n r maxr,minr maxr,minr最大，最小字尾和

m a x r p , m i n r p maxrp,minrp maxrp,minrp最大，最小字尾和左端點

f l a g flag flag翻轉标記

每次取最大子段和， a n s + = ans+= ans+=最大子段和，

然後把最大子段和的區間每個數 ∗ − 1 *-1 ∗−1，如果最大子段和 &lt; = 0 &lt;=0 <=0或者操作次數 &gt; k &gt;k >k退出

可以用網絡流證明

p.s.不要忘記恢複修改過的線段樹

#include <bits/stdc++.h>
#define MAXN 100005
using namespace std;
inline int read() {
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9') {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9') {
        x=(x*10)+(ch-'0');
        ch=getchar();
    }
    return x*f;
}
int a[MAXN];
bool DBG=true;
namespace SegmentTree{
	struct node{
		int sum;//區間和
		int l,r;//區間左右邊界
		int maxs;//最大子段和
        int mins;//最小子段和
		int maxsl;//最大子段和左邊界
        int maxsr;//最大子段和右邊界
		int minsl;//最小子段和左邊界
        int minsr;//最小子段和右邊界
		int maxl,minl;//最大，最小字首和
		int maxlp,minlp;//最大，最小字首和右端點（顯然左端點确定） 
		int maxr,minr;//最大，最小字尾和
		int maxrp,minrp;//最大，最小字尾和左端點
		bool flag;//翻轉标記
	}tree[MAXN<<2];
	inline void sw(int &a,int &b){int temp=a;a=b;b=temp;}
    inline void re(int &a){a=-a;}
	inline void Rev(int i){//翻轉tree[i]
        re(tree[i].sum);
		sw(tree[i].maxs,tree[i].mins);
        re(tree[i].maxs),re(tree[i].mins);
		sw(tree[i].maxsl,tree[i].minsl);
		sw(tree[i].maxsr,tree[i].minsr);
		sw(tree[i].maxl,tree[i].minl);
        re(tree[i].maxl),re(tree[i].minl);
		sw(tree[i].maxlp,tree[i].minlp);
		sw(tree[i].maxr,tree[i].minr);
        re(tree[i].maxr),re(tree[i].minr);
		sw(tree[i].maxrp,tree[i].minrp);
		tree[i].flag^=1;
	}
	#define lc i<<1
	#define rc i<<1|1
    #define nd tree[i]
	inline void pushdown(int i){
		if (tree[i].flag) Rev(lc),Rev(rc),tree[i].flag=0;
	}
	node operator + (const node &A,const node &B){//這裡不能寫錯
		node C;
		C.l=A.l,C.r=B.r;
        C.sum=A.sum+B.sum;
        C.flag=false;
        //維護maxs,mins,maxsl,minsl
        if (max(A.maxs,B.maxs)>A.maxr+B.maxl){
            if (A.maxs>B.maxs){
                C.maxs=A.maxs;
                C.maxsl=A.maxsl;
                C.maxsr=A.maxsr;
            }
            else {
                C.maxs=B.maxs;
                C.maxsl=B.maxsl;
                C.maxsr=B.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){
            if (A.mins<B.mins){
                C.mins=A.mins;
                C.minsl=A.minsl;
                C.minsr=A.minsr;
            }
            else {
                C.mins=B.mins;
                C.minsl=B.minsl;
                C.minsr=B.minsr;
            }
        }
        else {
            C.mins=A.minr+B.minl;
            C.minsl=A.minrp;
            C.minsr=B.minlp;
        }
        //維護maxl,minl,維護其端點
        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;
        }
        //維護maxr,minr,維護其端點
        if (A.maxr+B.sum>B.maxr){
            C.maxr=A.maxr+B.sum;
            C.maxrp=A.maxrp;
        }
        else {
            C.maxr=B.maxr;
            C.maxrp=B.maxrp;
        }
        if (A.minr+B.sum<B.minr){
            C.minr=A.minr+B.sum;
            C.minrp=A.minrp;
        }
        else {
            C.minr=B.minr;
            C.minrp=B.minrp;
        }
        return C;//快樂地return 
	}
    inline void pushup(int i){
        bool temp=tree[i].flag;
        tree[i]=tree[lc]+tree[rc];
        tree[i].flag=temp;
    }
    inline void Set(int i,int val){
        nd.sum=nd.maxs=nd.mins=nd.maxl=nd.minl=nd.maxr=nd.minr=val;
    }
    void Build(int l,int r,int i){
        tree[i].flag=0;
        if (l==r){
            tree[i].l=l,tree[i].r=l;
            Set(i,a[l]);
            nd.maxsl=nd.maxsr=nd.minsl=nd.minsr=nd.maxlp=nd.minlp=nd.maxrp=nd.minrp=l;
            return ;
        }
        int mid=(l+r)>>1;
        Build(l,mid,lc);
        Build(mid+1,r,rc);
        pushup(i);
    }
    node Query(int L,int R,int i){
        if (L<=tree[i].l&&tree[i].r<=R){
            return tree[i];
        }
        pushdown(i);
        int mid=(tree[i].l+tree[i].r)>>1;
        if (mid>=R) return Query(L,R,lc);
        else if (mid<L) return Query(L,R,rc);
        else return Query(L,R,lc)+Query(L,R,rc);
    }
    void Update(int L,int R,int i){//區間*-1
        if (L<=tree[i].l&&tree[i].r<=R){
            Rev(i);
            return ;
        }
        pushdown(i);
        int mid=(tree[i].l+tree[i].r)>>1;
        if (mid>=R) Update(L,R,lc);
        else if (mid<L) Update(L,R,rc);
        else Update(L,R,lc),Update(L,R,rc);
        pushup(i);
    }
    void Update_pos(int index,int i,int val){//單點修改
        if (tree[i].l==tree[i].r){
            Set(i,tree[i].flag?-val:val);
            return ;
        }
        pushdown(i);
        int mid=(tree[i].l+tree[i].r)>>1;
        if (index<=mid) Update_pos(index,lc,val);
        else Update_pos(index,rc,val);
        pushup(i);
    }
}
using namespace SegmentTree;
int L[MAXN],R[MAXN];
int main(){
    int n=read();
    for (register int i=1;i<=n;++i){
        a[i]=read();
    }
    Build(1,n,1);
    int q=read();
    while (q--){
        int opr=read();
        if (opr==1){
            int l=read(),r=read(),k=read();
            int tot=0,ans=0;
            for (register int i=1;i<=k;++i){
                node Q=Query(l,r,1);
                if (Q.maxs<=0) break;
                ans+=Q.maxs;
                L[++tot]=Q.maxsl,R[tot]=Q.maxsr;
                Update(L[tot],R[tot],1);
            }
            for (register int i=1;i<=tot;++i){
                Update(L[i],R[i],1);
            }
            printf("%d\n",ans);
        }
        else {
            int i=read(),val=read();
            Update_pos(i,1,val);
        }
    }
}