「CF280D」k-Maximum Subsequence Sum

发表于 | 分类于 | | 浏览量： 次

啥？线段树？还费用流？

传送门

洛谷

CF280D

题解

首先可以考虑一个贪心，每次取询问区间内权值和最大的子段，然后把这个子段标记上，该次询问中不能再取。

但是这个想法并不对，比如序列$3,-1,3$，可以取至多2个子段。由于第一次会取权值最大的子段$[1,3]$，然后就没有子段可以取了。而实际上取$[1,1]$和$[3,3]$的话答案会更优。

然后不难联想到，在求最大流的时候，我们通过建反向弧的方式来保证了正确性。

所以对于这题，可以在取了一个子段之后，将改子段取反，之后还能再取，来保证正确性。

而取反和取最大值的操作都可以通过线段树来维护。

时间复杂度$O(n\log n+mk\log n)$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=100005;
int n,Q,A[maxn];
inline int read()
{
	int ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
	return ret*f;
}
struct Range
{
	int L,R,Sum;
	inline bool operator < (const Range& b)const{return Sum<b.Sum;}
	inline Range operator + (const Range& b)const{return (Range){L,b.R,Sum+b.Sum};}
}Ra[25];
struct SegmentTree
{
	struct Node{Range Lmax,Rmax,Max,Lmin,Rmin,Min,All;bool Tag;}Tree[maxn*4];
	inline void Merge(Node& a,Node b,Node c)
	{
		a.All=b.All+c.All;
		a.Lmin=min(b.Lmin,b.All+c.Lmin);a.Rmin=min(c.Rmin,b.Rmin+c.All);
		a.Lmax=max(b.Lmax,b.All+c.Lmax);a.Rmax=max(c.Rmax,b.Rmax+c.All);
		a.Max=max(max(b.Max,c.Max),b.Rmax+c.Lmax);a.Min=min(min(b.Min,c.Min),b.Rmin+c.Lmin);
	}
	inline void PushUp(int rt){Merge(Tree[rt],Tree[rt*2],Tree[rt*2+1]);}
	inline void Reverse(int rt)
	{
		Tree[rt].Lmin.Sum*=-1;Tree[rt].Lmax.Sum*=-1;
		Tree[rt].Rmin.Sum*=-1;Tree[rt].Rmax.Sum*=-1;
		Tree[rt].Min.Sum*=-1;Tree[rt].Max.Sum*=-1;Tree[rt].All.Sum*=-1;
		swap(Tree[rt].Min,Tree[rt].Max);swap(Tree[rt].Lmax,Tree[rt].Lmin);swap(Tree[rt].Rmax,Tree[rt].Rmin);
	}
	inline void PushDown(int rt)
	{
		if(Tree[rt].Tag)
		{
			Reverse(rt*2);Reverse(rt*2+1);
			Tree[rt*2].Tag^=1;Tree[rt*2+1].Tag^=1;Tree[rt].Tag^=1;
		}
	}
	inline void Build(int L=1,int R=n,int rt=1)
	{ 
		if(L==R){Tree[rt].All=Tree[rt].Lmax=Tree[rt].Lmin=Tree[rt].Max=Tree[rt].Min=Tree[rt].Rmax=Tree[rt].Rmin=(Range){L,R,A[L]};return;}
		int M=(L+R)>>1;
		Build(L,M,rt*2);
		Build(M+1,R,rt*2+1);
		PushUp(rt);
	}
	inline void UpdatePoint(int P,int V,int L=1,int R=n,int rt=1)
	{
		if(L==R){Tree[rt].All.Sum=Tree[rt].Lmax.Sum=Tree[rt].Lmin.Sum=Tree[rt].Max.Sum=Tree[rt].Min.Sum=Tree[rt].Rmax.Sum=Tree[rt].Rmin.Sum=V;return;}
		int M=(L+R)>>1;PushDown(rt);
		if(P<=M) UpdatePoint(P,V,L,M,rt*2);
		if(M<P) UpdatePoint(P,V,M+1,R,rt*2+1);
		PushUp(rt);
	}
	inline Node QueryMax(int LL,int RR,int L=1,int R=n,int rt=1)
	{
		if(LL<=L&&R<=RR) return Tree[rt];
		int M=(L+R)>>1;Node ret;PushDown(rt);
		if(LL<=M) ret=QueryMax(LL,RR,L,M,rt*2);
		if(M<RR)
		{
			if(LL>M) ret=QueryMax(LL,RR,M+1,R,rt*2+1);
			else Merge(ret,ret,QueryMax(LL,RR,M+1,R,rt*2+1));
		}
		return ret;
	}
	inline void UpdateRange(int LL,int RR,int L=1,int R=n,int rt=1)
	{
		if(LL<=L&&R<=RR){Reverse(rt);Tree[rt].Tag^=1;return;}
		int M=(L+R)>>1;PushDown(rt);
		if(LL<=M) UpdateRange(LL,RR,L,M,rt*2);
		if(M<RR) UpdateRange(LL,RR,M+1,R,rt*2+1);
		PushUp(rt);
	}
}S;
int main()
{
	n=read();
	for(int i=1;i<=n;i++) A[i]=read();
	Q=read();S.Build();
	while(Q--)
	{
		if(read()==0)
		{
			int P=read(),V=read();
			S.UpdatePoint(P,V);
		}
		else
		{
			int L=read(),R=read(),K=read(),cnt,ans=0;
			for(cnt=0;cnt<K;cnt++)
			{
				SegmentTree::Node tep=S.QueryMax(L,R);
				if(tep.Max.Sum<=0) break;
				ans+=tep.Max.Sum;
				S.UpdateRange(tep.Max.L,tep.Max.R);
				Ra[cnt]=tep.Max;
			}
			for(int i=0;i<cnt;i++)
				S.UpdateRange(Ra[i].L,Ra[i].R);
			printf("%d\n",ans);
		}
	}
	return 0;
}