Logo Universal Online Judge

UOJ

时间限制:2 s 空间限制:1024 MB

#2673. 小Z的作业

Statistics

题目描述

​ 教练给小Z布置了一个作业,教练给出了 $n$ 个命题,让他证明 $n$ 个命题全部为真。但是小Z非常的懒,一旦需要证明的命题数量大于 $K$,小Z就会摆烂不完成作业。因此小Z向他的好朋友黑恶卷怪小L求助。小L帮小Z证明了 $m$ 个等价关系,即对于 $1\leq i\leq m$,小L证明了 $u_i$ 和 $v_i$ 是等价的。小L把他的成果发给了小Z,但是网络质量不佳,小Z只收到了一个区间的等价关系证明。

​ 现在有 $q$ 条时间线,你需要对于每条时间线,求出假如小Z收到了第 $l\sim r$ 个等价关系的证明,小Z是否能够完成作业。

输入格式

​ 第一行四个整数 $n,m,K,tp$,分别表示小Z需要证明的命题个数,小L证明出的等价关系数,小Z摆烂的临界值,是否强制在线。

​ 接下来 $m$ 行,第 $i+1$ 行包含两个整数 $u_i,v_i$ ,表示小L的第 $i$ 个证明给出了 $u_i$ 和 $v_i$ 是等价的结论。

​ 第 $m+2$ 行一个整数 $q$ ,表示时间线的个数。

​ 接下来 $q$ 行,每行两个整数 $l_i,r_i$,表示小Z收到了第 $l_i\sim r_i$ 个证明,你需要求出小Z是否能够完成作业。如果小Z能够完成作业,输出 “Yes”(不包含引号),如果小Z会摆烂不完成作业,输出 “No”(不包含引号)。

​ 如果 $tp=1$,表示输入的 $l_i$ 和 $r_i$ 是经过加密的。用 $lans_{i-1}$ 表示 $1\sim i-1$ 个询问的答案按顺序从左到右拼接构成的二进制数(Yes视为 $1$,No视为 $0$),你需要令 $l_i\leftarrow \left(\left((l_i+lans_{i-1})\ \operatorname{mod}\ 2^{32}\right)\ \operatorname{mod}\ m\right)+1$,$r_i\leftarrow \left(\left((r_i+lans_{i-1})\ \operatorname{mod}\ 2^{32}\right)\ \operatorname{mod}\ m\right)+1$,然后如果 $l_i>r_i$ 则交换 $l_i,r_i$ 。

​ 以下参考代码片段实现了这一强制在线的过程:

unsigned lans=0;
for(int i=1;i<=q;++i){
    int l,r;
    std::cin>>l>>r;
    if(tp==1){
        l=(l+lans)%m+1;
        r=(r+lans)%m+1;
        if(l>r) std::swap(l,r);
    }
    //solve
    lans<<=1;
    if(Answer_Is_Yes) ++lans;
}

本题下发文件中的 online.cpp 会包含该代码段。

输出格式

​ 每行一个字符串 Yes 或者 No,表示小Z是否能够完成作业。

样例一

input

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

output

Yes
Yes
Yes
No
Yes

样例二

input

10 10 6 1
3 9
2 3
7 10
5 3
2 10
4 8
7 6
3 2
4 3
10 10
10
6 7
9 10
3 8
6 7
3 7
1 3
7 10
3 5
4 9
5 6

output

No
Yes
Yes
Yes
Yes
No
Yes
No
Yes
No

样例解释二

加密前的原始数据为

7 8
1 10
5 10
1 10
1 5
7 9
1 8
5 7
2 7
1 2

限制与约定

​ 对于 $100\%$ 的数据,满足 $1\leq n,m\leq 2\times 10^5$,$1\leq K\leq n$,$tp\in \{0,1\}$,$1\leq q\leq 5\times 10^5$,$1\leq u_i,v_i\leq n$,$1\leq l_i,r_i\leq m$,当 $tp=0$ 时,有 $l_i\leq r_i$ 。

子任务编号 分值 $n,m\leq$ $q\leq $ $tp\in$ 特殊性质
$1$ 5 $2\times 10^5$ $5\times 10^5$ $\{0,1\}$ $K=1$且$n>m+1$
$2$ 5 $2\times 10^5$ $5\times 10^5$ $\{0,1\}$ $K=n$
$3$ 10 $2\times 10^3$ $5\times 10^5$ $\{0\}$
$4$ 10 $2\times 10^5$ $10^3$ $\{0,1\}$
$5$ 25 $2\times 10^5$ $5\times 10^5$ $\{0\}$
$6$ 15 $10^5$ $10^5$ $\{0,1\}$
$7$ 30 $2\times 10^5$ $5\times 10^5$ $\{0,1\}$