CF115E Linear Kingdom Races

洛谷傳送門

題目描述

You are a car race organizer and would like to arrange some races in Linear Kingdom.

Linear Kingdom has nn consecutive roads spanning from left to right. The roads are numbered from 11 to nn from left to right, thus the roads follow in the order of their numbers' increasing. There will be several races that may be held on these roads. Each race will use a consecutive subset of these roads. Also, each race will pay some amount of money to you if this race is held. No races overlap in time, so some roads can be used in several races.

Unfortunately, some of the roads are in a bad condition and they need repair. Each road has repair costs associated with it, you are required to pay this cost to repair the road. A race can only take place if all the roads used in the race are renovated. Your task is to repair such roads (possibly all or none) that will maximize your profit. Your profit is defined as the total money you get from the races that are held minus the total money you spent to repair the roads. Note that you may decide not to repair any road and gain zero profit.

Print the maximum profit you can gain.

輸入格式

The first line contains two single-space separated integers, nn and mm ( 1<=n,m<=2·10^{5}1<=n,m<=2⋅105 ), denoting the number of roads and the number of races, respectively.

Then nn lines follow, each line will contain a single non-negative integer not exceeding 10^{9}109 denoting the cost to repair a road. The costs are given in order from road 11 to road nn .

Finally, mm lines follow. Each line is single-space-separated triplets of integers. Each triplet will be given as lbl**b , ubu**b , and pp ( 1<=lb<=ub<=n,1<=p<=10^{9}1<=l**b<=u**b<=n,1<=p<=109 ), which means that the race these three integers describe will use all the roads from lbl**b to ubu**b , inclusive, and if it's held you get pp .

輸出格式

Print a single integer denoting the maximum possible profit you can gain.

Please, do not use the %lld specificator to read or write 64-bit integers in C++. It is recommended to use cin, cout stream (also you may use %I64d specificator).

題意翻譯

你是一個賽車比賽的組織者，想線上性王國中安排一些比賽。

線性王國有n條連續的從左到右的道路。道路從左到右依次編号為從1到n，是以道路按照升序排列。在這些道路上可能會有幾場比賽，每一場比賽都将使用這些道路的某個連續的子序列。而且，如果某場比賽舉行了，你将獲得一定數額的金錢。沒有比賽在時間上重疊，是以每一段道路可以在多個比賽中使用。

不幸的是，所有道路的狀況都不佳，需要修理。每條路都有與之相關的維修費用，你需要支付這筆費用來修理道路。隻有在某場比賽中需要使用的所有道路都進行了修複，才能進行比賽。你的任務是修複道路并使你的利潤最大化。你的利潤被定義為你從比賽中獲得的總金額減去你花在修理道路上的錢。請注意，您可以決定不修任何道路，并獲得利潤0。

輸出你能獲得的最大利潤。

輸入輸出格式

輸入格式：

第一行包括兩個整數n和m(1 \leq n,m \leq 2\cdot 10^5)(1≤n,m≤2⋅105)，分别表示道路的數量和比賽的數量。

接下來n行，每行一個整數，表示這條道路修複需要的代價。

再接下來m行，每行包括三個整數l_b,u_b,p(1 \leq l_b,u_b \leq n,1 \leq p \leq 10^9)l**b,u**b,p(1≤l**b,u**b≤n,1≤p≤109)，表示第b場比賽需要使用道路l_b,u_bl**b,u**b，你會獲得收益p。

輸出格式：

輸出一個整數，表示你能獲得的最大利潤。

P.S.請不要使用%lld在C++中讀寫64位整數。推薦使用cin和cout流（也可以使用%I64d）。

說明

在第一個樣例中，最優解是修複1、2、3和7。你将會在第1、2、4三場比賽中獲得15的收益。道路修理費用是11，是以你的利潤是4。

題解：

感謝翻譯官的翔實處理。

最優化問題，一開始以為是貪心。貪心政策是對于每一個比賽來講，如果它的收益小于消費，那麼肯定是很不劃算的。但是覺得這道題不應該這麼簡單。于是發現：對于某段區間，可能被多次覆寫，但是隻拿一次的花費。于是貪心變得不可行，開始思考DP。

