T398695 「TZOI」Round 0 落叶

**Tips：请注意，本题目的空间限制为 $64$ MiB。** 秋天到了，树上纷纷落下了落叶……

校园里有一条路，路边长着许多树，每到秋天，树就会纷纷落下落叶。 有时候，一片重量为 $w_i$，颜色为 $c_i$ 的落叶会落到第 $x$ 片落叶的右边。 有时候，值日生小 H 会来清理落叶，将从左到右第一片颜色为 $k$ 的落叶至最后一片颜色为 $k$ 的落叶之间的所有落叶（包括这两片）全部清扫掉。 有时候，小 H 会关心，第 $l$ 片到第 $r$ 片落叶的总重为多少。 由于最后剩下的落叶总数会影响值日的考核，所以他还想知道最后会剩下多少落叶。 由于小 H 要忙着去 AK IOI 没有时间来解决这一问题，所以你需要帮一帮他。 ### 形式化题意 有一个序列 $a$，初始为空，你需要支持以下三种操作： - `1 x y z`：在第 $x$ 个元素的右边插入元素 $i$，其中 $w_i = y$，$c_i = z$。 **特别地，若 $x = 0$，则表示将元素 $i$ 插入序列 $a$ 的中第一个位置。** - `2 k`：删除 $L_k$ 至 $R_k$ 间的所有元素。 - `3 l r`：求 $\sum \limits_{i = l} ^ r w_{a_i}$。 其中，$L_k$ 表示 $a$ 中第一个满足 $c_{a_i} = k$ 的 $i$，$R_k$ 表示 $a$ 中最后一个满足 $c_{a_i} = k$ 的 $i$。 数据保证这样的 $i$ 存在。

第一行，一个正整数 $n$，表示操作次数。 接下去 $n$ 行，每行先输入一个正整数 $op$ 表示操作类型。 - 若 $op = 1$，接着输入三个整数 $x, y, z$，表示一片重量为 $y$，颜色为 $z$ 的落叶落到第 $x$ 片落叶的右边。 - 若 $op = 2$，接着输入一个整数 $k$，表示将第一片颜色为 $k$ 的落叶至最后一片颜色为 $k$ 的落叶之间的所有落叶全部清扫掉。 - 若 $op = 3$，接着输入两个整数 $l, r$，表示询问第 $l$ 片到第 $r$ 片落叶的总重为多少。

首先输出若干行，对于每个 $op = 3$ 的询问，输出对应的答案。

#### 【样例解释】 第 $1 \sim 4$ 次操作过后，叶子序列变为： | 下标 | $1$ | $2$ | $3$ | $4$ | | :----------: | :----------: | :----------: | :----------: | :----------: | | 重量 | $2$ | $7$ | $3$ | $4$ | | 颜色 | $2$ | $3$ | $2$ | $1$ | 第 $5$ 次操作查询第 $2 \sim 4$ 片叶子的重量和，为 $7 + 3 + 4 = 14$。 第 $1 \sim 9$ 次操作过后，叶子序列变为： | 下标 | $1$ | $2$ | $3$ | | :----------: | :----------: | :----------: | :----------: | | 重量 | $3$ | $2$ | $4$ | | 颜色 | $1$ | $2$ | $1$ | 第 $10$ 次操作查询第 $1 \sim 3$ 片叶子的重量和，为 $3 + 2 + 4 = 9$。 **对于样例 #2，满足测试点 $2$ 的限制。** **对于样例 #3，满足测试点 $3 \sim 4$ 的限制。** **对于样例 #4，满足测试点 $6$ 的限制。** **对于样例 #5，满足测试点 $9 \sim 10$ 的限制。** #### 【数据范围】 设当前序列 $a$ 的长度为 $m$。 对于所有数据，保证 $1 \le n \le 5 \times 10 ^ 5$，$1 \le c_i \le n$，$1 \le w_i \le 10 ^ 9$，$1 \le x, l, r \le m$，$l \le r$。 对于操作 $2$，保证当前序列 $a$ 中存在 $i$ 满足 $c_{a_i} = k$。 | 测试点编号 | $n \le$ | 特殊性质 | | :----------: | :----------: | :----------: | | $1$ | $200$ | 无 | | $2$ | $2000$ | 无 | | $3 \sim 4$ | $2 \times 10 ^ 5$ | 无 | | $5$ | $5 \times 10 ^ 5$ | A | | $6$ | $5 \times 10 ^ 5$ | B | | $7 \sim 8$ | $5 \times 10 ^ 5$ | C | | $9 \sim 10$ | $5 \times 10 ^ 5$ | 无 | 特殊性质 A：保证操作 $1$ 总是在 $a$ 的末尾添加元素。 特殊性质 B：保证不存在操作 $2$。 特殊性质 C：保证操作 $2$ 的数量不超过 $100$ 次。