[yLOI2019] 珍珠

题目背景

别叹息太多告别,至少相遇很真切。 摇曳着盛放枯竭,时间从未停歇。 天涯浪迹的白雪,念念不忘山川蝴蝶。 听说有人孤负黑夜,偏要点亮人间的月。 ——银临《珍珠》

题目描述

扶苏给了你一个放珍珠的小匣子,这个匣子在左右两端都可以无限制的加入珍珠,珍珠在匣子里会排成一列,每次在左端加入珍珠,这个珍珠会被加入到这个珍珠序列的最左侧,在右端加入则会被加入到珍珠序列的最右侧。初始时,匣子是空的。 这些珍珠要么是黑色的,要么是白色的,为了方便起见,我们将白色看作 $0$,黑色看作 $1$。 在人鱼的世界中,定义颜色 $A$ **组合** 颜色 $B$ 为 $A\operatorname{nand}B$,读作 $A$ 与非 $B$。 定义 $A \operatorname{nand} B = \operatorname{not} (A \operatorname{and}B)$ ,其中 $\operatorname{and}$ 运算代表二进制与运算,$\operatorname{not}$ 运算代表二进制非运算。 定义位置 $x$ 到位置 $y$ 的组合和为: 从 $x$ 开始向 $y$ ,第一个颜色组合第二个颜色的结果组合第三个颜色,得到的结果组合第四个颜色……一直组合到位置 $y$ 的颜色的结果。特别的,$x = y$ 时,组合和为该颜色。 形式化的,设 $C_{x, y}$ 为序列 $A$ 从 $x$ 到 $y$ 的组合和,则 $$C_{x, y} = \begin{cases} C_{x, y - 1} \operatorname{nand} A_y & x < y \\ C_{x, y + 1} \operatorname{nand} A_y & x > y \\ A_x &x = y \end{cases}$$ 例如,给定序列 $1, 1, 0, 0$,从 $2$ 到 $4$ 的组合和为 $$(1 \operatorname{nand} 0) \operatorname{nand} 0 = 1 \operatorname{nand} 0 = 1$$ 从 $3$ 到 $1$ 的组合和为 $$(0 \operatorname{nand} 1) \operatorname{nand} 1 = 1 \operatorname{nand} 1 = 0$$ 从 $2$ 到 $2$ 的组合和为 $$1$$ 扶苏会在匣子的两边加入一些珍珠,或者给定一个位置 $p$,询问你从左向右数第 $1$ 个位置到从左向右数第 $p$ 个位置的组合和,或者从右向左数第 $1$ 个位置到从右向左数第 $p$ 个位置的组合和。

输入输出格式

输入格式


