[Codeforces 280D]k-Maximum Subsequence Sum（线段树)

题面

给出一个序列，序列里面的数有正有负，有两种操作

1.单点修改

2.区间查询，在区间中选出至多k个不相交的子区间，使得这至多k个子区间中数的和最大

分析

极其毒瘤的线段树，要维护18个变量

首先考虑查询k=1的情况，是常见的线段树模型。维护区间最大连续和，区间最大前缀和，区间最大后缀和。合并的时候分类讨论一下即可，这里不再赘述。

如果k>1怎么办呢。实际上可以贪心，每次取1个最大子区间，然后把子区间内的值取反。再继续取最大子区间。如果此时最大子区间的和已经<0，就不取了。

正确性可以感性理解一下。假如我们的区间内的数为{7,-2,3,-10},k=2.第一次取出的序列为{7,-2,3},然后取反，变成了{-7,2,-3,10}。再取一次就得到了{2}.把这两个子区间加起来，我们发现和为7+(-2)+3+2=7+3,正好是和最大的两个序列{7}{3}.这里的取反操作，实际上起到了把一个区间断成多个的效果。(upd:这里用模拟费用流里退流的思想,可以严格证明正确性)

那么我们考虑具体实现，除了区间最大连续和，区间最大前缀和，区间最大后缀和，我们还要维护对应连续和的起点和终点。取反实际上比较简单，只要再维护区间最小连续和等变量，取反的时候交换最大最小值，并乘上-1即可。

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define maxn 100000

#define maxk 20

using namespace std;

inline void qread(int &x){

	x=0;

	int sign=1;

	char c=getchar();

	while(c<'0'||c>'9'){

		if(c=='-') sign=-1;

		c=getchar();

	}

	while(c>='0'&&c<='9'){

		x=x*10+c-'0';

		c=getchar();

	}

	x=x*sign;

}

inline void qprint(int x){

	if(x<0){

		putchar('-');

		qprint(-x);

	}else if(x==0){

		putchar('0');

		return;

	}else{

		if(x/10>0) qprint(x/10);

		putchar('0'+x%10);

	}

}

int n,m;

int a[maxn+5];

struct val{

	int sum;//区间和

	//最小值相关

	int lmin;//最小前缀和

	int lminp;//最小前缀和的位置为[l,lminp],线段树节点里已经记录了[l,r]

	int rmin;//最小后缀和

	int rminp;//最小后缀和的位置为[rminp,r]

	int minv;//最小连续和

	int minpl;//最小连续和的起点

	int minpr;//最小连续和的终点

	//最大值相关

	int lmax;

	int lmaxp;

	int rmax;

	int rmaxp;

	int maxv;

	int maxpl;

	int maxpr;

	friend val operator + (val lson,val rson){

		val ans;

		ans.sum=lson.sum+rson.sum;

		ans.lmin=lson.lmin;

		ans.lminp=lson.lminp;

		if(lson.sum+rson.lmin<ans.lmin){

			ans.lmin=lson.sum+rson.lmin;

			ans.lminp=rson.lminp;

		}

		ans.rmin=rson.rmin;

		ans.rminp=rson.rminp;

		if(rson.sum+lson.rmin<ans.rmin){

			ans.rmin=rson.sum+lson.rmin;

			ans.rminp=lson.rminp;

		}

		int minv=min(min(lson.minv,rson.minv),lson.rmin+rson.lmin);

		ans.minv=minv;

		if(lson.minv==minv){

			ans.minpl=lson.minpl;

			ans.minpr=lson.minpr;

		}else if(rson.minv==minv){

			ans.minpl=rson.minpl;

			ans.minpr=rson.minpr;

		}else{

			ans.minpl=lson.rminp;

			ans.minpr=rson.lminp;

		}

		ans.lmax=lson.lmax;

		ans.lmaxp=lson.lmaxp;

		if(lson.sum+rson.lmax>ans.lmax){

			ans.lmax=lson.sum+rson.lmax;

			ans.lmaxp=rson.lmaxp;

		}

		ans.rmax=rson.rmax;

		ans.rmaxp=rson.rmaxp;

		if(rson.sum+lson.rmax>ans.rmax){

			ans.rmax=rson.sum+lson.rmax;

			ans.rmaxp=lson.rmaxp;

		}

		int maxv=max(max(lson.maxv,rson.maxv),lson.rmax+rson.lmax);

		ans.maxv=maxv;

		if(lson.maxv==maxv){

			ans.maxpl=lson.maxpl;

			ans.maxpr=lson.maxpr;

		}else if(rson.maxv==maxv){

			ans.maxpl=rson.maxpl;

			ans.maxpr=rson.maxpr;

		}else{

			ans.maxpl=lson.rmaxp;

			ans.maxpr=rson.lmaxp;

		}

		return ans;

	}

