自动搬运

查看原文

来自洛谷，原作者为

	灵华 **

搬运于2025-08-24 22:33:48，当前版本为作者最后更新于2021-08-26 18:51:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

P7867 马戏团 - 官方题解

题外话

先说两句，这个题确实是挺那啥，题目本身不难，但是却很容易就把解法想的非常麻烦 （我一开始就想成了图论 ，最后在几位爷的指正下修正了做法，其实这题还是比较简单的。

---

先分析一下题意，简化一下就是：

给定一个序列，然后给出几个区间的左右端点和其价值，让你选择其中的几个，总花费是区间的在序列上的 并集 之和，总价值是这些 选择的区间的价值之和 ，最后要求的答案就是总价值减总花费的最大值。

我们设 $f_i$ 表示前 $i$ 个舞台且以第 $i$ 个舞台作为 最后一个 区间的 右端点 所能产生的最大利益。然后先处理出 $sum(j,i)$ 表示所有区间的左右端点在 $j \sim i$ 这段里面的价值之和 和 $s(j,i)$ 表示第 $j$ 个到第 $i$ 个舞台所要的费用。

显然，我们最后选完区间，会发现我们选择的所有区间一定是几个 不相交 的 连续区间 ，那我们考虑枚举每个点当做某个区间的 右端点 ，再枚举当前这个区间的左端点，求一个当前这个区间的最大值，最后再把每一个区间的最大值加起来，就是答案了。

$sum(j,i)$ 的处理我们可以用一个vector数组 $vc_i$ 记录以 $i$ 为右端点的区间，然后我们每次枚举 $i$ 的时候就把新的 $i$ 数组内的区间的影响加进去，每一个区间我们会影响的 $sum(j,i)$ 里面的 $j$ 值就只有当 $j \le$ 当前区间的左端点 这个条件满足的时候会有影响，所以我们把 $1$ 到当前这个区间的左端点给区间加上当前区间的价值（ 可能会有点绕， 仔细想想就明白了）。

$s(j,i)$ 的处理就用一个前缀和就好了。

由此，我们可以得出这么一个方程式：

$$f_i = \max ( f_{i-1} , \max ( f_{j-1} + sum(j,i) + s(j,i) (1 \le j \le i ) ) ) $$

上面那个式子第二个 $max$ 之前的东西都很好理解，说一下第二个 $max$ 里面的东西。

$f_{j-1}$ 表示第 $j$ 个之前最大的利益，所以这后半部分的式子表示有一个从 $j$ 到 $i$ 的区间我们全部选择。

这样子我们就得到了一个时间复杂度是 $O(n^2)$ 级别的解法，但是数据范围是 $10^6$，所以肯定会炸，考虑优化。

我们发现这整个式子其实是由两个 $max$ 组成的，而且我们发现第一个 $max$ 可以 $O(1)$ 做，第二个 $max$ 可以用线段树来优化，而且我们加入新的区间时也可以用线段树来区间加，所以总复杂度为 $O(n \log n)$。

具体实现的话，看代码吧。码风稍微有点奇怪，希望不影响阅读。

Code：

#include <iostream>
#include <vector>
#include <cstdio>
using namespace std ;

const long long INF = 0x3f3f3f3f3f3f3f3f ;

struct Node
{
	int l , r ;
	long long v ;
} q[1000005] ;

int n , m ;
long long s[1000005] , f[1000005] , t[4000005] , lz[4000005] ;
vector < int > vc[1000005] ;

void build ( int k , int l , int r )
{
	if ( l == r )
	{
		t [ k ] = s [ l - 1 ] ;
		return ;
	}
	int mid = ( l + r ) >> 1 ;
	build ( k << 1 , l , mid ) ;
	build ( k << 1 | 1 , mid + 1 , r ) ;
	t [ k ] = max ( t [ k << 1 ] , t [ k << 1 | 1 ] ) ;
}

void pushdown ( int k )
{
	if ( lz [ k ] )
	{
		t [ k << 1 ] += lz [ k ] ;
		t [ k << 1 | 1 ] += lz [ k ] ;
		lz [ k << 1 ] += lz [ k ] ;
		lz [ k << 1 | 1 ] += lz [ k ] ;
		lz [ k ] = 0 ;
	}
}

void change ( int k , int l , int r , int x , int y , long long z )
{
	if ( x <= l && r <= y )
	{
		t [ k ] += z ;
		lz [ k ] += z ;
		return ;
	}
	pushdown ( k ) ;
	int mid = ( l + r ) >> 1 ;
	if ( x <= mid )
		change ( k << 1 , l , mid , x , y , z ) ;
	if ( y > mid )
		change ( k << 1 | 1 , mid + 1 , r , x , y , z ) ;
	t [ k ] = max ( t [ k << 1 ] , t [ k << 1 | 1 ] ) ;
}

long long query ( int k , int l , int r , int x , int y )
{
	if ( x <= l && r <= y )
		return t [ k ] ;
	pushdown ( k ) ;
	int mid = ( l + r ) >> 1 ;
	long long res = -INF ;
	if ( x <= mid )
		res = query ( k << 1 , l , mid , x , y ) ;
	if ( y > mid )
		res = max ( res , query ( k << 1 | 1 , mid + 1 , r , x , y ) ) ;
	return res ;
}

int main ( )
{
	cin >> n >> m ;
	for ( int i = 1 ; i <= n ; ++ i )
	{
		long long x ;
		cin >> x ;
		s [ i ] = s [ i - 1 ] + x ;
	}
	for ( int i = 1 ; i <= m ; ++ i )
	{
		cin >> q [ i ] .l >> q [ i ] .r >> q [ i ] .v ;
		vc [ q [ i ] .r ] .push_back ( i ) ;
	}
	f [ 0 ] = 0 ;
	build ( 1 , 1 , n ) ;
	for ( int i = 1 ; i <= n ; ++ i )
	{
		for ( int j = 0 ; j < ( int ) vc [ i ] .size ( ) ; ++ j )
			change ( 1 , 1 , n , 1 , q [ vc [ i ] [ j ] ] .l , q [ vc [ i ] [ j ] ] .v ) ;
		f [ i ] = max ( f [ i - 1 ] , query ( 1 , 1 , n , 1 , i ) - s [ i ] ) ;
		change ( 1 , 1 , n , i + 1 , i + 1 , f [ i ] ) ;
	}
	cout << f [ n ] << endl ;
	return 0 ;
}