配点 : 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