← 返回比赛

已结束 GESP挑战赛#15

← 上一题下一题 →

A4759 | $聪明图$

时间限制1s

内存限制512MB

通过 / 提交0/0

题目描述

Yuilice会给聪明的你一个$n$个点的有向图，在初始时只有$i$连向$i+1$的边（$i < n$）。 你可以进行三种不同的操作: 1. 增加一条边 2. 删除一条边 （保证这条边存在） 3. 询问以$x$为起点能到达的点的个数。 现在，请你根据每一次操作3输出对应的内容～ 请注意我们保证每次操作后都会满足对于$i<n$存在从$i$连向$i+1$的边，可能出现重边或自环。

输入格式

第一行两个整数$n,Q$。表示点数和操作个数。 接下来$Q$行，每行表示一个操作，具体如下： 1. 1 x y ：增加一条从$x$连向$y$的边。 2. 2 x y ：删除一条从$x$连向$y$的边。 注意在有重边的情况下只会删除其中一条。 3. 3 x ：询问以$x$为起点能到达的点的个数。

输出格式

对于每个操作$3$输出一行，每行一个整数表示答案。

输入输出样例

输入 #1

输出 #1

对于所有测试点，满足$n,Q\leq 5 \times 10^5$。 测试点编号$n,Q$其他约束$1 \sim 2$$\leq 10^3$无$3 \sim 4$$\leq 10^4$无$5 \sim 8$$\leq 10^5$没有操作$2$，且操作$1$都在操作$3$之前$9 \sim 12$$\leq 10^5$没有操作$2$$13 \sim 16$$\leq 10^5$保证每次操作后最多有$10$条新增的边$17 \sim 18$$\leq 10^5$无$19 \sim 20$$\leq 5 \times 10^5$无

C++ 编辑器

输入

输出