問題
背景
Ikuta君试图将一排的广告牌涂成相同的颜色。与此同时,为了阻挠Ikuta君,Big Bridge 伯爵不断地增加或减少广告牌。在每次干扰发生时开始重新涂色,求将所有广告牌涂成相同颜色所需的时间。
課題
N(1 ≤ N ≤ 100,000) 个广告牌 x 排列在轴上。 i 第 i 个广告牌位于 x_i(-10^9 ≤ x_i ≤ 10^9) 位置,a_i(1 ≤ a_i ≤ 200,000) 颜色。Big Bridge 伯爵 Q(1 ≤ Q ≤ 100,000) 对看板进行增加或删除操作。各次增加和删除操作完成后,当Ikuta君开始重新涂漆时,求将所有看板涂成相同颜色需要多少时间。Ikuta君最初位于 x = 0 的位置,移动到x_p 减去 x_q 需要 |x_p - x_q| 的时间。此外,将a_p 颜色的看板涂成 a_q 颜色需要 |a_p - a_q| 时间。
配点
300
入力
输入按以下格式给出。
N x_1 a_1 : x_N a_N Q c_1 y_1 b_1 : c_Q y_Q b_Q
1 行表示最初排列的看板数量的整数, N 。 继续 N 行表示最初排列的看板位置和颜色的整数, x_i 、a_i 。 表示 N+2 行表示看板增加或删除次数的整数, Q 。 继续 Q 行表示看板增加或删除的整数, c_i 、y_i 、b_i 。 表示 c_i 表示查询的类型。 c_i = 1 时表示看板的增加操作,y_i 位置上增加 b_i 颜色的看板。 c_i = 2 时表示看板的删除,y_i 位置上的 b_i 颜色的看板将被删除。
制約
- 1 ≤ N ≤ 100,000
- -10^9 ≤ x_i ≤ 10^9
- 1 ≤ a_i ≤ 200,000
- 1 ≤ Q ≤ 100,000
- 1 ≤ c_i ≤ 2
- -10^9 ≤ y_i ≤ 10^9
- 1 ≤ b_i ≤ 200,000
- 对于删除查询,必定存在要被删除的看板。
- 在任意时点,看板的个数不会变为 0 。
- 在任意时点,同一位置不会存在多个看板。
部分点
针对此问题设置了部分分数。这个问题的测试用例 30 这些点还满足以下约束。
- 1 ≤ N ≤ 2,000
- 1 ≤ Q ≤ 2,000
出力
对于每次添加和删除之后的看板列,输出让Iocta君将所有看板涂成相同颜色所需的最短时间, 1 每行输出一次。
入力例1
1 10 1 3 1 2 2 1 -2 3 2 10 1
出力例1
3 9 3
1 在第几次查询添加看板时,位置 x=2 的颜色为 a=2 的看板,位置 x=10 的颜色为 a=1 的看板有,因此将 x=2 的看板涂成颜色 a=1 所需时间为 3 ,即可让所有看板颜色一致。
2 在第几次查询添加看板时,位置 x=-2 的颜色为 a=3 的看板,位置 x=2 的颜色为 a=2 的看板,位置 x=10 的颜色为 a=1 的看板有,因此将 x=-2 的看板涂成颜色 a=1 涂刷之后,x=2 的看板涂成颜色 a=1 所需时间为 9 ,即可让所有看板颜色一致。
3 在用查询删除了招牌的时候,位置 x=-2 的颜色为 a=3 的看板,位置 x=2 的颜色为 a=2 上仍然有招牌,所以将其中一个招牌涂成另一个招牌的颜色时,时间 3 ,即可让所有看板颜色一致。