【杂记】一些思维题
Mier_Samuelle
·
·
算法·理论
题单
交互题
I
:::info[CF2222E Seek the Truth]{open}
交互题。
现有非负整数 k \in \{1,2,3\} 及 c \in [1,2^n)，定义 f(x)=\begin{cases} x\,\&\,c & k=1 \\ x \,|\,c & k=2 \\ x \oplus c & k=3 \end{cases}。
交互开始前，你可以选择 a \in [0,2^n)，并令 S=\{a\}。接下来，你可以执行以下两种询问：
- 选择 x \in [0,2^n)，将 f(x) 插入 S，交互库将返回 |S|；
- 选择 y \in [0,2^n)，交互库将返回 S 中 \ge y 的数的个数。
在 n+3 次询问内确定 k,c 的值。
:::
:::info[记号]{open}
- and/or/xor 分别表示按位与、按位或、按位异或；
- $\text{lowbit}(x)$ 表示 $x$ 的最低二进制位的位值。
:::
不妨先考虑已知 $k$ 如何求 $c$。我们知道：对于 $x \in [0,2^n)$，它 and 上 $2^n-1$ 一定等于它本身，or/xor 上 $0$ 也一定等于它本身。这意味着，只要在 $k=1$ 时插入 $f(2^n-1)$，或在 $k \in \{2,3\}$ 时插入 $f(0)$，就能使 $S=\{c\}$。然后使用操作二进行二分，便可在 $n$ 次查询内求出 $c$。
然后考虑如何确定 $k$。先令 $a=0$，考虑插入 $f(0)$，则在 $k=1$ 时 $S=\{0\}$，$k \in \{2,3\}$ 时 $S=\{0,c\}$。这样做虽然不能区分 $k \in \{2,3\}$，但对于求 $c$ 来说已经够了，于是先求出 $c$。
接下来要区分 $k \in \{2,3\}$，也就是要区分 or/xor，它们最大的区别是：or 一定是单调的，即一个数进行 or 运算一定不会变小，而 xor 则不一定。受此启发，我们考虑插入 $f(c-\text{lowbit}(c))$。$c-\text{lowbit}(c)$ 的二进制位是 $c$ 的一个子集，它 or 上 $c$ 一定等于 $c$，而 xor 上 $c$ 一定会变小。也就是说，此时若 $k=2$ 则 $S=\{0,c\}$，若 $k=3$ 则 $S=\{0,x,c\}$，那么根据返回的 $|S|$ 便可区分。
但不难发现当 $c-\text{lowbit}(c)=0$ 时上述方法会失效。此时 $c$ 的二进制位并没有非空子集，我们需要另一种方法。考虑插入 $f(c+2^{n-1})$，此时若 $k=2$ 则 $S=\{0,c,c+2^{n-1}\}$，若 $k=3$ 则 $S=\{0,c,2^{n-1}\}$，再用操作二查询 $c+2^{n-1}$ 便可区分。此时还有 $c=2^{n-1}$ 这个 corner case，改为插入 $f(c+1)$ 即可，区分的方式大致相同，不再赘述。
结算一下操作次数：
- 若 $k=1$，插入 $f(0),f(2^n-1)$ 需要 $2$ 次，二分查找需要 $n$ 次，一共 $n+2$ 次；
- 若 $k=2$，插入 $f(0)$ 需要 $1$ 次，二分查找需要 $n$ 次，后续区分 $k \in \{2,3\}$ 至多需要 $2$ 次，一共 $n+3$ 次。
符合要求，那么做完了。
:::success[Code]
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, t;
int insert(ll x){
cout << "I " << x << endl;
cin >> t;
return t;
}
int query(ll x){
cout << "Q " << x << endl;
cin >> t;
return t;
}
ll lowbit(ll x){
return x & (-x);
}
void answer(int k, ll c){
cout << "A " << k << " " << c << endl;
return;
}
void solve(){
cin >> n;
cout << 0 << endl;
int s = insert(0), k;
ll c;
if (s == 1){
k = 1;
insert((1ll << n) - 1);
}
else{
k = 2;
}
ll l = 1, r = (1ll << n) - 1, res;
while (l <= r){
ll mid = (l + r) >> 1;
if (query(mid)){
l = mid + 1;
res = mid;
}
else{
r = mid - 1;
}
}
c = res;
if (k == 2){
ll qc = c - lowbit(c);
if (qc){
if (insert(qc) == 3){
k = 3;
}
}
else{
if (c != (1ll << (n - 1))){
qc = c + (1ll << (n - 1));
}
else{
qc = c + 1;
}
insert(qc);
if (!query(qc)){
k = 3;
}
}
}
answer(k, c);
return;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--){
solve();
}
return 0;
}
```
:::
### II
:::info[[CF2219B2 Unique Values (Hard version)](https://codeforces.com/problemset/problem/2219/B2)]{open}
交互题。
有一长度为 $2n+1$ 的序列。$[1,n]$ 中有 $n-1$ 个数都在其中出现了 $2$ 次，有且仅有一个数在其中出现了 $3$ 次。你的目标是确定这三个位置。
你可以执行以下询问至多 $33$ 次：
- 选择一个子序列 $i_1,i_2,\dots,i_k$，交互库将返回在该子序列中出现了 $1$ 次的数的个数。
$n \le 10^3$。
:::
记这三个位置分别为 $p_1,p_2,p_3$，并设 $p_1<p_2<p_3$。
考虑如何判断一个子序列是否包含了全部的三个位置。对于出现次数分别为 $0,1,2,3$ 的数，它们对返回结果的贡献分别为 $0,1,0,0$。注意到只有出现了 $3$ 次的数具有奇偶性与出现次数不同的贡献。也就是说，只要返回结果与询问子序列长度的奇偶性不同，该子序列就一定包含了全部的三个位置。
$33 \approx 3 \cdot \log_2(2n+1)$，这提示我们进行二分。据此，可以先通过询问前缀，二分得出 $p_3$。然后在 $[1,p_3)$ 范围内二分，询问前缀时多带上一个 $p_3$，得出 $p_2$。最后用类似方法得出 $p_1$。
:::success[Code]
```cpp
#include <bits/stdc++.h>
using namespace std;
int query(int l, int r, int p1, int p2){
cout << "? " << r - l + 1 + (bool)p1 + (bool)p2 << " ";
for (int i = l; i <= r; i++){
cout << i << " ";
}
if (p1){
cout << p1 << " ";
}
if (p2){
cout << p2 << " ";
}
cout << endl;
int tmp;
cin >> tmp;
return tmp;
}
void solve(){
int n;
cin >> n;
n = 2 * n + 1;
int l = 1, r = n, res1, res2, res3;
while (l <= r){
int mid = (l + r) >> 1;
if ((query(1, mid, 0, 0) & 1) != (mid & 1)){
r = mid - 1;
res3 = mid;
}
else{
l = mid + 1;
}
}
l = 1, r = res3 - 1;
while (l <= r){
int mid = (l + r) >> 1;
if ((query(1, mid, res3, 0) & 1) != ((mid + 1) & 1)){
r = mid - 1;
res2 = mid;
}
else{
l = mid + 1;
}
}
l = 1, r = res2 - 1;
while (l <= r){
int mid = (l + r) >> 1;
if ((query(1, mid, res2, res3) & 1) != ((mid + 2) & 1)){
r = mid - 1;
res1 = mid;
}
else{
l = mid + 1;
}
}
cout << "! " << res1 << " " << res2 << " " << res3 << endl;
return;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--){
solve();
}
return 0;
}
```
:::
### III
:::info[[CF1392E Omkar and Duck](https://codeforces.com/problemset/problem/1392/E)]{open}
给定 $n,q$。交互开始前，你可以选定一个 $n \times n$ 的矩阵，其元素值域为 $[0,10^{16}]$。
随后有 $q$ 次查询，每次查询中有一条隐藏的 $(1,1)$ 到 $(n,n)$ 的路径，每步只能向右走或向下走。给定这条路径上所有格子的权值和 $k$，你需要据此确定这条路径。
2s，$n \le 25$，$q \le 1000$。
:::
可以发现，一条从左上角到右下角的路径，一定经过了每条副对角线恰好一次。一个自然的想法是，将每条副对角线视作一个数位，给该条对角线上的每个格子赋上不同的权值，直接把路径上经过的所有格子的权值拼成一个整数。
然而这样肯定塞不进 $10^{16}$。注意到 $2^{50} \le 10^{16}$，于是往二进制的方向想。假设我们已经确定了一条路径的一部分，现在位于 $(i,j)$，那我们其实只有 $(i+1,j),(i,j+1)$ 两个格子可以走，把这两个格子区分开即可，即一个赋 $2^{i+j+1}$，一个赋 $0$。
以样例为例，对于 $n=4$，构造以下矩阵：
$$\begin{bmatrix} 2^0 & 2^1 & 2^2 & 2^3 \\ 0 & 0 & 0 & 0 \\ 2^2 & 2^3 & 2^4 & 2^5 \\ 0 & 0 & 0 & 0 \end{bmatrix}$$
对于第一组询问，给定 $k=39=(0100111)_2$。这个二进制表示中的每一位就恰好对应了我们走的每一步，根据当前 $i$ 的奇偶性移动到对应的格子即可。
:::success[Code]
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[30][30];
signed main(){
int n, q;
cin >> n;
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++){
if (i & 1){
a[i][j] = 0;
}
else{
a[i][j] = 1ll << (i + j);
}
cout << a[i][j] << " ";
}
cout << endl;
}
cin >> q;
while (q--){
ll k;
cin >> k;
int x = 0, y = 0;
for (int i = 1; i < 2 * n; i++){
cout << x + 1 << " " << y + 1 << endl;
if (k >> i & 1){
if (x & 1){
x++;
}
else{
y++;
}
}
else{
if (x & 1){
y++;
}
else{
x++;
}
}
}
}
return 0;
}
```
:::
### IV
:::info[[CF2178E Flatten or Concatenate](https://codeforces.com/problemset/problem/2178/E)]{open}
有 $a,b$ 两数组，初始时均为 $[2^k]$。现进行以下两种操作若干次：
- 选择 $a,b$ 中的一个数组，并任选该数组的一个最大元素 $x$，将其替换为同一位置上的两个 $x/2$。要求 $x$ 为偶数；
- 令 $a,b$ 同时变为 $a+b$，其中 $+$ 为数组拼接。
现将两数组隐藏。你可以进行以下询问：
- 选择 $1 \le l \le r \le n$，交互库将返回 $a_l+a_{l+1}+\dots+a_r$ 的值。
使用不超过 $300$ 次询问确定 $a$ 中的最大值。
3s，$n \le 10^5$。
:::
最终序列可以拆成前后两个和相等的子段，且这些子段还可以递归地继续拆分。每次拆分时，序列的最大值一定在长度较短的那个子段中。证明显然。
二分即可。需要 $O(\log^2 n)$ 次询问。
:::success[Code]
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll query(int l, int r){
cout << "?" << " " << l << " " << r << endl;
fflush(stdout);
ll x;
cin >> x;
if (x == -1){
exit(0);
}
return x;
}
void solve(){
int n;
cin >> n;
int left = 1, right = n;
ll sum = query(1, n);
while (left < right){
ll val = sum / 2;
int l = left, r = right - 1, ans = -1;
while (l <= r){
int mid = (l + r) >> 1;
ll res = query(left, mid);
if (res == val){
ans = mid;
break;
}
else if (res < val){
l = mid + 1;
}
else{
r = mid - 1;
}
}
if (ans - left + 1 <= right - ans){
right = ans;
}
else{
left = ans + 1;
}
sum = val;
}
cout << "!" << " " << sum << endl;
fflush(stdout);
return;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--){
solve();
}
return 0;
}
```
:::
## 构造题
### I
:::info[[CF2242E Product of Closures](https://codeforces.com/problemset/problem/2242/E)]{open}
对于十进制数 $x$，记 $C(x)$ 为将 $x$ 的二进制表示（不含前导零）重复无数次得到的无限长的 01 串。$t$ 次询问，每次给定 $l,r,n$，对于所有 $l \le x<y \le r$，求字典序最小的 $C(x)\,\&\, C(y)$，输出其前 $n$ 位。
2s，$t \le 10^3$，$l<r \le 2^{30}$，$n \le 10^3$。
:::
要求的是字典序最小，那越高的位就要越小。由定义知 $C(x)$ 的开头一定是 $1$，我们想让第二个 $1$ 出现的位置越晚越好，那最理想的策略就是让 $x$ 取 $[l,r]$ 内最大的二的幂次（当然有可能取不到，后面会讲）。
假设 $x$ 取到了这个幂次（记为 $2^k$），我们还要再取一个 $y$，使 $C(x)\,\&\,C(y)$ 的字典序最小。经过一些手玩，我们发现取 $y=2^{k-1}$ 总是最优的（当然还是有可能取不到，后面也会讲）。这个不太好严格证明，让我们结合一个例子来感性理解。
例如 $l=1$，$r=10$，根据上述策略，我们会取 $x=8$，$y=4$，此时 $C(x)=100010001000\dots$，$C(y)=100100100100\dots$，$C(x)\,\&\,C(y)$ 计算如下：
$$
\begin{array}{r} \begin{array}{r} C(16)\\ C(8)\\ \end{array} \mathop{\&} \begin{array}{r} 1000100010001000\dots\\ 1001001001001001\dots\\ \end{array} \\ \hline \begin{array}{r} 1000000000001000\dots \end{array} \end{array}
$$
我们发现，对于 $x$ 中从左至右的每个 $1$，$y$ 中与它对齐的那一位每次都会偏移。当且仅当 $y$ 取 $2^{k-1}$ 时，每次只偏移一位，那么 $1$ 与 $1$ 对齐的时刻就越晚，字典序也就越小。
这样我们就解决了 $[l,r]$ 中至少可以取到两个二的次幂的情况。现在考虑取不到的情况，分为两种。
第一种，只有一个二的次幂可以取（记为 $2^k$）。此时 $x=2^k$ 是肯定要取上的，考虑 $y$ 怎么取。依旧感性理解，已知 $[l,x)$ 内所有数二进制下的位数相等，那么 $y$ 取得越小，$1$ 的位置就越靠后，字典序就越小。故我们取 $y=l$（若 $l=2^k$ 则取 $y=l+1$）。
第二种，没有任何二的次幂可以取。此时 $[l,r]$ 内所有数二进制下的位数都相等，问题等价于选出 $x,y$ 使 $x\,\&\,y$ 的字典序最小。那么 $x=l$ 肯定要取，我们还可以取一个 $y$ 来消去 $x$ 末尾的尽可能多的 $1$，同时要保证 $y>x$。那么我们找到 $r$ 二进制下与 $l$ 不同的最高位，将这一位右边的所有位全部清零，得到 $y$。
做完了。很多结论我没有严格证明，建议自己多手玩几个例子来理解。
:::success[Code]
```cpp
#include <bits/stdc++.h>
using namespace std;
void output(int a, int b, int n){
int lena = __lg(a) + 1, lenb = __lg(b) + 1;
for (int i = 0; i < n; i++){
int da = (a >> (lena - i % lena - 1) & 1);
int db = (b >> (lenb - i % lenb - 1) & 1);
cout << (da & db);
}
cout << "\n";
return;
}
void solve(){
int l, r, n;
cin >> l >> r >> n;
int k;
for (k = 0; (1 << (k + 1)) <= r; k++);
int a = (1 << k), b = (1 << (k - 1));
if (a >= l && b >= l){
output(a, b, n);
}
else if (a >= l){
b = (a == l ? l + 1 : l);
output(a, b, n);
}
else{
a = l;
int p = __lg(l ^ r);
b = (r >> p) << p;
output(a, b, n);
}
return;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--){
solve();
}
return 0;
}
```
:::
### II
:::info[[CF2232D Magical Tiered Cake](https://codeforces.com/problemset/problem/2232/D)]{open}
给定长度为 $n$ 的序列 $a$。有 $n$ 层蛋糕，层的大小从上至下递增。初始时所有蛋糕被放置在 A 盘，你需要将它们全部移动到 C 盘，可借助 B 盘中转。第 $i$ 层蛋糕可移动，当且仅当其上方恰好有 $a_i$ 层蛋糕。
每步操作中，你可以选择一层可以移动的蛋糕，将其移动到某个盘的顶部。你只能将蛋糕放置在比它大的蛋糕的上方。
在 $2^n$ 步操作内完成目标，或报告无解。
2s，$n \le 20$。
:::
变种汉诺塔问题。先回顾一下经典的汉诺塔问题，要将盘子 $x$ 从 A 移到 C，要先递归地将盘子 $1 \sim x-1$ 从 A 移到 B。
考虑套用这个策略，本题中，要将盘子 $x$ 从 A 移到 C，需要满足 $x$ 上方恰好有 $a_x$ 个盘子，就要先将盘子 $1 \sim x-a_x-1$ 移到 B，并将盘子 $x-a_x \sim x-1$ 叠在 $x$ 上面。
据此，定义递归函数 $f(x,\text{to})$ 表示将盘子 $1 \sim x$ 移到 $\text{to}$ 数组中指定的位置上，并用 $p_x$ 记录 $x$ 此时的位置。
- 若 $p_x=\text{to}_x$，则无需额外操作，执行 $f(x-1,\text{to})$ 即可。
- 否则，按照上述策略构建盘子 $1 \sim x-1$ 的目标位置数组 $\text{pos}$，执行 $f(x-1,\text{pos})$，将 $x$ 移到 $\text{to}_x$，再执行 $f(x-1,\text{to}_x)$。
接下来证明操作次数小于 $2^n$。记 $f_n$ 为将 $n$ 个盘子从 A 移到 C 的操作次数，则有 $f_n=2 \cdot f_{n-1}+1$，且 $f_0=0$，则 $f_n=2^n-1<2^n$。注意无解的情形需特判。
:::success[Code]
```cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 25;
int a[MAXN], p[MAXN], t[MAXN], n;
struct Opt{
int id, from, to;
};
vector <Opt> op;
void output(int id, int from, int to){
cout << id << " " << from << " " << to << "\n";
return;
}
void move(int x, int to[]){
if (x == 0){
return;
}
if (p[x] == to[x]){
move(x - 1, to);
return;
}
int tmp[25] = {};
for (int i = 1; i <= x - a[x] - 1; i++){
tmp[i] = 6 - to[x] - p[x];
}
for (int i = x - a[x]; i <= x - 1; i++){
tmp[i] = p[x];
}
move(x - 1, tmp);
op.push_back({x, p[x], to[x]});
p[x] = to[x];
move(x - 1, to);
return;
}
void solve(){
cin >> n;
for (int i = 1; i <= n; i++){
cin >> a[i];
p[i] = 1;
t[i] = 3;
}
for (int i = 1; i <= n; i++){
if (a[i] >= i){
cout << "NO\n";
return;
}
}
op.clear();
move(n, t);
cout << "YES\n";
cout << op.size() << "\n";
for (auto x : op){
output(x.id, x.from, x.to);
}
return;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--){
solve();
}
return 0;
}
```
:::
### III
:::info[[CF1450C2 Errich-Tac-Toe (Hard Version)](https://codeforces.com/problemset/problem/1450/C2)]{open}
给定 $n$，和一个 $n \times n$ 的由 $\texttt{X}$、$\texttt{O}$、$\texttt{.}$ 组成的字符矩阵。将所有 $\texttt{.}$ 替换为 $\texttt{X}$ 或 $\texttt{O}$，使任意一行或一列中不存在三个连续的相同字符。
1s，$n \le 300$。
:::
对于 $n=3$ 的情形，考虑以下局面：
$$\begin{matrix} \texttt{OXX} \\ \texttt{XOX} \\ \texttt{XXO} \end{matrix}$$
容易发现它是合法的，因为我们在一条对角线放满了 $\texttt{O}$，这阻止了三连 $\texttt{X}$ 的形成，又在两个角上放了 $\texttt{X}$，这阻止了三连 $\texttt{O}$ 的形成。
考虑推广这种构造方法。我们选定 $p,q$，满足 $0 \le p,q \le 2$ 且 $p \ne q$。对于任意 $(i,j)$，若 $(i+j) \bmod 3=p$，将 $c_{i,j}$ 改为 $\texttt{O}$，若 $(i+j) \bmod 3=q$，将 $c_{i,j}$ 改为 $\texttt{X}$。同样地，前者阻止三连 $\texttt{X}$ 的形成，后者阻止三连 $\texttt{O}$ 的形成。
接下来证明一定存在一组修改次数不超过 $\lfloor\frac{k}{3}\rfloor$ 的 $(p,q)$。每一个 $(i,j)$ 恰好在两组 $(p,q)$ 中被修改，所有位置在全部的六组 $(p,q)$ 中总共被修改了 $2k$ 次，则根据抽屉原理，必定存在一组 $(p,q)$，其修改次数不超过 $\lfloor\frac{2k}{6}\rfloor=\lfloor \frac{k}{3} \rfloor$。
:::success[Code]
```cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 310;
int n;
char c[MAXN][MAXN], ans[MAXN][MAXN];
void solve(){
cin >> n;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= n; j++){
cin >> c[i][j];
}
}
int idp = 0, idq = 0, minn = 1e9;
for (int p = 0; p <= 2; p++){
for (int q = 0; q <= 2; q++){
if (p == q){
continue;
}
int cnt = 0;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= n; j++){
if (c[i][j] == '.'){
continue;
}
if ((i + j) % 3 == p){
cnt += (c[i][j] == 'X');
}
if ((i + j) % 3 == q){
cnt += (c[i][j] == 'O');
}
}
}
if (cnt < minn){
minn = cnt;
idp = p;
idq = q;
}
}
}
for (int i = 1; i <= n; i++){
for (int j = 1; j <= n; j++){
if (c[i][j] == '.'){
cout << '.';
continue;
}
if ((i + j) % 3 == idp){
cout << 'O';
}
else if ((i + j) % 3 == idq){
cout << 'X';
}
else{
cout << c[i][j];
}
}
cout << "\n";
}
return;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--){
solve();
}
return 0;
}
```
:::
### IV
:::info[[P16325 【MX-J29-T4】XOR and Swap](https://www.luogu.com.cn/problem/P16325)]{open}
给定长度为 $2^n-1$ 的排列 $p,q$，下标从 $0$ 开始。
一次操作中，你可以：
- 选择两个不同的下标 $i,j$，使 $p_i \oplus p_j \le i \oplus j$；
- 交换 $p_i,p_j$。
使用不超过 $2.1 \times 10^6$ 次操作将 $p$ 变为 $q$。
5s，$n \le 20$。
:::
按照此类构造题的套路，如果我们能找出一个中转序列 $a$，使 $p,q$ 都能到达 $a$，就可以按 $p \rightarrow a \rightarrow q$ 的流程操作。
一个十分自然的想法是，令 $a=[0,1,2,\dots,2^n-1]$，即 $a_i=i$。对于任意一个 $p_i \ne i$ 的 $i$，设 $p_j=i$，则我们希望交换 $i,j$。题中给出的约束是 $p_i \oplus p_j \le i \oplus j$，现在已知 $p_j=i$，则可转化为 $p_i \oplus i \le p_j \oplus j$。也就是说，只要让每次选出的 $p_i \oplus i$ 尽可能小，就一定可以交换 $i,j$。
用一个优先队列维护所有 $p_i \oplus i$ 的值，每次取出最小的一个，将 $i,j$ 交换，并相应地更新队列，就可以在 $2^n$ 次操作内完成了。复杂度 $O(2^n \cdot n)$。
:::success[Code]
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int MAXN = 1.1e6;
int p[MAXN], q[MAXN], to[MAXN], n;
vector <pii> op1, op2;
vector <pii> solve(int a[]){
priority_queue <pii, vector<pii>, greater<pii>> qr;
for (int i = 0; i < (1 << n); i++){
to[a[i]] = i;
if (a[i] != i){
qr.push({a[i] ^ i, i});
}
}
vector <pii> res;
while (!qr.empty()){
int x = qr.top().first, i = qr.top().second, j = to[i];
qr.pop();
if ((a[i] ^ i) != x){
continue;
}
res.push_back({i, j});
swap(a[i], a[j]);
to[a[j]] = j;
if (a[j] != j){
qr.push({a[j] ^ j, j});
}
}
return res;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 0; i < (1 << n); i++){
cin >> p[i];
}
for (int i = 0; i < (1 << n); i++){
cin >> q[i];
}
op1 = solve(p);
op2 = solve(q);
cout << op1.size() + op2.size() << "\n";
for (auto [i, j] : op1){
cout << i << " " << j << "\n";
}
reverse(op2.begin(), op2.end());
for (auto [i, j] : op2){
cout << i << " " << j << "\n";
}
return 0;
}
```
:::
### V
:::info[[P14030 【MX-X20-T4】「FAOI-R7」连接时光 I](https://www.luogu.com.cn/problem/P14030)]{open}
给定长度为 $n$ 的整数序列 $a$，可能包含负数。
对于一个 $1 \sim n$ 的排列 $p$，定义 $f(p)$ 如下：
- 设置一张无向图 $G$，节点编号为 $1 \sim n$，初始时边集为空；
- 对于所有 $1 \le i<j \le n$，若 $p_i>p_j$，在 $G$ 中连边 $(i,j)$，边权为 $a_j$；
- 若 $G$ 不连通，则 $f(p)=-\infty$，否则 $f(p)$ 为 $G$ 中所有边的边权和。
构造排列 $p$，使 $f(p)$ 最大化，并求出该最大值。
- 特殊性质 B：$a_i<0$；
- 特殊性质 C：$i$ 为奇数时 $a_i>0$，$i$ 为偶数时 $a_i<0$。
2s，$n \le 10^5$。
:::
#### 特殊性质 B
贡献均为负，因此连的边越少越好，且要向尽可能大的 $a_i$ 连边。考虑每个节点都只向后缀 max 连边，记 $\text{suf}_i$ 为后缀 $[i,n]$ 的 max，则此时 $f(p)=\sum\limits_{i=2}^n \text{suf}_i$。容易证明，这是 $f(p)$ 的上界。
接下来要构造一组解来顶到这个上界。先找出所有后缀 max，并使所有不是后缀 max 的节点向后缀 max 连边。连完后会以后缀 max 为界，形成若干个连通块。以 $a=[-4,-1,-5,-3,-2]$ 为例，就是 $[-4,-1]$ 形成一个连通块，$[-5,-3,-2]$ 形成另一个连通块。
考虑这一步中 $p$ 应该怎么构造。我们不希望连通块之间产生多余的边，因此要让靠前的连通块的 $p_i$ 整体偏小。在上面的例子中，我们给 $[-4,-1]$ 分配 $1 \sim 2$，$[-5,-3,-2]$ 分配 $3 \sim 5$。在每个连通块内部，我们希望后缀 max 与前面的每个节点连边，且前面的节点之间不连边，将最小的 $p_i$ 分配给后缀 max，然后让前面的节点递增即可。在这个例子中，即 $p=[2,1,4,5,3]$。
然后还要把这些连通块拼在一起。我们希望每两个连通块间只连一条边，且这条边的负贡献尽可能小。观察可知，交换前一个连通块中最大的 $p_i$ 和后一个连通块中最小的 $p_i$，即可做到这一点。在这个例子中，即 $p=[3,1,4,5,2]$。不难发现，先前的所有性质都没有被破坏，且多出的一条边恰好连向后缀 max，可以顶到上界。
#### 特殊性质 C
将正数和负数分开考虑。我们想要吃满正数的贡献，因此让所有正数的 $p_i$ 递减。我们不想要负数产生贡献，因此让所有负数的 $p_i$ 递增。同时，我们也不想让正数向负数连边，因此要让正数的 $p_i$ 整体偏小。这样构造之后，负数会向它后面的正数连边，因此是连通的。
然而这样有个问题，如果最后一个数是负数，则没有任何节点会向它连边，它也不会向任何节点连边，整个图就会不连通。我们希望用一条边将最后一个节点拼到前面的完整连通块上。仿照性质 B 的做法，交换 $p_n$ 和前面最大的 $p_i$ 即可，同样不会破坏任何性质。
#### 正解
把两个特殊性质拼一下就是正解。你发现性质 C 和一般情况的唯一区别在于，一般情况下后面的负数可能不止一个。于是我们找到最靠后的一个非负数 $p_x$，对于 $[1,x]$，我们用性质 C 的构造方法，对于 $[x+1,n]$，我们用性质 B 的构造方法。注意让 $[1,x]$ 的 $p_i$ 整体偏小，以免产生多余的边。同样地，为了让这两部分连通，交换前面最大的 $p_i$ 和后面最小的 $p_i$ 即可。
构造出 $p$ 之后，用一棵树状数组算出 $f(p)$ 即可。做完了，复杂度 $O(n \log n)$。
:::success[Code]
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 2e5 + 10;
const ll INF = 0x3f3f3f3f3f3f3f3f;
vector <int> id;
ll a[MAXN];
int p[MAXN], suf[MAXN], n;
struct Fenwick_tree{
int v[MAXN];
void init(){
memset(v, 0, sizeof(v));
return;
}
int lowbit(int x){
return x & -x;
}
void update(int u, int x){
while (u <= n){
v[u] += x;
u += lowbit(u);
}
return;
}
int query(int u){
int res = 0;
while (u){
res += v[u];
u -= lowbit(u);
}
return res;
}
}tr;
void solve(){
cin >> n;
for (int i = 1; i <= n; i++){
cin >> a[i];
}
int pos = 0;
for (int i = n; i >= 1; i--){
if (a[i] >= 0){
pos = i;
break;
}
}
id.clear();
suf[n] = n;
id.push_back(n);
int cnt = 2;
for (int i = n - 1; i >= pos + 1; i--){
if (a[i] >= a[suf[i + 1]]){
suf[i] = i;
id.push_back(i);
cnt++;
}
else{
suf[i] = suf[i + 1];
}
}
id.push_back(pos);
int k = n, last = 0;
for (int i = 0; i < cnt - 1; i++){
for (int j = id[i] - 1; j >= id[i + 1] + 1; j--){
p[j] = k--;
}
p[id[i]] = k--;
if (id[i] > id[i + 1] + 1){
last = id[i] - 1;
}
else{
last = id[i];
}
if (i > 0){
swap(p[last], p[id[i - 1]]);
}
}
k = 1;
for (int i = pos; i >= 1; i--){
if (a[i] >= 0){
p[i] = k++;
}
}
last = 0;
for (int i = 1; i <= pos; i++){
if (a[i] < 0){
p[i] = k++;
last = i;
}
}
if (pos && pos != n){
if (last){
swap(p[last], p[id[cnt - 2]]);
}
else{
swap(p[1], p[id[cnt - 2]]);
}
}
tr.init();
ll ans = 0;
for (int i = 1; i <= n; i++){
ans += (tr.query(n) - tr.query(p[i] - 1)) * a[i];
tr.update(p[i], 1);
}
cout << ans << "\n";
for (int i = 1; i <= n; i++){
cout << p[i] << " ";
}
cout << "\n";
return;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--){
solve();
}
return 0;
}
```
:::
### VI
:::info[[P16995 【MX-S15-T1】「DLESS-5」Another OR Problem](https://www.luogu.com.cn/problem/P16995)]{open}
给定长度为 $n$ 的序列 $a$ 和非负整数 $k$，构造长度为 $n$ 的序列 $b$，使 $\sum b=k$ 且 $\bigoplus_{1 \le i \le n} a_i+b_i$ 最大化，并求出该最大值。
2s，$n \le 10^6$，$a_i,k < 2^{60}$。
:::
既然是按位或，那么肯定要拆位。从高到低考虑每个二进制位。当前位的贡献一定大于后面所有位的贡献之和，因此能填则填。如果当前这一位已经有 $1$ 了，则不管，否则找一个代价最小的 $a_i$ 填上。这样做看似会因为进位而损失一些低位的 $1$，但如果不找代价最小的，当前这一步便会产生额外的开销，可以证明，这些额外的开销一定会使结果不优。
这样填完一轮，$k$ 可能还剩下一些，由于是按位或，多填不影响答案，因此可以先把所有能填的 $0$ 全部填上。然而这样做完之后可能还剩。考虑此时的情形，每个 $a_i$ 肯定都有一串后缀 $1$，阻止我们把剩余的 $k$ 填进去。于是，我们选择后缀 $1$ 个数最少的 $a_i$，将剩下的所有 $k$ 全部填给它。损失的 $1$ 并不会影响答案，因为其它 $a_i$ 会补上这些位。唯一的例外是 $n=1$，特判掉即可。
做完了。复杂度 $O(n \log V)$。可能需要精细实现。
:::success[Code]
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e6 + 10;
int n;
ll a[MAXN], b[MAXN], k;
ll lowbit(ll x){
return x & -x;
}
void solve(){
cin >> n >> k;
for (int i = 1; i <= n; i++){
cin >> a[i];
}
if (n == 1){
cout << a[1] + k << "\n";
cout << k << "\n";
return;
}
for (int i = 1; i <= n; i++){
b[i] = 0;
}
for (int d = 60; d >= 0; d--){
bool flag = false;
ll maxv = -1;
int id = 0;
for (int i = 1; i <= n; i++){
ll val = a[i] + b[i];
if (val >> d & 1ll){
flag = true;
}
else if (maxv < val % (1ll << d)){
maxv = val % (1ll << d);
id = i;
}
}
if (!flag && k >= (1ll << d) - maxv){
b[id] += (1ll << d) - maxv;
k -= (1ll << d) - maxv;
}
}
ll ans = 0;
for (int i = 1; i <= n; i++){
ans |= (a[i] + b[i]);
}
cout << ans << "\n";
for (int d = 60; d >= 0 && k; d--){
for (int i = 1; i <= n; i++){
if (!((a[i] + b[i]) >> d & 1ll) && k >= (1ll << d)){
b[i] += (1ll << d);
k -= (1ll << d);
}
}
}
ll mind = 1e18;
int id = 0;
for (int i = 1; i <= n; i++){
if (mind > lowbit(a[i] + b[i] + 1)){
mind = lowbit(a[i] + b[i] + 1);
id = i;
}
}
b[id] += k;
for (int i = 1; i <= n; i++){
cout << b[i] << " ";
}
cout << "\n";
return;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int c, t;
cin >> c >> t;
while (t--){
solve();
}
return 0;
}
```
:::
## 其它
### I
:::info[[P14480 化作彗星](https://www.luogu.com.cn/problem/P14480)]{open}
给定一张 $k$ 个点 $m$ 条边的无向图。定义 $f(x,y)=0/1$ 表示 $x,y$ 在该图上是否有连边。
$t$ 组询问，每次给定长度为 $n$ 的序列 $a,b$，你可以对序列 $a$ 进行以下操作任意次：
- 选择 $1 \le i<n$，及 $1 \le x,y \le k$，满足 $f(a_i,a_{i+1})=f(x,y)=1$，令 $a_i \leftarrow x$，$a_{i+1} \leftarrow y$。
判断 $a$ 是否可以变为 $b$。
1s，$n \le 10^5$，$\sum n \le 10^6$，$m \le 3 \times 10^5$，$k \le 2 \times 10^5$。
:::
称图上度数为 $0$ 的节点为孤立点。显然孤立点是不可能改变的，因此两序列孤立点的位置和值都必须完全相同，否则无解。于是序列被孤立点切分为若干段，我们只需对每段分别判断。
可以发现以下性质：
- 所有存在连边的相邻元素对可以通过一步操作变得相同，可以视作同一个东西。以下称这样的元素对为 **块**。
- 对于形如 $(u,v,x)$ 的子段，若图上存在连边 $(u,v),(x,y)$，则可执行 $(u,v,x) \rightarrow (x,y,x) \rightarrow (x,u,v)$。即任意一个块都可以在所属段内自由移动。
- 对于形如 $(u,v,x)$ 的子段，若图上存在连边 $(u,v),(x,y),(y,z)$，则可执行 $(u,v,x) \rightarrow (x,y,x) \rightarrow (x,y,z) \rightarrow (u,v,z)$。即任意元素可借助一个块变成图上偶数步可达的任意元素。那么可以想到，对于任意一对相邻元素，只要它们奇数步可达，我们就可以通过此种操作让它们变成一个块。
那么可以得出一种构造：先用第三种操作形成尽可能多的块，再用这些块去转化剩下的元素，最后用第二种操作把顺序排好。这个过程可以用栈模拟。具体来说，对 $a,b$ 分别开一个栈，依次将元素入栈。每次入栈时检查：当前元素是否与栈顶元素奇数步可达，若是，则形成一个块，将栈顶弹出。最后检查两栈中剩余元素个数是否相等及对应元素是否偶数步可达即可。
需要特判一个 cornor：任意段初始时必须至少有一个块，否则无法进行任何转化。但特别地，若两序列已在段内完全相同，则需忽略这一条。
判断元素是否奇数步或偶数步可达可用并查集，判断元素间是否存在连边可用 set，复杂度 $O(n \log n)$。
:::success[Code]
```cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10, MAXK = 2e5 + 10;
int a[MAXN], b[MAXN], m, k, t, n;
bool ans;
set <int> to[MAXK];
stack <int> sta, stb;
struct DSU{
int fa[MAXK * 2];
void init(){
for (int i = 1; i <= 2 * k; i++){
fa[i] = i;
}
return;
}
int find(int x){
if (fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
void merge(int x, int y){
int a = find(x), b = find(y);
fa[a] = b;
return;
}
}dsu;
void check(int l, int r){
if (l > r){
return;
}
bool ok = true;
for (int i = l; i <= r; i++){
if (a[i] != b[i]){
ok = false;
}
}
if (ok){
return;
}
bool oka = false, okb = false;
for (int i = l; i < r; i++){
if (to[a[i]].find(a[i + 1]) != to[a[i]].end()){
oka = true;
}
if (to[b[i]].find(b[i + 1]) != to[b[i]].end()){
okb = true;
}
}
if (!oka || !okb){
ans = false;
}
if (sta.size() != stb.size()){
while (!sta.empty()) sta.pop();
while (!stb.empty()) stb.pop();
ans = false;
return;
}
ok = true;
while (!sta.empty()){
int x = sta.top(), y = stb.top();
sta.pop();
stb.pop();
if (dsu.find(x) != dsu.find(y)){
ok = false;
}
}
if (!ok){
ans = false;
}
return;
}
void solve(){
cin >> n;
for (int i = 1; i <= n; i++){
cin >> a[i];
}
for (int i = 1; i <= n; i++){
cin >> b[i];
}
for (int i = 1; i <= n; i++){
if (to[a[i]].empty() && !to[b[i]].empty()){
cout << "NO\n";
return;
}
if (to[b[i]].empty() && !to[a[i]].empty()){
cout << "NO\n";
return;
}
if (to[a[i]].empty() && to[b[i]].empty() && a[i] != b[i]){
cout << "NO\n";
return;
}
}
while (!sta.empty()) sta.pop();
while (!stb.empty()) stb.pop();
ans = true;
int last = 1;
for (int i = 1; i <= n; i++){
if (to[a[i]].empty()){
check(last, i - 1);
last = i + 1;
continue;
}
if (!sta.empty() && dsu.find(a[i]) == dsu.find(sta.top() + k)){
sta.pop();
}
else{
sta.push(a[i]);
}
if (!stb.empty() && dsu.find(b[i]) == dsu.find(stb.top() + k)){
stb.pop();
}
else{
stb.push(b[i]);
}
}
check(last, n);
cout << (ans ? "YES\n" : "NO\n");
return;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> m >> k >> t;
dsu.init();
for (int i = 1; i <= m; i++){
int u, v;
cin >> u >> v;
dsu.merge(u, v + k);
dsu.merge(u + k, v);
to[u].insert(v);
to[v].insert(u);
}
while (t--){
solve();
}
return 0;
}
```
:::
### II
:::info[[CF2248E Excuse for Breaks](https://codeforces.com/problemset/problem/2248/E)]{open}
给定 $n,m,d$，及序列 $p_1,p_2,\dots,p_m$ 和 $r_1,r_2,\dots,r_m$。保证 $p$ 严格递增。
对于任意长的 01 序列 $a$，定义函数 $f(a)$ 如下：
```
function f(a):
v := 0
c := 0
for i from 1 to length(a):
if a[i] is equal to 1:
v := v + d
c := c + 1
else:
c := 0
for j from 1 to m:
if c is equal to p[j]:
v := v + r[j]
if c is equal to n:
c := 0
return v
```
记 $I(a)$ 表示长度为 $|a|$ 的全 1 序列，判断是否存在某个 $a$ 使 $f(a)>f(I(a))$。
2s，$n,d \le 10^9$，$m \le 2000$。
:::
发现 $0$ 会把 $a$ 切分成若干段连续的 $1$，对于一个长度为 $x$ 的段，其贡献就是 $f(I(x))$。因此，若存在两个长度分别为 $x,y$ 的段，满足 $f(I(x))+f(I(y))>f(I(x+y+1))$，那么 $f(a)$ 可以 $>f(I(a))$，否则不可以。
进一步地，发现 $f(I(x))$ 具有周期性，即对于任意 $x>n$，有 $f(I(x))=f(I(x-n))+f(I(n))$。这将 $x,y$ 的枚举范围缩小到了 $[1,n]$。
最后，发现 $x,y$ 必须是会产生贡献的点，即必须存在 $i,j$ 满足 $p_i=x$，$p_j=y$，否则必然不优。至此，$x,y$ 的枚举范围缩小到了 $[1,m]$，可以 $O(m^2)$ 暴力枚举，双指针或二分计算 $f(I(x+y+1))$ 即可，复杂度 $O(m^2 \log m)$ 或 $O(m^2)$。
:::success[Code]
```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 2010;
int p[MAXN], r[MAXN], n, m, d;
void solve(){
cin >> n >> m >> d;
for (int i = 1; i <= m; i++){
cin >> p[i] >> r[i];
r[i] += r[i - 1];
}
for (int i = 1; i <= m; i++){
for (int j = 1; j <= m; j++){
int u = p[i], v = p[j];
if (u + v + 1 <= n){
int pos = upper_bound(p + 1, p + m + 1, u + v + 1) - p - 1;
if (r[i] + r[j] > r[pos] + d){
cout << "YES\n";
return;
}
}
else{
int pos = upper_bound(p + 1, p + m + 1, u + v + 1 - n) - p - 1;
if (r[i] + r[j] > r[pos] + r[m] + d){
cout << "YES\n";
return;
}
}
}
}
cout << "NO\n";
return;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--){
solve();
}
return 0;
}
```
:::
### III
:::info[[QOJ #1869 Power Station of Art](https://qoj.ac/problem/1869)]{open}
给定两张边集相同的无向图 $A,B$，不保证连通，每个节点有一颜色（红或黑）和一权值。每次可选择一张图和图上相邻的两个节点 $u,v$，交换它们的权值，且若同色则反转它们的颜色，否则保持不变。判定能否通过若干次操作使 $A,B$ 所有节点的权值和颜色对应相同。
3s，多测，设 $\sum n$ 为节点数之和，$\sum n \le 10^6$。
:::
这个操作不好处理，因为权值在换而颜色却没换，考虑转化一下，变成每次将权值和颜色都交换，并将颜色反转。容易证明这是等价的。转化后相当于每个节点上有一个二元组 $(a_i,c_i)$，可以拿着二元组在图上移动，每经过一条边 $c_i$ 就反转，而 $a_i$ 不变。
模拟赛搬这题的时候给了一个二分图的特殊性质，故考虑二分图怎么做。容易发现，将二元组从一个点移动到同部的点不会改变颜色，而移动到异部的点则会改变颜色。也就是说，左部的黑点只能变成右部的红点，而左部的红点只能变成右部的黑点，反之亦然。综上，我们得到了有解的一个必要条件：对于每组权值相同的节点，两图中 **左部黑点 + 右部红点** 数量相同，且 **左部红点 + 右部黑点** 数量相同。进一步地，我们发现只要上述条件成立，每次移动一个二元组至正确位置，一定可以构造出一种操作方案，故这就是有解的充要条件。
现在考虑不是二分图怎么做。既然不是二分图，那就肯定有奇环，在奇环上走一圈显然会使颜色反转，也就是说，所有颜色不匹配的节点都可以通过去奇环上走一圈来变得匹配。故只要同颜色点数量的奇偶性相同，且每种权值节点的数量相同，就一定有解。
综上，对于每个连通块，判断其是否是二分图，然后根据相应的条件判断即可。点权值域较大，需要离散化，复杂度 $O(n \log n)$。
:::success[Code]
```cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 10;
vector <int> adj[MAXN], ver[MAXN];
int a[MAXN], b[MAXN], idx[MAXN], st[MAXN], col[MAXN], cnt[2][MAXN], e[MAXN * 2], n, m, cur, len;
int lb[2][MAXN], lr[2][MAXN], rb[2][MAXN], rr[2][MAXN];
bool vis[MAXN];
string c, d;
void dfs(int u){
idx[u] = cur;
ver[cur].push_back(u);
for (int v : adj[u]){
if (idx[v]){
continue;
}
dfs(v);
}
return;
}
bool check(int u){
vis[u] = true;
for (int v : adj[u]){
if (vis[v]){
if (col[u] == col[v]){
return false;
}
}
else{
col[v] = col[u] ^ 1;
if (!check(v)){
return false;
}
}
}
return true;
}
void solve(){
cin >> n >> m;
for (int i = 1; i <= n; i++){
idx[i] = col[i] = vis[i] = 0;
adj[i].clear();
ver[i].clear();
}
for (int i = 1; i <= 2 * n; i++){
for (int j = 0; j <= 1; j++){
lb[j][i] = lr[j][i] = rb[j][i] = rr[j][i] = cnt[j][i] = 0;
}
}
for (int i = 1; i <= m; i++){
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
len = 0;
for (int i = 1; i <= n; i++){
cin >> a[i];
e[++len] = a[i];
}
cin >> c;
for (int i = 1; i <= n; i++){
cin >> b[i];
e[++len] = b[i];
}
cin >> d;
c = " " + c;
d = " " + d;
sort(e + 1, e + len + 1);
len = unique(e + 1, e + len + 1) - e - 1;
for (int i = 1; i <= n; i++){
a[i] = lower_bound(e + 1, e + len + 1, a[i]) - e;
b[i] = lower_bound(e + 1, e + len + 1, b[i]) - e;
}
cur = 0;
for (int i = 1; i <= n; i++){
if (!idx[i]){
cur++;
st[cur] = i;
dfs(i);
}
}
bool ok = true;
for (int i = 1; i <= cur; i++){
if (check(st[i])){
for (int u : ver[i]){
for (int j = 0; j <= 1; j++){
lb[j][a[u]] = lr[j][a[u]] = lb[j][b[u]] = lr[j][b[u]] = 0;
rb[j][a[u]] = rr[j][a[u]] = rb[j][b[u]] = rr[j][b[u]] = 0;
}
}
for (int u : ver[i]){
if (!col[u]){
if (c[u] == 'B'){
lb[0][a[u]]++;
}
else{
lr[0][a[u]]++;
}
if (d[u] == 'B'){
lb[1][b[u]]++;
}
else{
lr[1][b[u]]++;
}
}
else{
if (c[u] == 'B'){
rb[0][a[u]]++;
}
else{
rr[0][a[u]]++;
}
if (d[u] == 'B'){
rb[1][b[u]]++;
}
else{
rr[1][b[u]]++;
}
}
}
for (int u : ver[i]){
if (lb[0][a[u]] + rr[0][a[u]] != lb[1][a[u]] + rr[1][a[u]]){
ok = false;
}
if (lr[0][a[u]] + rb[0][a[u]] != lr[1][a[u]] + rb[1][a[u]]){
ok = false;
}
if (lb[0][b[u]] + rr[0][b[u]] != lb[1][b[u]] + rr[1][b[u]]){
ok = false;
}
if (lr[0][b[u]] + rb[0][b[u]] != lr[1][b[u]] + rb[1][b[u]]){
ok = false;
}
}
}
else{
for (int u : ver[i]){
cnt[0][a[u]] = cnt[0][b[u]] = cnt[1][a[u]] = cnt[1][b[u]] = 0;
}
for (int u : ver[i]){
cnt[0][a[u]]++;
cnt[1][b[u]]++;
}
for (int u : ver[i]){
// cout << cnt[0][a[u]] << " " << cnt[1][a[u]] << "\n";
if (cnt[0][a[u]] != cnt[1][a[u]]){
ok = false;
}
if (cnt[0][b[u]] != cnt[1][b[u]]){
ok = false;
}
}
int cnta = 0, cntb = 0;
for (int u : ver[i]){
cnta += (c[u] == 'B');
cntb += (d[u] == 'B');
}
if ((cnta & 1) != (cntb & 1)){
ok = false;
}
}
}
cout << (ok ? "YES" : "NO") << "\n";
return;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--){
solve();
}
return 0;
}
```
:::
### IV
:::info[[CF1495B Let's Go Hiking](https://codeforces.com/problemset/problem/1495/B)]{open}
给定长度为 $n$ 的排列 $p$。小 A 先选择下标 $1 \le x \le n$，随后小 B 选择下标 $1 \le y \le n$ 且 $x \ne y$。
小 A 和小 B 轮流操作。小 A 先手，小 B 后手。
- 轮到小 A 时，他可以选择 $1 \le x' \le n$，满足 $|x'-x|=1$，$x' \ne y$，且 $p_{x'}<p_x$，并令 $x \leftarrow x'$；
- 轮到小 B 时，他可以选择 $1 \le y' \le n$，满足 $|y'-y|=1$，$y' \ne x$，且 $p_{y'}>p_y$，并令 $y \leftarrow y'$。
最先无法操作的一方败。求有多少个初始下标 $x$ 可以使小 A 获胜。
1s，$n \le 10^5$。
:::
称满足 $a_i>a_{i-1}$ 且 $a_i>a_{i+1}$ 的位置 $i$ 为峰顶（规定 $a_0=a_{n+1}=0$），则小 A 必须选择高度严格最高（即往某个方向延续最长）的峰顶，才有可能获胜，这是容易证明的，因为如果不这样选，小 B 就会选择高度最高（可以不严格，因为小 B 是后手）的那个峰顶的山脚，那样就一定比小 A 活得久。
现在小 A 已经选择了最高的峰顶，考虑小 B 可以怎样让小 A 输掉。他可以在该峰顶较长一侧的半山腰上选择一个与峰顶距离（此处定义为节点数）为偶数的位置，这样小 A 就不敢往这边走了，不然会被小 B 堵死。这时候，如果另外一边的距离不够小 A 活得比小 B 久，他就会输掉。反之则小 A 获胜。
据此实现即可，需要注意一些细节。
:::success[Code]
```cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
int a[MAXN], s[MAXN], e[MAXN], n;
bool hill[MAXN];
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++){
cin >> a[i];
}
for (int i = 1; i <= n; i++){
if (a[i] > a[i - 1] && a[i] > a[i + 1]){
hill[i] = true;
}
}
int last = 1;
for (int i = 1; i <= n; i++){
s[i] = last;
if (a[i] > a[i + 1]){
last = i + 1;
}
}
last = n;
for (int i = n; i >= 1; i--){
e[i] = last;
if (a[i] > a[i - 1]){
last = i - 1;
}
}
int maxn = 0, cnt = 0, idx = 0;
for (int i = 1; i <= n; i++){
if (hill[i]){
int len = max(i - s[i] + 1, e[i] - i + 1);
if (len > maxn){
maxn = len;
cnt = 1;
idx = i;
}
else if (len == maxn){
cnt++;
}
}
}
if (cnt == 1){
int len = max(idx - s[idx] + 1, e[idx] - idx + 1);
if (len - (len & 1) >= min(idx - s[idx] + 1, e[idx] - idx + 1)){
cout << 0 << endl;
}
else{
cout << 1 << endl;
}
}
else{
cout << 0 << endl;
}
return 0;
}
```
:::
### V
:::info[[P16996 【MX-S15-T2】「DLESS-5」宇宙射线](https://www.luogu.com.cn/problem/P16996)]{open}
给定长度为 $n$ 的排列 $a$。现对其执行冒泡排序：
$$
\begin{aligned}
&\text{01: } \textbf{Algorithm } \text{BubbleSort}(a, n) \\
&\text{02: } \quad \textbf{for } i \leftarrow 1 \textbf{ to } n \textbf{ do} \\
&\text{03: } \quad\quad \textbf{for } j \leftarrow 1 \textbf{ to } n-i \textbf{ do} \\
&\text{04: } \quad\quad\quad \textbf{if } a[j] > a[j+1] \textbf{ then} \\
&\text{05: } \quad\quad\quad\quad \text{Swap}(a[j], a[j+1]) \\
&\text{06: } \quad\quad\quad \textbf{end if} \\
&\text{07: } \quad\quad \textbf{end for} \\
&\text{08: } \quad \textbf{end for} \\
&\text{09: } \textbf{end Algorithm}
\end{aligned}
$$
受宇宙射线影响，第 4 行的 `if` 语句执行时，恰有一次进入了相反的分支。给定 $n,a$，求运行 `BubbleSort(a,n)` 后，本质不同的 $a$ 的个数。
1s，$n \le 2 \times 10^6$。
:::
先回顾一下冒泡排序是怎么做的。一共要跑 $n$ 趟排序，其中第 $i$ 趟会通过交换相邻元素，将序列中第 $i$ 大的元素挪到正确的位置上，本题中就是将 $n-i+1$ 挪到下标 $n-i+1$ 处。
假设宇宙射线影响了第 $i$ 趟排序，导致 $n-i+1$ 没有被挪到正确的位置上。设此时 $a_x=n-i+1$，且 $a_y$ 最终占据了下标 $n-i+1$，则：
- 若 $x<y$，即 $a_x$ 在 $a_y$ 左边，则 $a_x$ 会不断向右挪，直到与 $a_y$ 相邻，此时发生错误，$a_x$ 没有和 $a_y$ 交换，然后 $a_y$ 不断向右挪，挪到 $n-i+1$ 为止。这就要求 $a_y$ 是区间 $[y,n-i+1]$ 内的最大值。
- 若 $x>y$，即 $a_x$ 在 $a_y$ 右边，则 $a_y$ 会不断向右挪，直到与 $a_x$ 相邻，此时发生错误，$a_x$ 和 $a_y$ 交换，然后 $a_y$ 不断向右挪，挪到 $n-i+1$ 为止。这就要求 $a_y$ 是区间 $[1,x) \cup (x,n-i+1]$ 内的最大值，即 $n-i$。
第一类贡献可用单调栈 $O(n)$ 统计，第二类贡献可简单地 $O(1)$ 统计，一共要跑 $n$ 趟排序，所以是 $O(n^2)$ 的，不可接受。
瓶颈在于每次都跑一遍单调栈，考虑只跑一次。容易发现，栈的深度减 $1$ 恰好就是 $n-i+1$ 右边的后缀最大值个数，即第一类贡献。第二类贡献也是容易统计的，因为若 $n-i$ 在栈内，则一定是紧挨着 $n-i+1$ 的，而不在栈内的情况就是会产生贡献的情况。跑完一趟排序后，更新单调栈可做到 $O(1)$。至此，我们便可以 $O(n)$ 统计贡献了。
然而还有一个 corner case，即宇宙射线没有影响排序的结果。容易发现，此时错误一定发生在 $n-i+1$ 左边的某两个元素上，即只要 $x>2$，就有可能出现这种情况。记录一下最大值的位置即可。
:::success[Code]
```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 2e6 + 10;
int a[MAXN], s[MAXN];
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
for (int i = 1; i <= n; i++){
cin >> a[i];
}
int t = 0;
for (int i = n; i >= 1; i--){
if (a[i] > s[t]){
s[++t] = a[i];
}
}
int ans = 0;
for (int i = n; i >= 2; i--){
ans += t - 1;
if (t > 1 && s[t] == s[t - 1] + 1){
t--;
}
else{
s[t]--;
ans++;
}
}
int pos1 = 1, pos2 = 2, nxt = 3, flag = 0;
for (int i = n; i >= 2; i--){
if (a[pos1] == i){
pos1 = pos2;
pos2 = nxt;
nxt++;
}
else if (a[pos2] == i){
pos2 = nxt;
nxt++;
}
else{
flag = 1;
break;
}
}
ans += flag;
cout << ans << endl;
return 0;
}
```
:::