UOJ Logo Universal Online Judge

UOJ

#507. 【JOISC2020】星座3

统计

JOI-kun 拍了一张夜景照片。这张照片由 $N \times N$ 个像素组成,即长宽均为 $N$ 个像素。从左到右第 $x$ 列,从上往下第 $y$ 行的像素被称为 $(x,y)$。

图片中的每个像素都代表着建筑物、夜空或星星。建筑物颜色是白色、夜空颜色是黑色,星星颜色是黄色。对于 $1 \le i \le N$ 的每个 $i$,在第 $i$ 列中,从最下面一行到第 $A_i$ 行像素是表示建筑物的白色像素。其余的像素中,有 $M$ 个黄色像素代表着星星。第 $j$ 个黄色像素 $(1 \le j \le M)$ 是像素 $(X_j,Y_j)$。所有其他像素都是代表夜空的黑色像素。

我们称对于原照片的一个子矩形,如果以下两个条件成立,则被称作一个星座:

  • 矩形区域中没有白色像素。
  • 矩形区域中有两个或多个黄色像素。

JOI-kun 已经厌倦了看星座。因此他想把一些黄色像素画成黑色,使得修改后的照片不存在任何星座。

然而,如果他将过多黄色像素涂黑,这幅画就变得不自然了。更准确地说,如果他把第 $j$ 个黄色像素 $1 \le j \le M$ 成黑色,那么图片的不自然度就会增加 $c_j$。没有进行涂黑操作前,照片不自然度为 $0$。

编写一个程序,在给定图片信息和每个黄色像素的整数的情况下,选择若干个星星涂黑,使得修改后的图不存在星座,且不自然度最小。

输入格式

第一行一个正整数 $N$。

第二行 $N$ 个正整数,第 $i$ 个正整数表示 $A_i$。

第三行一个正整数 $M$。

接下来 $M$ 行,每行三个正整数 $X_i,Y_j,C_j$,表示一个黄色像素。

输出格式

一行一个非负整数表示答案。

样例一

input

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

output

2

explanation

在样例1中,左下角为$(1,4)$,右上角为$(2,5)$的子矩形形成了一个星座。这也是唯一的星座。

如果JOI-kun将第三个黄色像素涂黑,此时不自然度为$2$,同时为所有合法方案的最小值。

下图为样例1的解释:

样例一示意图

样例二

input

7
5 6 2 3 6 7 6
5
7 7 5
3 3 7
3 7 10
1 7 6
4 7 8

output

16

explanation

最优解为将第$3,4$个黄色像素涂黑。

样例三

input

8
6 8 5 7 3 4 2 1
10
8 2 9
6 6 7
8 3 18
5 8 17
8 5 3
5 5 3
5 4 8
1 8 13
1 7 5
7 4 13

output

44

数据范围

子任务1($14$分): $N,M \le 300$。

子任务2($21$分): $N,M \le 2000$。

子任务3($65$分): $N,M \le 200000$。

对于所有测试数据,满足$1 \le N,M \le 200000,1 \le A_i \le N,1 \le X_i,Y_i \le N,1 \le C_j \le 10^9$。

时间限制:$1\texttt{s}$

空间限制:$512\texttt{MB}$

下载

样例数据下载