UOJ Logo Universal Online Judge

UOJ

附件下载 统计

跳蚤国王成功夺回了管理员权限,并剥夺了 Skip 蚤的权限,让其在 UOJ 上禁赛三年,且所在省的跳蚤 Rating 强制扣$100$。

跳蚤国王在检查题库时,发现 Skip 蚤获得权限期间,一位热爱线段树的 Picks 往 OJ 上传了一道没有 std 的题目。

因为之前的行为引起了民愤,出题人 Picks 拒绝向跳蚤国王透露这题的解法。正巧跳蚤国王准备筹办的 ULR #2 缺一道题,你能帮助跳蚤国王解开这道题以完成 ULR 的筹备吗?

给定一个长度为 $n$ 的操作序列。操作有 4 种:

  1. | x:将非负整数 $v$ 变为 $v\ \mathrm{bitor}\ x$,其中 $\mathrm{bitor}$ 为按位或操作;
  2. & x:将非负整数 $v$ 变为 $v\ \mathrm{bitand}\ x$,其中 $\mathrm{bitand}$ 为按位与操作;
  3. ^ x:将非负整数 $v$ 变为 $v\ \mathrm{bitxor}\ x$,其中 $\mathrm{bitxor}$ 为按位异或操作;
  4. + x:将非负整数 $v$ 变为 $(v + x) \bmod 2^{32}$。这一种操作保证 $x=1$。

所有操作的 $x$ 均为输入给定的非负整数,每一个操作的 $x$ 并不一定相同。操作从 $0$ 开始编号。

给定 $q$ 次询问,每次给出整数 $v,l,r,t$,求对数 $v$ 依次进行操作序列中区间 $[l,r]$ 中的操作后写成二进制形式,从低到高第 $t+1$ 个二进制位(即表示 $2^t$ 的位)的值,容易发现每组询问的答案只有可能是 $0$ 或 $1$。

本题部分子任务强制在线,详见输入格式和限制与约定部分。

输入格式

第一行三个整数 $n,q,op$ 表示操作序列长度、询问个数、询问解密参数。

接下来 $n$ 行依次描述操作序列中的每个元素。每行一个字符 $c$ 表示操作类型,后接一个整数 $x$ 表示操作参数。对于 + 操作保证 $x=1$。

接下来 $q$ 行每行四个整数 $v',l',r',t'$ 表示一组询问。注意询问进行了加密,解密方法如下:

  • 设需要解密的询问为第 $t$ 组询问,$ans_i$ 表示第 $i$ 组询问的答案,询问从 $0$ 开始编号;
  • 计算 $\mathrm{key} = op \times (\sum_{i=0}^{t-1} 2^ians_i) \mod 998244353$;
  • 则对应询问的真实参数如下: \begin{align} v &= (v' + \mathrm{key})\bmod 2^{32} \\ l &= \min\{(l'\ \mathrm{bitxor}\ \mathrm{key})\bmod n,(r'\ \mathrm{bitxor}\ \mathrm{key})\bmod n\} \\ r &= \max\{(l'\ \mathrm{bitxor}\ \mathrm{key})\bmod n,(r'\ \mathrm{bitxor}\ \mathrm{key})\bmod n\} \\ t &= (t'\ \mathrm{bitxor}\ \mathrm{key}) \bmod 32 \end{align}

注意解密过程中 $v$ 的计算方式与其他三者不同。注意无论询问是否强制在线都需要进行询问解密。

输出格式

一行一个长度为 $q$ 的 01 字符串,其中第 $i$ 个字符表示第 $i$ 组询问的答案。

样例一

input

6 6 0
^ 17
+ 1
^ 28
| 6
& 29
+ 1
3 0 2 1
8 1 5 3
7 1 4 0
12 0 4 2
31 0 2 1
50 1 2 0

output

100111

explanation

  • 第一个询问中有 $3 \xrightarrow[]{\mathrm{bitxor}\ 17} 18 \xrightarrow[]{+1} 19 \xrightarrow[]{\mathrm{bitxor}\ 28} 15 = (1111)_2$,其表示 $2^1$ 的二进制位,即从右往左数第 $2$ 个二进制位的值为 $1$,故第一个询问答案为 $1$;
  • 第二个询问中有 $8 \xrightarrow[]{+1} 9 \xrightarrow[]{\mathrm{bitxor}\ 28} 21 \xrightarrow[]{\mathrm{bitor}\ 6} 23 \xrightarrow[]{\mathrm{bitand}\ 29} 21 \xrightarrow[]{+1} 22 = (10110)_2$,其表示 $2^3$ 的二进制位,即从右往左数第 $4$ 个二进制位的值为 $0$,故第二个询问答案为 $0$。

样例二

input

6 6 1
^ 17
+ 1
^ 28
| 6
& 29
+ 1
3 13674554 3172638 395059201
7 6992286 3863695438 3302730626
6 122315987 1653449004 2270895617
11 277356193 306830369 65457603
22 2313889149 858796667 36414120
25 4135467483 3048814434 3407639193

output

100111

explanation

该样例解密后即为样例一。

样例三

见附加文件中 ex_sequence3.inex_sequence3.ans,该组样例满足子任务 $1$ 的性质。

样例四

见附加文件中 ex_sequence4.inex_sequence4.ans,该组样例满足子任务 $3$ 的性质。

样例五

见附加文件中 ex_sequence5.inex_sequence5.ans,该组样例满足子任务 $6$ 的性质。

限制与约定

对于 $100\%$ 的数据,$1 \leq n \leq 10^5 , 1 \leq q \leq 6 \times 10^5 , 0 \leq op \leq 1, 0 \leq x,v',l',r',t' < 2^{32}$。保证当操作为 + 操作时 $x=1$。

子任务编号$n \leq $$q \leq $$op \leq $特殊性质分值
$1$$3000$$5000$$1$$2$
$2$$4 \times 10^4$$2 \times 10^5$$0$只有 ^,+ 操作$8$
$3$$4 \times 10^4$$2 \times 10^5$$1$只有 ^,+ 操作$14$
$4$$10^5$$4 \times 10^5$$1$只有 ^,+ 操作$16$
$5$$10^5$$6 \times 10^5$$1$没有 + 操作$6$
$6$$4 \times 10^4$$2 \times 10^5$$0$$10$
$7$$10^5$$4 \times 10^5$$0$$10$
$8$$4 \times 10^4$$2 \times 10^5$$1$$14$
$9$$10^5$$6 \times 10^5$$1$$20$

本题数据中读入的最大文件大小约为 $\texttt{30MB}$,请注意算法常数如读入速度对运行时间带来的影响。

时间限制:$\texttt{2s}$

空间限制:$\texttt{512MB}$

下载

样例数据下载