Linear Kingdom Races

题意翻译

## 题目描述 你是一个赛车比赛的组织者，想在线性王国中安排一些比赛。 线性王国有n条连续的从左到右的道路。道路从左到右依次编号为从1到n，因此道路按照升序排列。在这些道路上可能会有几场比赛，每一场比赛都将使用这些道路的某个连续的子序列。而且，如果某场比赛举行了，你将获得一定数额的金钱。没有比赛在时间上重叠，所以每一段道路可以在多个比赛中使用。 不幸的是，**所有道路**的状况都不佳，需要修理。每条路都有与之相关的维修费用，你需要支付这笔费用来修理道路。只有在某场比赛中需要使用的所有道路**都进行了修复**，才能进行比赛。你的任务是修复道路并使你的利润最大化。你的利润被定义为你从比赛中获得的总金额减去你花在修理道路上的钱。**请注意，您可以决定不修任何道路，并获得利润0。** 输出你能获得的最大利润。 ## 输入输出格式 ### 输入格式： 第一行包括两个整数n和m$(1 \leq n,m \leq 2\cdot 10^5)$，分别表示道路的数量和比赛的数量。 接下来n行，每行一个整数，表示这条道路修复需要的代价。 再接下来m行，每行包括三个整数$l_b,u_b,p(1 \leq l_b,u_b \leq n,1 \leq p \leq 10^9)$，表示第b场比赛需要使用道路$l_b,u_b$，你会获得收益p。 ### 输出格式： 输出一个整数，表示你能获得的最大利润。 P.S.请不要使用%lld在C++中读写64位整数。推荐使用cin和cout流（也可以使用%I64d）。 ## 说明 在第一个样例中，最优解是修复1、2、3和7。你将会在第1、2、4三场比赛中获得15的收益。道路修理费用是11，因此你的利润是4。

题目描述

You are a car race organizer and would like to arrange some races in Linear Kingdom. Linear Kingdom has $ n $ consecutive roads spanning from left to right. The roads are numbered from $ 1 $ to $ n $ 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, $ n $ and $ m $ ( $ 1<=n,m<=2·10^{5} $ ), denoting the number of roads and the number of races, respectively. Then $ n $ lines follow, each line will contain a single non-negative integer not exceeding $ 10^{9} $ denoting the cost to repair a road. The costs are given in order from road $ 1 $ to road $ n $ . Finally, $ m $ lines follow. Each line is single-space-separated triplets of integers. Each triplet will be given as $ lb $ , $ ub $ , and $ p $ ( $ 1<=lb<=ub<=n,1<=p<=10^{9} $ ), which means that the race these three integers describe will use all the roads from $ lb $ to $ ub $ , inclusive, and if it's held you get $ p $ .

输出格式

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).

输入输出样例

输入样例 #1

7 4
3
2
3
2
1
2
3
1 2 5
2 3 5
3 5 3
7 7 5

输出样例 #1

4

输入样例 #2

2 1
0
3
1 2 5

输出样例 #2

2

输入样例 #3

3 1
10
10
10
1 3 10

输出样例 #3

0

说明

In the first sample the optimal solution is to repair roads $ 1 $ , $ 2 $ , $ 3 $ , and $ 7 $ . Three races will take place which nets you $ 15 $ . The road repair costs $ 11 $ , hence your profit is $ 4 $ .