← 返回题目列表

AtCoder · abc417_g

G. 二元猫

中文机器翻译题面 查看原题

分数: 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 is 0,所以输出 0 在第一行。
  • 在第二个查询中,连接 S_0=0 和 S_0=0 得到 S_3=00。第二个字符为 S_3 is 0,所以输出 0 在第二行。
  • 在第三个查询中,连接 S_1=1 和 S_1=1 得到 S_4=11。第一个字符为 S_4 is 1,所以输出 1 第三行。
  • 在第四个查询中,连接 S_2=01 和 S_3=00 得到 S_5=0100。第二个字符为 S_5 is 1,所以输出 1 在第四行。
  • 在第五个查询中,连接 S_2=01 和 S_4=11 得到 S_6=0111。第三个字符为 S_6 is 1,所以输出 1 第五行。
  • 在第六个查询中,连接 S_5=0100 和 S_4=11 得到 S_7=010011。第二个字符为 S_7 is 1,所以输出 1 在第六行。
  • 在第七个查询中,连接 S_6=0111 和 S_7=010011 得到 S_8=0111010011。第六个字符是 S_8 is 1,所以输出 1 在第七行。