← 返回题目列表

AtCoder · kupc2018_i

I. 京都联盟

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

配点 : 400 点

問題文

左右排列 在由 N 方块表示的字段上。 M 一个物理敌人潜伏着。

敌人有宽度,i 第一个敌人是从左边开始 它藏在第 L_i, L_i+1, ..., R_i 格子里。 这些正方形中 1 如果您拥有的信息多于方块,您的分数就会增加。 s_i 。

起初,我们没有获得任何关于任何方块的信息。

Q 查询按顺序给出。 第 j 个查询是 从左开始当t_j, l_j, r_j 表示,当

  • t_j = 0 第 l_j, l_j+1, ..., r_j 方格的信息将丢失。 获取第
  • t_j = 1 第 l_j, l_j+1, ..., r_j 格的信息。

查找处理每个查询后的总分。

制約

  • 所有输入均为整数。
  • 1 \leq N, M, Q \leq 10^5
  • 1 \leq s_i \leq 10^9
  • t_j 是 0 或 1 。 当
  • 1 \leq L_i \leq R_i \leq N
  • 1 \leq l_j \leq r_j \leq N

入力

输入是按以下格式从标准输入给出的。

N M
L_1 R_1 s_1
L_2 R_2 s_2
:
L_M R_M s_M
Q
t_1 l_1 r_1
t_2 l_2 r_2
:
t_Q l_Q r_Q

出力

按顺序处理每个查询后输出总分。


入力例 1

4 2
1 2 5
4 4 8
3
1 1 4
0 2 4
0 1 1

出力例 1

13
5
0

每个查询均按如下方式进行。

  • 从左起 由于我们已经获得了第 1, 2, 3, 4 格的信息。
    • 从左起 由于我们已经获得了第 1 个方格的信息,因此分数 5 。
    • 从左起 由于我们已经获得了第 4 个方格的信息,因此分数 8 。
    • 总分是 13 。
  • 从左起 由于我们已经获得了第 2, 3, 4 方格的信息将丢失。 获取第
    • 此时 由于我们只有第 1 个方格的信息,因此总分是 5 。
  • 从左起 由于我们已经获得了第 1 方格的信息将丢失。 获取第
    • 由于我们没有任何方格的信息,因此总分是 小于或等于 0 。

入力例 2

6 3
2 3 5
2 4 4
6 6 3
5
1 1 2
1 4 6
0 2 2
1 3 4
0 6 6

出力例 2

9
12
7
12
9

入力例 3

100 10
38 64 158260522
61 81 24979445
53 77 433933447
21 32 211047202
49 53 731963982
1 12 430302156
47 57 880895728
61 74 189330739
44 98 404539679
10 49 492686568
10
1 55 81
1 32 72
0 14 67
1 13 24
1 45 56
1 9 38
0 7 61
1 4 26
1 45 58
0 44 99

出力例 3

2091939560
3527637312
1052783310
1756517080
3527637312
3957939468
1052783310
2186819236
3957939468
1134035926