seuOJ450 - Infinite Binary String

题目类型：传统
输入文件：标准输入流
输出文件：标准输出流
时间限制：3000 ms
空间限制：1024 MiB
题目标签：春季, 夏季, 2023

题目描述

有一个无限长度的二进制字符串，字符串下标从 $0$ 开始，初始时该字符串每一位均为 $0$ ，即字符串为"000...000..."。

这里有三个对于字符串的操作:

+ x1 x2：将字符串 $[x1,x2]$ 位的所有数置为 $1$ 。
- x1 x2：将字符串 $[x1,x2]$ 位的所有数置为 $0$ 。
? k：查询字符串中第 $k$ 个 $0$ 的位置（ $k$ 从 $1$ 开始）。

输入格式

第一行，一个正整数 $q(1\le q \le 3⋅10^5)$ ，表示操作的次数。

下面的 $q$ 行，一行一个合法的操作。

对于所有操作，保证 $0 \le x_1 \le x_2 \le10^{18}$ , $1\le k \le 10^{18}$ 。

输出格式

对于每个查询，输出一个数字代表本次查询的答案。

样例

输入样例1：

输出样例1:

6
0

输入样例2：

20
? 878494275932786174
? 191206274092260882
+ 90709979082345650 155142141185936482
+ 517494333569600530 564853145673499945
+ 292058956849763644 736907297231575987
+ 250899541204107384 366738113984603143
? 259122961181491897
+ 149295125735363566 910059229663807234
- 109473047945647405 565286205925699217
- 883301298997052753 913230049662700033
+ 295634031302217703 309192531649055162
? 915522570298079114
+ 566433447467846309 754658072386278321
? 610866486668767338
+ 641530186302671096 742430918223400068
- 663857704259305552 687937536746193119
? 349435671598058575
? 282988533888872405
? 157927321439531627
? 899654625275143831

输出样例2:

878494275932786173
191206274092260881
809562879312551333
1265859232579571863
961203148950260087
381757240808197789
315310103099011619
176690390302833381
1225911455069749012

样例解释：
对于样例 $1$ ，在字符串的前 $0$ 至 $9$ 位的变化如下：
0000000000
1100000000
1101110000
1101110000
0001110000
0001110000