分数: 625 点
问题陈述
定义字符串 S_0 和 S_1 as S_0= 0 和 S_1= 1.
你被给予 Q 查询,所以按顺序处理。
在 i第一个查询 (1\leq i\leq Q),给你一个整数三元组 (L_i,R_i,X_i).
让 S_{i+1} 是连接得到的字符串 S_{L_i} 和 S_{R_i} 按此顺序。 然后,找到 X_i- 第一个字符 S_{i+1}.
保证 X_i 的长度最多为 S_{i+1}.
约束
- 1\leq Q\leq 5\times 10^5
- 0\leq L_i,R_i\leq i
- 1\leq X_i\leq 10^{18}
- X_i 的长度最多为 S_{i+1}.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
Q L_1 R_1 X_1 L_2 R_2 X_2 \vdots L_Q R_Q X_Q
输出
输出 Q 行。 的 i第行 (1\leq i\leq Q) 应包含以下问题的答案 i第一个查询。
示例输入 1
7 0 1 1 0 0 2 1 1 1 2 3 2 2 4 3 5 4 2 6 7 6
示例输出 1
0 0 1 1 1 1 1
每个查询的处理方式如下:
- 在第一个查询中,连接 S_0=
0和 S_1=1得到 S_2=01。第一个字符为 S_2 is0,所以输出 0 在第一行。 - 在第二个查询中,连接 S_0=
0和 S_0=0得到 S_3=00。第二个字符为 S_3 is0,所以输出 0 在第二行。 - 在第三个查询中,连接 S_1=
1和 S_1=1得到 S_4=11。第一个字符为 S_4 is1,所以输出 1 第三行。 - 在第四个查询中,连接 S_2=
01和 S_3=00得到 S_5=0100。第二个字符为 S_5 is1,所以输出 1 在第四行。 - 在第五个查询中,连接 S_2=
01和 S_4=11得到 S_6=0111。第三个字符为 S_6 is1,所以输出 1 第五行。 - 在第六个查询中,连接 S_5=
0100和 S_4=11得到 S_7=010011。第二个字符为 S_7 is1,所以输出 1 在第六行。 - 在第七个查询中,连接 S_6=
0111和 S_7=010011得到 S_8=0111010011。第六个字符是 S_8 is1,所以输出 1 在第七行。