「KDOI-06-S」签到题
题目背景
你正在追番,突然家长进来了,于是你假装在写一道数据结构题。
题目描述
定义一个长度为 $m$ 的数组 $v$ 是合法的,当且仅当经过若干次以下操作可以使 $v$ 中的所有元素相等:
* 选择四个整数 $a,b,c,d$($1\leq a\leq b\leq m$,$1\leq c\leq d\leq m$)满足 $b-a+1=d-c+1$,且 $v_a\operatorname{~or~}v_{a+1}\operatorname{~or~}\cdots\operatorname{~or~}v_b=v_c\operatorname{~or~}v_{c+1}\operatorname{~or~}\cdots\operatorname{~or~}v_d$,其中 $\operatorname{or}$ 表示按位或运算。接下来,将区间 $[a,b]$ 的数**复制下来再覆盖**到区间 $[c,d]$。**注意:区间 $\bm{[a,b]}$ 和 $\bm{[c,d]}$ 可能会相交。**
给出一个长度为 $n$ 的序列 $a_1,a_2,\ldots,a_n$ 以及 $q$ 次询问,每次询问给定两个正整数 $l,r$,你需要回答区间 $[l,r]$ 内的最长合法子区间的长度。
输入输出格式
输入格式
从标准输入读入数据。
**本题含有多组测试数据。**
输入的第一行包含两个整数 $T,id$,表示数据组数和测试点编号(样例的测试点编号为 $0$)。
对于每组测试数据数据,第一行两个正整数 $n,q$,表示序列长度与询问次数。
第二行 $n$ 个正整数 $a_1,a_2,\ldots,a_n$,表示序列 $a$ 中每个元素的值。
接下来 $q$ 行,每行两个正整数 $l,r$,表示询问的区间。
输出格式
输出到标准输出。
对于每组测试数据的每次询问,输出一行一个整数,表示区间 $[l,r]$ 内的最长合法子区间的长度。
输入输出样例
输入样例 #1
2 0
7 2
0 4 2 6 0 6 6
1 7
2 3
3 1
1 2 3
1 3
输出样例 #1
7
1
3
说明
**【样例解释 #1】**
对于第一组数据的第一个询问,最长的合法子区间为 $[1,7]$,以下是一种可能的操作序列:
1. 选择区间 $[1,4]$ 和 $[2,5]$,将区间 $[1,4]$ 中的数**先复制**下来,再覆盖到 $[2,5]$ 上,此时序列变为 $[0,0,4,2,6,6,6]$。
2. 选择区间 $[5,6]$ 和 $[3,4]$,此时序列变为 $[0,0,6,6,6,6,6]$。
3. 选择区间 $[4,7]$ 和 $[1,4]$,此时序列变为 $[6,6,6,6,6,6,6]$。
注意,操作**并不会**真正的修改原序列中的值。
对于第一组数据的第二个询问,最长的合法子区间为 $[2,2]$ 和 $[3,3]$。
**【样例 #2】**
见选手目录下的 `binary/binary2.in` 与 `binary/binary2.ans`。
这个样例满足测试点 $5\sim 8$ 的条件限制。
**【样例 #3】**
见选手目录下的 `binary/binary3.in` 与 `binary/binary3.ans`。
这个样例满足测试点 $25\sim 31$ 的条件限制。
**【样例 #4】**
见选手目录下的 `binary/binary4.in` 与 `binary/binary4.ans`。
这个样例满足测试点 $46\sim 50$ 的条件限制。
***
**【数据范围】**
对于所有数据保证:$1\le T\le 2\times 10^5$,$1\le n,q,\sum n,\sum q\le 2\times 10^6$,$0\le a_i < 2^{30}$。
| 测试点编号 | $\sum n\le$ | $\sum q\le$ | 特殊性质 |
| :----------: | :----------: | :----------: | :----------: |
| $1$ | $5$ | $5$ | 无 |
| $2\sim 4$ | $100$ | $100$ | 无 |
| $5\sim 8$ | $1000$ | $1000$ | 无 |
| $9\sim 14$ | $1000$ | $10^6$ | 无 |
| $15\sim 19$ | $6000$ | $10^6$ | 无 |
| $20\sim 24$ | $50000$ | $10$ | 无 |
| $25\sim 31$ | $10^5$ | $10^5$ | B |
| $32\sim 36$ | $2\times 10^5$ | $2\times 10^5$ | 无 |
| $37\sim 41$ | $5\times 10^5$ | $10^6$ | B |
| $42\sim 44$ | $5\times 10^5$ | $5\times 10^5$ | 无 |
| $45$ | $2\times 10^6$ | $2\times 10^6$ | A |
| $46\sim 50$ | $2\times 10^6$ | $2\times 10^6$ | 无 |
+ 特殊性质 A:保证序列 $a$ 中的每个数均在 $[0,2^{30})$ 之间均匀随机生成。
+ 特殊性质 B:保证对于任意 $1\le i\le n$,$a_i\le 3$。
***
**【提示】**
本题输入输出量较大,请使用适当的 I/O 方式。
**请注意常数因子对程序运行效率产生的影响。**
KDOI 出题组温馨提示:**多测不清空,爆零两行泪。**