每个输入文件中都有且仅有一组测试数据。 数据的第一行是一个整数 $n$,代表扶苏的操作个数。 由于正常读入每个操作所需要的输入量过大,因此我们采用下面的生成器来生成每个操作。 ```cpp #include <cstdio> namespace Maker { typedef unsigned int uit; bool __sp; uit __x, __y, __z; int __type, __k, __m; const int L = 1 << 21; char buf[L], *front=buf, *end=buf; char GetChar() { if (front == end) { end = buf + fread(front = buf, 1, L, stdin); if (front == end) return -1; } return *(front++); } template <typename T> inline void qr(T &x) { char ch = GetChar(), lst = ' '; while ((ch > '9') || (ch < '0')) lst = ch, ch = GetChar(); while ((ch >= '0') && (ch <= '9')) x = (x << 1) + (x << 3) + (ch ^ 48), ch = GetChar(); if (lst == '-') x = -x; } template <typename T> inline void Begin(const T &x) { __type = x % 10; qr(__x); qr(__y); qr(__z); qr(__m); __sp = (__type == 3) || (__type == 4); __type &= 1; } inline uit __Next_Integer() { __x ^= __y << (__z & 31); __y ^= __z >> (__x & 31); __z ^= __x << (__y & 31); __x ^= __x >> 5; __y ^= __y << 13; __z ^= __z >> 6; return __x; } inline uit Rand() { return __Next_Integer(); } template <typename Tx, typename Ty, typename Tz> inline void Get_Nextline(Tx &x, Ty &y, Tz &z) { if (__m) { --__m; x = 0; y = 0; z = 0; qr(x); qr(y); qr(z); if (x == 0) { ++__k; } } else { x = Rand() & 1; y = Rand() & 1; if (__k == 0) { x = 0; } if (x == 0) { ++__k; if (__sp) { z = __type; } else { z = Rand() & 1; } } else { int dk = __k >> 1; if (dk == 0) { z = 1; } else { z = Rand() % dk + dk; } } } } } ``` 对于 C/C++ 选手,我们提供了如上的数据生成代码(C 选手请使用 C++ 语言提交),请将他们直接复制到你的代码中。 对于非 C/C++ 选手,请你自行按照上面代码的内容,自行写出你所使用语言的对应生成器。 下面的内容只针对 C++ 选手,请其他语言的选手自行按照对应语言的语法来完成代码。 在读入 $n$ 这个数字以后,请你调用 ``Maker`` 命名空间中的 ``Begin`` 函数,函数的参数为 $n$。换句话说,你的代码中需要出现类似 ``Maker::Begin(n)`` 的语句。 在调用完 ``Maker::Begin`` 函数以后,生成器就可以开始工作了。一共有 $n$ 次操作,每次操作时请你调用 ``Maker::Get_Nextline`` 函数,传入三个**整形**变量,(不妨设为 $x,y,z$),每次函数调用结束以后,$x,y,z$ 的值都会被修改,作为每次操作的参数。具体含义如下: > 每次操作会有三个整数作为参数, 依次记为 $x,y,z$ > > 如果 $x = 0$,则代表这是一次插入操作; > > 如果 $x = 1$,则代表这是一次查询。 > > 如果 $y = 0$,则代表插入操作是从左侧进行的,或者查询的位置是从左向右数的; > > 如果 $y = 1$,则代表插入操作是从右侧进行的,或者查询的位置是从右向左数的。 > > 如果 $x = 0$,则 $z$ 是一个非零即一的整数,代表插入珍珠的颜色,$0$ 代表白色,$1$ 代表黑色; > > 如果 $x = 1$,则 $z$ 代表查询从第一个到第 $z$ 个位置的组合和。组合和的方向和位置的方向由参数 $y$ 决定。 对于 C/C++ 选手,我们提供了模板程序([模板程序链接](https://www.luogu.org/paste/lk7wn4a1)),在这个程序中,已经做好了变量的读入和生成器的初始化,同时能够自动获取 $x,y,z$ 的值,你需要做的只是每次依照题意进行一个操作,最终输出答案。你可以自主选择是否使用这个模板,最终的评测得分与你的代码内容**无关**。 **特别提醒:不建议使用 ``fread`` 等直接从输入中大量读取信息然后保存的函数对 $n$ 进行读入,如果你非要这么做,请你自行重写 ``Maker::Begin()`` 中的读入部分。** 特别提醒:由于数据生成器使用了 ``fread`` 函数,程序不再能在控制台中输入数据,请在本地调试时**使用文件输入**,在提交时**不要使用文件输入**。在任何时候都**不需要使用文件输出**。 **从输入数据的第二行起,所有的数据都会被生成器自动读入(包括第二行),不需要你再行读入**。 输入数据的第二行是四个整数 $a,b,c,m$,其中 $a,b,c$ 是生成器的参数,$m$ 为需要额外读入的操作数。 为了在某种意义上避免因为生成的操作完全随机而产生的乱搞做法,我们将首先额外读入 $m$ 个给定的操作,然后再行随机。 以下 $m$ 行,每行三个整数 $x,~y,~z$,代表一次操作。 请特别注意,这 $m$ 次操作会被生成器**自动读入**。

输出格式


为了避免输出过大,请输出一行四个用空格隔开的整数,分别代表所有的查询中: > 一共有多少次查询的结果为 $1$。 > > 一共有多少次查询的操作编号为奇数且查询结果为 $0$。 > > 一共有多少次查询的操作编号为偶数且查询结果为 $1$。 > > 一共有多少次查询的操作编号是 $1024$ 的倍数且查询结果为 $0$。 定义第 $i$ 次操作的操作编号为 $i$。 **注意,一次插入也算做一次操作**。

输入输出样例

输入样例 #1

6
233 666 250 0

输出样例 #1

0 0 0 0

说明

#### 样例输入输出 1 解释 第一次操作,$x=0,y=1,z=0$,在匣子右端插入一个 $0$,那么匣子里的珍珠序列为 $\{0\}$ 第二次操作,$x = 1,y = 0,z = 1$,查询从左向右数第一个数到第一个数的组合和,答案是 $0$。 第三次操作,$x = 0,y = 1,z = 1$,在匣子右端插入一个 $1$,匣子里的珍珠序列为 $\{0,~1\}$ 第四次操作,$x = 1,y = 0,z = 1$,查询从左向右数第一个数到第一个数的组合和,答案是 $0$。 第五次操作,$x = 0,y = 0,z = 0$,在匣子左侧插入一个 $0$,那么匣子里的珍珠序列为 $\{0,~0,~1\}$ 第六次操作,$x = 0,y = 1,z = 1$,在匣子右侧插入一个 $1$,那么匣子的珍珠序列为 $\{0,~0,~1,~1\}$ 没有任何一次查询的结果满足【输出格式】中提到的任意一种情况,于是输出 ``0 0 0 0``。 --- #### 数据规模与约定 **本题采用多测试点捆绑测试,共有 $7$ 个子任务**。 - Subtask 1(5 points):$n = m = 0$。 - Subtask 2(15 points):$n = 1001$。 - Subtask 3(15 points):$n = 10^5 + 2$。 - Subtask 4(10 points):$n = 10^7 + 3$,对于所有 $x = 0$ 的操作,保证 $z = 1$。 - Subtask 5(10 points):$n = 10^7 + 4$,对于所有 $x = 0$ 的操作,保证 $z = 0$。 - Subtask 6(15 points):$n = 10^7 + 5$,$m = 0$。 - Subtask 7(30 points):$n = 10^7 + 6$。 对于全部的测试点,保证 $0 \leq n \leq 10^7 + 6$,$0 \leq m \leq \min(n, 10^6)$,$x, y \in \{0, 1\}$,且对于所有 $x = 0$ 的操作,保证 $z \in \{0, 1\}$,若设 $k$ 为在任一查询时匣子里的珍珠个数,则保证对于 $x = 1$ 的操作,$1 \leq z \leq k$,匣子为空时不会有查询操作。 --- #### 提示与说明 - 请注意常数因子对程序效率造成的影响。 - $n$ 的末位数字可以帮助你快速的判断测试点所属的子任务。 - 由于涉及到非操作,与非运算可能不具备一些常见位运算的运算律,请格外注意。 - std 使用 C++ 语言,保证时限是 std 用时的 1.5 倍以上,**但是不保证其他语言能够通过本题**。 - 对于 C++ 选手,如果你直接复制上面的生成器,保证生成器运行总时间不超过 300ms。