P15792 「1&0OI R1」三月雨
题目背景
**这是一道函数式交互题。请使用合适版本的 C++ 提交，建议不要使用 C++14 (GCC 9)。**
>$\text{念往昔 \textcolor{66CCFF}我急旋慢转\textcolor{EE0000}你抚琴低吟}$
>
>$\text{{到如今 重唱此曲却已无}\textcolor{EE0000}你}$
>
>$\text{莫叹息 \textcolor{66CCFF}我再舞一曲\textcolor{EE0000}你意乱情迷}$
>
>$\text{空余忆 \textcolor{AA6680}{良辰美景}多可惜}$
过往的场景渐渐在某些方面模糊，在另一些方面却回响得愈发清晰。
即使相处的一切在日复一日的孤独中逐渐碎散，却仍未习惯身边失落的曾经存在的温度。
当试图吟哼镌刻着良辰美景的旧曲时，才发现太久的离别已使珍惜的记念闪烁不定。
不……不能忘却……
潸然的泪织成了细密的网，隔绝着窗外静谧的春夜。
题目描述
$\text{\textcolor{66CCFF}{1}}$ 常常追忆过去。
她现在正在试图想起 $\text{\textcolor{EE0000}{0}}$ 为她弹奏的那首曲子。曲子可以被看做一个由 $n$ 个音符组成的序列 $a$，**索引从 $0$ 开始**，其中的每个音符 $a_i(0 \le i < n)$ 可以用一个非负整数来代表。
不幸的是，由于缺乏绝对音感加之离别日久，她已经忘却了每个 $a_i$ 具体是什么，这给她的追忆旅程带来极大挑战。
然而，她仍留存着某『感觉』。感觉是一个数值，与乐段内每一个音符有关。对于一个从乐曲第 $l$ 个音符开始到第 $r$ 个音符结束的乐段 $[l,r]$，她有两种感觉：
- 一种感觉是这个乐段**每对不同音符的按位与**的和，即 $\displaystyle\sum_{l \le i < j \le r}{a_i \operatorname{and} a_j}$。
- 一种感觉是这个乐段**每对不同音符的按位异或**的和，即 $\displaystyle\sum_{l \le i < j \le r}{a_i \operatorname{xor} a_j}$。
这里，“每对”为无序对。$\operatorname{and}$ 和 $\operatorname{xor}$
分别表示按位与运算和按位异或运算。
由于 $\text{\textcolor{EE0000}{0}}$ 曾经非常多次以不同的开始和结尾向 $\text{\textcolor{66CCFF}{1}}$ 演奏曲子，所以 $\text{\textcolor{66CCFF}{1}}$ 确信对于任意的 $0 \le l < r < n$，她都还记得乐段 $[l,r]$ 的两种感觉。**注意这个乐段的长度至少为 $2$。**
因为过度悲伤，$\text{\textcolor{66CCFF}{1}}$ 的 OI 水平急剧下降，无法推算还原出曲子的模样，请你帮助她！你可以向她咨询她对于一些乐段的感觉，并最后告诉她原曲每个音符是什么。
**形式化地**，有一个长为 $n$ 的**未知**序列 $a(a_0,\ldots,a_{n-1})$，定义 $f_{\operatorname{and}}(l,r) = \sum_{l \le i < j \le r}{a_i \operatorname{and} a_j}$ 及 $f_{\operatorname{xor}}(l,r) = \sum_{l \le i < j \le r}{a_i \operatorname{xor} a_j}$。你可以进行若干次操作，每次操作为给定 $0 \le l < r < n$ 并查询 $f_{\operatorname{and}}(l,r)$ 或 $f_{\operatorname{xor}}(l,r)$。你最后需要确定 $a_0,\ldots,a_{n-1}$ 的值并返回序列 $a$。
---
**【交互格式】**
**你不需要也不应该实现 `main` 函数。**
你需要实现以下函数：
- `std :: vector sanyueyu(int n);`
- 参数 $n$ 表示乐曲的长度；
- 其应该返回一个持有 `int` 类型的 `vector`，长度为 $n$，且该 `vector` 的第 $i$ 个元素为 $a_i$。
你可以调用如下函数：
- `long long ask_and(int l, int r);`
- `long long ask_xor(int l, int r);`
- 参数 $l$ 和 $r$ 均表示询问乐段的左右端点。
- 分别返回乐段 $[l,r]$ 的第一种『感觉』和第二种『感觉』的值，即 $f_{\operatorname{and}}(l,r)$ 和 $f_{\operatorname{xor}}(l,r)$。
由于洛谷的交互机制，你应该将这些函数的原型声明在文件开头：
```cpp
std :: vector sanyueyu(int n);
long long ask_and(int l, int r);
long long ask_xor(int l, int r);
```
以下是一个您的程序可能的结构：
```cpp
// 这里引入你需要的头文件
/*
这里放置你要声明的全局变量
*/
std :: vector sanyueyu(int n);
long long ask_and(int l, int r);
long long ask_xor(int l, int r);
std :: vector sanyueyu(int n){
std :: vector ans;
/*
这里放置你的解题代码
*/
return ans;
}
```
输入格式
**以下为交互库的输入格式，你的程序不需要，也不应该从标准输入读入任何数据。**
第一行输入两个整数 $n,t$。$n$ 含义如题所述，$t$ 与你的测试点的得分有关，具体含义见【评分标准】。
第二行输入 $n$ 个整数，依次代表 $a_0\ldots a_{n - 1}$。
输出格式
交互库会与 Special Judge 部分进行交互，以使 Special Judge 返回特定的分数和错误信息。
**你的程序不需要，也不应该向标准输出输出任何数据。**
说明/提示
**【评分标准】**
对于每个测试点，你的程序若满足以下任意一条条件，将获得 $0$ 分：
1. 你的程序 CE/RE/TLE/MLE/UKE 了。
2. 你某一次调用 `ask_and` 或 `ask_xor` 时传入的 $l$ 和 $r$ 不满足 $0 \le l < r < n$。
3. 你返回的 `vector` 长度不为 $n$。
4. 对于你返回的 `vector`，存在一个 $i(0 \le i < n)$，使得你的 `vector` 第 $i$ 项不为 $a_i$。
对于情况 2~4，测试点将显示为 WA，并且尽管比赛中不会显示，$\text{\textcolor{66CCFF}{1}}$ 仍然会告诉你错误信息，分别为 `Error:2`、`Error:3` 和 `Error:4`，优先级递减。
否则，你将在该测试点获得分数。对于每个测试点，有一个特定的参数 $t$。设你的程序在该测试点调用 `ask_and` 和 `ask_xor` 的总次数为 $c$：
- 如果 $c \le t$，那么你将获得该测试点 $100\%$ 的分数。
- 否则，你将获得 $10\%$ 的分数，测试点将显示为 WA，并返回 `Error:1`（比赛时同样不可见）。
**【数据范围】**
对于所有测试点，有：
- $3 \le n \le 10^5$;
- $0 \le a_i \le 10^6$；
- $t \ge n + 1$。
每个测试点的具体数据范围见下表。
::cute-table{tuack}
| 测试点编号 | $n=$ | $t=$ | $a_i \le$ |
|:-:|:-:|:-:|:-:|
| $1$ | $3$ | $6$ | $10$ |
| $2$ | ^ | $5$ | $10^6$ |
| $3$ | ^ | $4$ | ^ |
| $4$ | $4$ | $8$ | $10$ |
| $5$ | ^ | ^ | $10^6$ |
| $6$ | ^ | $6$ | ^ |
| $7$ | ^ | $5$ | ^ |
| $8$ | $10^5$ | $10 ^ 5\times2$ | ^ |
| $9$ | ^ | $10^5+2$ | ^ |
| $10$ | ^ | $10^5+1$ | ^ |
**【checker 与交互库】**
为方便选手调试，本题提供了一个 checker，在附件中。它的输入格式与上文【输入格式】部分的格式相同。
使用时，你可以将你的代码粘贴到 checker 开头，或以任意合理的方式嵌入你的代码，然后运行 checker 并输入自造数据。
如果你的程序通过了该组自造数据，checker 的输出信息将以 `Accept!` 打头；否则将会以 `Error:1`~`Error:4` 打头，这些前缀的含义同【评分标准】。
checker 还会给出一些其他有利于调试的信息，请自行阅读这些信息以理解其含义。
请注意，交互库的实现与 checker **完全不同**，你的代码不应依赖 checker 的具体实现。
作为参考，交互库调用一次 `ask_and` 和 `ask_xor` 的时间复杂度均为 $O(\log \max \{a_i\})$。如果你的程序时间复杂度正确，交互库应该能在规定的时间内完成对你的程序的判定。