AT_kupc2018_i.League of Kyoto

在一个由 $N$ 个格子组成、左右一列排列的场地上，潜伏着 $M$ 个敌人。

每个敌人占据一定宽度，第 $i$ 个敌人潜伏在从左起第 $L_i,\ L_i+1,\ ...,\ R_i$ 个格子上。如果你获得了这些格子中至少一个格子的信息，就可以获得分数 $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$ 个格子的信息。

请你输出每次查询操作后获得的总分数。

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

$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 \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$

样例说明 1

每次查询的进展如下：

• 获得了从左起第 $1, 2, 3, 4$ 个格子的信息。
• 因为获得了第 $1$ 个格子的信息，获得分数 $5$。
• 因为获得了第 $4$ 个格子的信息，获得分数 $8$。
• 总分数为 $13$。
• 失去了从左起第 $2, 3, 4$ 个格子的信息。
• 此时只获得了第 $1$ 个格子的信息，总分数为 $5$。
• 失去了从左起第 $1$ 个格子的信息。
• 没有获得任何格子的信息，总分数为 $0$。

由 ChatGPT 4.1 翻译