×

计蒜客

  1. 题库
  2. 简单数据结构题
  3. 问答
  • 10.41%
  • 524288K

使用 #pragma 等方式开启优化可能导致您的提交无效。

有 $n$ 个魔法物品(编号为 $1,2,\cdots ,n$ )和 $m$ 对互斥关系,每对关系形如 $x,y$ ,表示编号为 $x$ 和 $y$ 的魔法物品会相互排斥。

回答 $q$ 次询问,每次询问给出 $k$ 个区间 $[l_1,r_1], [l_2,r_2],\cdots,[l_k,r_k]$ ,你需要知道这 $k$ 个区间的是否包含互斥的魔法物品。

输入格式

第一行一个整数 $T$ 和一个标识符 $f$ ,表示数据组数和该测试点是 $(1)$ 否 $(0)$ 在线。

对于每组数据:

第一行三个整数 $n,m,q$ 。

接下来 $m$ 行每行两个不同的整数 $x,y$ 。

接下来 $q$ 行,每行第一个整数为 $k$ ,接下来 $2\times k$ 个整数,依次为 $l_1, r_1, l_2, r_2,\cdots,l_k,r_k$ 。

变量的具体意义见题目描述。

输出格式

每组数据输出一行 $q$ 个字符,第 $i$ 个字符表示第 $i$ 个询问的答案。若一个询问没有包含互斥的魔法物品,则答案为 0 否则为 1

数据规模与约定

您可以点击“只看题面”以获得更好的阅读体验。

测试点编号$0\leq n\leq$$0\leq m\leq$$0\leq q\leq$$0\leq \sum k\leq$
1-2$2000$$2000$$2000$$2000$
3-4$10^5$$2000$$2000$$2000$
5-6$10^5$$10^5$$4000$$4000$
7-8$10^5$$10^5$$20000$$10^5$
9-10$10^5$$10^5$$10^5$$10^5$

以上为一组数据的范围 ,保证 $1\leq T \leq 5$ 。

为了便于编写程序,保证 $k$ 个区间互不相交且以左端点递增的顺序给出。

对于 $f=1$ 的 $8$ 、$10$ 号测试点(其余测试点 $f$ 均为 $0$ ) ,每个询问的 $2\times k$ 个区间端点需要异或上 $p$ , $p$ 表示此前有多少个询问的输出是 $1$ ,处理完一组数据后无需将 $p$ 置 $0$

输出时每行末尾的多余空格,不影响答案正确性

样例输入

2 0
5 2 3
1 2
3 4
2 1 3 4 5
1 2 3
2 2 3 4 5
6 3 2
1 2
1 3
5 6
1 1 2
1 2 3

样例输出

101
10

样例解释

第 $1$ 组数据有 $5$ 个物品,其中 $1$ 号与 $2$ 号排斥, $3$ 号与 $4$ 号排斥。第 $3$ 个操作( 2 2 3 4 5 )中两个区间的并是 $\{2,3,4,5\}$ ,包含 $3-4$ 这组排斥关系,故应输出 $1$ 。

想挑战这道题吗

  • main.c