← 返回题目列表

Codeforces · 1906/F

F. 价值最大化

中文机器翻译题面 查看原题

给定一个由 $$$N$$$ 整数组成的从 1 开始的数组:$$$A_1、A_2、\cdots、A_N$$$。最初,每个元素的值设置为$$$0$$$。

有 $$$M$$$ 操作(编号从 $$$1$$$ 到 $$$M$$$)。操作$$$i$$$由$$$\langle L_i, R_i, X_i \rangle$$$表示。如果执行$$$i$$$操作,则$$$L_i \leq j \leq R_i$$$的所有元素$$$A_j$$$将增加$$$X_i$$$。

您必须回答 $$$Q$$$ 独立查询。每个查询由 $$$\langle K, S, T \rangle$$$ 表示,它表示以下任务。选择满足$$$S \leq l \leq r \leq T$$$的范围$$$[l, r]$$$,并执行操作$$$l, l + 1, \dots, r$$$。查询的答案是$$$l$$$和$$$r$$$所有可能选择中执行完操作后$$$A_K$$$的最大值。

输入

第一行由两个整数 $$$N$$$ $$$M$$$ ($$$1 \leq N, M \leq 100\,000$$$) 组成。

接下来的 $$$M$$$ 行由三个整数 $$$L_i$$$ $$$R_i$$$ $$$X_i$$$ ($$$1 \leq L_i \leq R_i \leq N; -100\,000 \leq X_i \leq 100\,000$$$) 组成。

以下行由整数 $$$Q$$$ ($$$1 \leq Q \leq 100\,000$$$) 组成。

接下来的 $$$Q$$$ 行由三个整数 $$$K$$$ $$$S$$$ $$$T$$$ ($$$1 \leq K \leq N; 1 \leq S \leq T \leq M$$$) 组成。

输出

对于每个查询,在一行中输出一个整数,表示查询的答案。

示例

输入 #1

2 6
1 1 -50
1 2 -20
2 2 -30
1 1 60
1 2 40
2 2 10
5
1 1 6
2 1 6
1 1 3
2 1 3
1 1 2

输出 #1

100
50
0
0
-20

输入 #2

5 3
1 3 3
2 4 -2
3 5 3
6
1 1 3
2 1 3
3 1 3
3 2 3
2 2 3
2 2 2

输出 #2

3
3
4
3
0
-2

注意

示例输入/输出#1 的说明

对于查询$$$1$$$,解决方案之一是执行操作$$$4$$$ 和$$$5$$$。

对于查询$$$2$$$,解决方案之一是执行操作$$$4$$$、$$$5$$$ 和$$$6$$$。

对于查询$$$3$$$,唯一的解决方案是执行操作$$$3$$$。

对于查询$$$4$$$,唯一的解决方案是执行操作$$$1$$$。

对于查询$$$6$$$,唯一的解决方案是执行操作$$$2$$$。