#P10604. [2021年联测]想法

    ID: 9721 传统题 10500ms 512MiB 尝试: 3 已通过: 2 难度: 9 上传者: 标签>图论强连通分量数据结构贪心CF2600分块构造数学

[2021年联测]想法

想法(omoi)

【题目描述】

你正在思考这道题。

你的大脑中有nn个结点。有mm 条神经,第ii 条神经可以视作一条从结点uiu_{i} 连向结点viv_{i}的单向边。允许自环和重边;不同编号的神经分别切换,只有同一有序端点对的全部神经均未激活时,该对才没有直接连接。一开始,所有神经都处于激活状态。

在你思考这道题的qq个时刻中,你的大脑中可能有信息的传输,也可能有结构的变化。具体地,每个时刻都会发生以下两种事情之一:

• 1 i 切换第ii 条神经的状态。即:若原来为激活状态,则变为未激活;反之亦然。

• 2 s t 询问如果信息从结点ss出发,只沿着激活状态的神经传输,能否到达结点 tt。

【输入格式】

从标准输入读入。

第 1 行包含 3 个正整数n,m,qn,m,q,表示点数、边数与操作数。

接下来mm行,第ii 行包含 2 个正整数ui,viu_{i},v_{i},表示第ii 条神经从结点uiu_{i} 连向结点 viv_i。

接下来qq 行,每行 1 个操作,格式见题目描述。

【输出格式】

输出到标准输出。

对于每个 2 操作,若能则输出 YES,否则输出 NO。

【样例 1 输入】

5 6 7
1 2
1 3
2 4
3 4
3 5
4 5
2 1 5
2 2 3
1 3
1 4
2 1 4
1 3
2 1 5

【样例 1 输出】

YES
NO
NO
YES

【样例 2】

见选手目录下的 omoi/omoi2.in 与 omoi/omoi2.ans。

【样例 3】

见选手目录下的 omoi/omoi3.in 与 omoi/omoi3.ans。

【子任务】

本题开启捆绑测试。

对于所有数据,$1\le n\le 5\times 10^{4},1\le m\le 10^{5},1\le q\le 10^{5},1\le u_{i},v_{i}\le n$。

子任务 n≤n\le m≤m\le q≤q\le 特殊性质 分值
1 5,0005,000 10410^{4} 5,0005,000 无 15
2 2×1042\times 10^{4} 4×1044\times 10^{4} 3×1043\times 10^{4} 20
3 5×1045\times 10^{4} 8×1048\times 10^{4} 5×1045\times 10^{4}
4 10510^{5} A 15
5 无 30

• 特殊性质 A:没有 1 操作。