L3-026 传送门

Statement

Metadata

作者: WENG, Caizhi
单位: 浙江大学
代码长度限制: 16 KB
时间限制: 3500 ms
内存限制: 512 MB

平面上有 $2n$ 个点，它们的坐标分别是 $(1, 0), (2, 0), \cdots (n, 0)$ 和 $(1, 10^9), (2, 10^9), \cdots, (n, 10^9)$ 。我们称这些点中所有 $y$ 坐标为 $0$ 的点为“起点”，所有 $y$ 坐标为 $10^9$ 的点为终点。一个机器人将从坐标为 $(x, 0)$ 的起点出发向 $y$ 轴正方向移动。显然，该机器人最后会到达某个终点，我们设该终点的 $x$ 坐标为 $f(x)$ 。

在上述条件下，显然有 $f(x) = x$ 。不过这样的数学模型就太无趣了，因此我们对上述数学模型做一些小小的改变。我们将会对模型进行 $q$ 次修改，每一次修改都是以下两种操作之一：

+ $x'$ $x''$ $y$ : 在 $(x', y)$ 与 $(x'', y)$ 处增加一对传送门。当机器人碰到其中一个传送门时，它会立刻被传送到另一个传送门处。数据保证进行该操作时， $(x', y)$ 与 $(x'', y)$ 处当前不存在传送门。
- $x'$ $x''$ $y$ : 移除 $(x', y)$ 与 $(x'', y)$ 处的一对传送门。数据保证这对传送门存在。

求每次修改后 $\sum\limits_{x=1}^n xf(x)$ 的值。

输入格式

第一行输入两个整数 $n$ 与 $q$ ( $2 \le n \le 10^5$ , $1 \le q \le 10^5$ )，代表起点和终点的数量以及修改的次数。

接下来 $q$ 行中，第 $i$ 行输入一个字符 $op_i$ 以及三个整数 $x'_i$ , $x''_i$ and $y_i$ ( $op_i in {text{+' (ascii: 43)}, \text{-' (ascii: 45)}}-' (ascii: 45)}}Extra close brace or missing open braceop_i in {text{<code>+' (ascii: 43)}, \text{</code>-' (ascii: 45)}}-' (ascii: 45)}}$ , $1 \le x'_i < x''_i \le n$ , $1 \le y_i < 10^9$ )，代表第 $i$ 次修改的内容。修改顺序与输入顺序相同。

输出格式

输出 $q$ 行，其中第 $i$ 行包含一个整数代表第 $i$ 次修改后的答案。

输入样例

输出样例

样例解释 修改 | $f(1)$ | $f(2)$ | $f(3)$ | $f(4)$ | $f(5)$ | 结果 — | — + 1 3 1 | 3 | 2 | 1 | 4 | 5 | 51 + 1 4 3 | 3 | 2 | 4 | 1 | 5 | 48 + 2 5 2 | 3 | 5 | 4 | 1 | 2 | 39 - 1 4 3 | 3 | 5 | 1 | 4 | 2 | 42

Last update: May 4, 2022