	void reverse(){

		sum=-sum;

		lmin=-lmin;

		lmax=-lmax;

		swap(lmin,lmax);

		swap(lminp,lmaxp);

		rmin=-rmin;

		rmax=-rmax;

		swap(rmin,rmax);

		swap(rminp,rmaxp);

		minv=-minv;

		maxv=-maxv;

		swap(minv,maxv);

		swap(minpl,maxpl);

		swap(minpr,maxpr);

	}

	void set(int pos,int val){

		sum=lmin=lmax=rmin=rmax=minv=maxv=val;

		lminp=lmaxp=rminp=rmaxp=minpl=maxpl=minpr=maxpr=pos;

	}

	void print(){

		printf("val: maxv=%d lmax=%d rmax=%d\n",maxv,lmax,rmax);

	}

};

struct segment_tree{

	struct node{

		int l;

		int r;

		int sum;

		int mark;//区间-1（翻转max,min） 标记

		val v;

	}tree[maxn*4+5];

	void push_up(int pos){

		tree[pos].v=tree[pos<<1].v+tree[pos<<1|1].v;

	}

	void build(int l,int r,int pos){

		tree[pos].l=l;

		tree[pos].r=r;

		if(l==r){

			tree[pos].v.set(l,a[l]);

			return;

		}

		int mid=(l+r)>>1;

		build(l,mid,pos<<1);

		build(mid+1,r,pos<<1|1);

		push_up(pos);

//		printf("[%d,%d]: ",l,r);

//		tree[pos].v.print();

	}

	void push_down(int pos){

		if(tree[pos].mark){

			tree[pos<<1].mark^=1;

			tree[pos<<1].v.reverse();

			tree[pos<<1|1].mark^=1;

			tree[pos<<1|1].v.reverse();

			tree[pos].mark=0;

		}

	}

	void update_segment(int L,int R,int pos){

		if(L<=tree[pos].l&&R>=tree[pos].r){

			tree[pos].mark^=1;

			tree[pos].v.reverse();

			return;

		}

		push_down(pos);

		int mid=(tree[pos].l+tree[pos].r)>>1;

		if(L<=mid) update_segment(L,R,pos<<1);

		if(R>mid) update_segment(L,R,pos<<1|1);

		push_up(pos);

	}

	void update_point(int upos,int val,int pos){

		if(tree[pos].l==tree[pos].r){

			tree[pos].v.set(tree[pos].l,val);

			return;

		}

		push_down(pos);

		int mid=(tree[pos].l+tree[pos].r)>>1;

		if(upos<=mid) update_point(upos,val,pos<<1);

		else update_point(upos,val,pos<<1|1);

		push_up(pos);

	}

	val query(int L,int R,int pos){

		if(L<=tree[pos].l&&R>=tree[pos].r){

			return tree[pos].v;

		}

		push_down(pos);

		int mid=(tree[pos].l+tree[pos].r)>>1;

		val lans,rans;

		lans.set(0,0);

		rans.set(0,0);

		if(L<=mid){

			lans=query(L,R,pos<<1);

		}

		if(R>mid){

			rans=query(L,R,pos<<1|1);

		}

		if(lans.maxpl==0) return rans;

		else if(rans.maxpl==0) return lans;

		else return lans+rans;

	}

}T;

val tmp[maxk+5];

int solve(int l,int r,int k){

	int sz=0;

	int ans=0;

	for(int i=1;i<=k;i++){

		tmp[++sz]=T.query(l,r,1);

		if(tmp[sz].maxv<0){

			sz--;

			break;

		}

		ans+=tmp[sz].maxv;

		T.update_segment(tmp[sz].maxpl,tmp[sz].maxpr,1);

	}

	for(int i=sz;i>=1;i--){

		T.update_segment(tmp[i].maxpl,tmp[i].maxpr,1);

	}

	return ans;

}

int main(){

//#ifndef LOCAL

//	freopen("easy.in","r",stdin);

//	freopen("easy.out","w",stdout);

//#endif

	int op,x,val,l,r,k;

	qread(n);

	for(int i=1;i<=n;i++) qread(a[i]);

	T.build(1,n,1);

	qread(m);

	for(int i=1;i<=m;i++){

		qread(op);

		if(op==0){

			qread(x);

			qread(val);

			T.update_point(x,val,1);

		}else{

			qread(l);

			qread(r);

			qread(k);

			qprint(solve(l,r,k));

			putchar('\n');

		}

	}

}