当我对 2025 联合省选的 D1T2 感到不满时，我：

Redshift_Shine · 2025-03-06 13:42:48 · 生活·游记

追忆-加强版

题目背景

你看着这道题的 O(nq) 暴力通过了所有样例，十分不满。于是你出了一道题。

题目描述

给定一个 n 个点 m 条边的有向图 G，结点由 1 至 n 编号。第 i (1 \leq i \leq m) 条边从 u_i 指向 v_i，保证 u_i < v_i。节点 j (1 \leq j \leq n) 有两个权值 a_j, b_j，保证 [a_1, \ldots, a_n] 与 [b_1, \ldots, b_n] 均是 1 \sim n 的排列。

你需要进行 q 次操作。操作有以下三种:

• 1. $l \leq a_y \leq r$。 2. 图 $G$ 中存在一条 $x$ 到 $y$ 的有向路径，即存在整数 $k \geq 1$ 与 $k$ 个结点 $p_1, p_2, \ldots, p_k$，满足 $p_1 = x$，$p_k = y$，且对于所有 $1 \leq i < k$，图 $G$ 中存在从 $p_i$ 指向 $p_{i+1}$ 的有向边。特别地，图 $G$ 中总是存在一条 $x$ 到 $x$ 的有向路径。

为了通过上述题目，我们使用以下算法：

• 使用 bitset 在 O(\frac{nm}{\omega}) 的时间复杂度内计算并储存从每个点能够到达的点，并计算数组 p，满足 b_{p_i}=i。
• 对于操作 1，直接交换 a_x 和 a_y。
• 对于操作 2，首先交换 p_{b_x} 和 p_{b_y}，随后直接交换 b_x 和 b_y。
• 对于询问 3，从 n 到 1 降序枚举 i，若 x 可以到达 p_i 且 l\le a_{p_i}\le r，直接输出 i 并退出循环。若无法找到符合上述条件的 i，输出 0。

请对于所有的 a,b 的排列方式，m 条边的选择及其输入顺序，q 次询问的类型，参数及其输入顺序，输出询问 3 中 i 枚举次数的期望值，保留整数，向下取整。

一道正常的计数题本该就此为止。然而，由于原题的限制，在某一些测试点，你还需要省去上述所有排列方式中的一些不符合特殊限制的样例。所以，请认真阅读数据范围。

输入格式

本题有多组测试数据。输入的第一行两个整数 c, T，分别表示测试点编号和测试数据组数，接下来输入每组测试数据。样例满足 c = 0。

对于每组测试数据，

• 第一行三个整数 n, m, q，分别表示图 G 的节点数、图 G 的边数和操作次数。

输出格式

对于每组测试数据，输出一行一个整数，表示询问 3 中 i 的期望枚举次数。

输入输出样例 #1

输入 #1

0 1
1 1 1

输出 #1

0

说明/提示

【样例 1 解释】

该样例内有一组数据。

显然，在 n=m=q=1 的情况下，a 和 b 只能为 \set{1}。而询问有以下三种情况：

• 1 1 1
• 2 1 1
• 3 1 1 1

在第三种情况下，1 总能到达 1，且 1 本身必定满足条件，所以 i 的枚举次数为 1。

综上，对于所有情况，i 的期望枚举次数为 \frac{1}{3}，向下取整输出为 0。

【子任务】

对于所有测试点，

注意，以下表格中的特殊性质要求你输出的答案必须是对满足对应特殊性质的所有输入计算的期望。

• 特殊性质 A：\forall 1 \leq i \leq q, o_i \neq 1。
• 特殊性质 B：\forall 1 \leq i \leq q, o_i \neq 2。
• 特殊性质 C：\forall 1 \leq i \leq q, l_i = 1, r_i = n。
• 特殊性质 D：保证在每个 3 操作的时刻，\forall 1 \leq i \leq n, a_i = b_i。

【提示】

请注意本题特别的时空限制。