沿襲剛剛的思路，考慮設定\(DP\)為\(dp[i]\)表示前i場比賽的最大價值。（加排序）但是發現，由于并集緣故，不能轉移。是以設定\(dp[i]\)表示前i個道路的最大價值。

轉移應該是很好想的。

對于每一個新的i，有選、不選兩種轉移。不選的話就是\(dp[i]=dp[i-1]\)，選的話就是\(dp[i]=\max(dp[j]+w[j])\)，其中\(w[j]\)是拓展目前道路對答案的貢獻。

需要拓展哪些道路呢？或者說，哪些道路是對目前答案有貢獻的呢？當然是那些右端點正好在i點的比賽們。于是我們采用挂鍊（vector挂鍊）方式把每個右端點對應的所有左端點挂上，然後就可以轉移了。

貢獻是什麼呢？根據題意，貢獻就是比賽的盈利減去這個區間的花費。

我們發現，轉移的時候要頻繁修改區間，那麼為了保證時間複雜度，我們采用線段樹來優化這個東西。維護一棵線段樹，維護\(dp[j]+w[j]\)。維護過程如下：

首先，對于每個i，先對區間\([0,i-1]\)統一減去\(v[i]\)。

然後對于每個可轉移的比賽區間\([l,r]\)，對\([0,l-1]\)統一加上p。

最後查詢的就是\([0,i-1]\)的區間最大值。更新狀态，并把新狀态賦給新線段樹。

是以代碼：

#include<cstdio>
#include<algorithm>
#include<vector>
#define int long long
#define lson pos<<1
#define rson pos<<1|1
using namespace std;
const int maxn=2*1e5+10;
const int INF=1e9;
struct add
{
	int l,k;
	add(int p,int q)
	{
		l=p,k=q;
	}
};
int n,m;
int v[maxn];
vector<add> vec[maxn];
int tree[maxn<<2],lazy[maxn<<2];
int dp[maxn];
void pushup(int pos)
{
	tree[pos]=max(tree[lson],tree[rson]);
}
void mark(int pos,int l,int r,int k)
{
	tree[pos]+=k;
	lazy[pos]+=k;
}
void pushdown(int pos,int l,int r)
{
	int mid=(l+r)>>1;
	mark(lson,l,mid,lazy[pos]);
	mark(rson,mid+1,r,lazy[pos]);
	lazy[pos]=0;
}
void update(int pos,int l,int r,int x,int y,int k)
{
	int mid=(l+r)>>1;
	if(x<=l && r<=y)
	{
		mark(pos,l,r,k);
		return;
	}
	pushdown(pos,l,r);
	if(x<=mid)
		update(lson,l,mid,x,y,k);
	if(y>mid)
		update(rson,mid+1,r,x,y,k);
	pushup(pos);
}
int query(int pos,int l,int r,int x,int y)
{
	int mid=(l+r)>>1;
	if(x<=l && r<=y)
		return tree[pos];
	pushdown(pos,l,r);
	int ret=-INF;
	if(x<=mid)
		ret=max(ret,query(lson,l,mid,x,y));
	if(y>mid)
		ret=max(ret,query(rson,mid+1,r,x,y));
	return ret;
}
signed main()
{
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%lld",&v[i]);
	for(int i=1;i<=m;i++)
	{
		int x,y,z;
		scanf("%lld%lld%lld",&x,&y,&z);
		vec[y].push_back(add(x,z));
	}
	for(int i=1;i<=n;i++)
	{
		update(1,0,n,0,i-1,-v[i]);
		for(int j=0;j<vec[i].size();j++)
		{
			int ll=vec[i][j].l,kk=vec[i][j].k;
			update(1,0,n,0,ll-1,kk);
		}
		dp[i]=max(query(1,0,n,0,i-1),dp[i-1]);
		update(1,0,n,i,i,dp[i]);
	}
	printf("%lld",dp[n]);
	return 0;
}