ABC-470-C - Inc, Dec, Xor 增减异或(注意题目条件限制:初始时 A 的所有元素均为 0,以及操作的摊还分析) · znzryb
## 题目大意
### Inc, Dec, Xor
<!-- Notion block type: heading_4 -->
有一个长度为 $N$ 的整数序列 $A=(A_1,A_2,\ldots,A_N)$,**初始时** $A$ **的所有元素均为** $0$**。**
给定 $Q$ 个操作,请按顺序依次处理。操作共有两种,格式如下:
- `1 x`:将 $A_x$ 的值增加 $1$。
- `2`:对每个 $i=1,2,\ldots,N$,若 $A_i \geq 1$,则将 $A_i$ 的值减少 $1$。
请求出每次操作处理完毕后 $A_1,A_2,\ldots,A_N$ 的按位异或值。
> **关于按位异或**
非负整数 $A,B$ 的按位异或 $A \oplus B$ 定义如下:$A \oplus B$ 在二进制表示下 $2^k$($k \geq 0$)位上的数字,当 $A,B$ 在二进制表示下 $2^k$ 位上的数字恰有一个为 $1$ 时为 $1$,否则为 $0$。
例如 $3 \oplus 5 = 6$(二进制表示为 $011 \oplus 101 = 110$)。
一般地,$k$ 个非负整数 $p_1,p_2,\ldots,p_k$ 的按位异或定义为 $(\dots((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k)$,可以证明其结果与 $p_1,p_2,\ldots,p_k$ 的顺序无关。
<!-- Notion block type: heading_4 -->
输入从标准输入按以下格式给出:
```
N Q
query_1
query_2
⋮
query_Q
```
其中每个操作为以下两种格式之一:
```
1 x
```
```
2
```
<!-- Notion block type: heading_4 -->
输出 $Q$ 行。
第 $i$ 行($1\le i\le Q$)输出第 $i$ 个操作处理完毕后 $A_1,A_2,\ldots,A_N$ 的按位异或值。
<!-- Notion block type: heading_4 -->
- $1\le N\le 5\times 10^5$
- $1\le Q\le 5\times 10^5$
- $1\le x\le N$
- 输入的所有值均为整数
<!-- Notion block type: heading_4 -->
<!-- Notion block type: heading_4 -->
```
2 5
1 2
1 2
1 1
2
2
```
<!-- Notion block type: heading_4 -->
```
1
2
3
1
0
```
<!-- Notion block type: heading_4 -->
处理第 $1$ 个操作后 $A=(0,1)$,$0,1$ 的按位异或为 $1$,故第 $1$ 行输出 $1$。
处理第 $2$ 个操作后 $A=(0,2)$,$0,2$ 的按位异或为 $2$,故第 $2$ 行输出 $2$。
处理第 $3$ 个操作后 $A=(1,2)$,$1,2$ 的按位异或为 $3$,故第 $3$ 行输出 $3$。
处理第 $4$ 个操作后 $A=(0,1)$,$0,1$ 的按位异或为 $1$,故第 $4$ 行输出 $1$。
处理第 $5$ 个操作后 $A=(0,0)$,$0,0$ 的按位异或为 $0$,故第 $5$ 行输出 $0$。
<!-- Notion block type: heading_4 -->
```
3 8
1 2
1 3
1 1
1 2
1 1
2
1 3
1 1
```
<!-- Notion block type: heading_4 -->
```
1
0
1
2
1
0
1
2
```
## 思路讲解
那么这道题目的关键点就是这个,**初始时** $A$ **的所有元素均为** $0$,以及我们只能增加一个元素啊,我们只要**实时维护一个这个正数的这个集合**,**遇到操作二暴力遍历**就可以解决了。
```cpp
int main() {
int n = readInt(), q = readInt();
/* alive:保存所有满足 A[i] >= 1 的下标,且保证【互不重复】。
* 维护方式:
* - A[x] 由 0 变 1 时 push_back(x)(这是唯一的“从零变非零”时机)
* - A[i] 由 1 变 0 时把它从 alive 中删除
* 因为 A[i] = 0 对异或没有贡献,所以只关心非零元素即可。
*/
vector<int> alive;
alive.reserve(min(n, q)); // 非零元素个数不会超过 min(N, 操作1次数)
int cur = 0; // cur = A[1] ^ A[2] ^ ... ^ A[n],实时维护
while (q--) {
int op = readInt();
if (op == 1) {
/* -------- 操作 1:A[x] += 1 -------- */
int x = readInt();
if (A[x] == 0) alive.push_back(x); // 从 0 变成非零,加入集合(不会重复)
cur ^= A[x]; // 先把旧值的贡献异或掉(旧值为 0 时是空操作)
++A[x];
cur ^= A[x]; // 再把新值的贡献异或上去
} else {
/* -------- 操作 2:所有非零元素 -1 --------
* 直接遍历 alive 暴力做。单次代价 = |alive|,
* 而这次操作让 sum(A) 恰好减少 |alive|,
* 由于 sum(A) 的总增量 <= 操作 1 的次数 <= Q,
* 所以所有操作 2 的总代价 <= Q,均摊 O(1)。
*/
int m = 0; // m 是“原地压缩”后新数组的长度
for (int idx : alive) {
cur ^= A[idx]; // 去掉旧值贡献
--A[idx];
cur ^= A[idx]; // 加上新值贡献(变成 0 时异或 0,无影响)
if (A[idx] > 0) alive[m++] = idx; // 仍非零则保留;归零的自然被覆盖删除
}
alive.resize(m); // 截断,完成删除
}
IO::writeInt(cur); // 每次操作后输出当前全局异或值
}
IO::flushOut();
return 0;
}
```
## AC代码
[https://atcoder.jp/contests/abc470/submissions/78274919](https://atcoder.jp/contests/abc470/submissions/78274919)
::: AI 代码
```cpp
#include <bits/stdc++.h>
using namespace std;
/* ==================== 快速读写 ====================
* N, Q 达到 5e5,输入输出规模在几 MB 级别,
* 用 fread / fwrite 缓冲避免 cin/scanf 的常数瓶颈。
*/
namespace IO {
const int BUF = 1 << 16;
char ibuf[BUF], *ip1 = ibuf, *ip2 = ibuf;
inline char gc() {
if (ip1 == ip2) { // 缓冲区空了就重新填充
ip2 = (ip1 = ibuf) + fread(ibuf, 1, BUF, stdin);
if (ip1 == ip2) return EOF;
}
return *ip1++;
}
// 本题所有数值都是非负整数,不需要处理负号
inline int readInt() {
int c = gc(), x = 0;
while (c < '0' || c > '9') c = gc(); // 跳过空格 / 换行
while (c >= '0' && c <= '9') { x = x * 10 + (c - '0'); c = gc(); }
return x;
}
char obuf[BUF], *op = obuf;
inline void flushOut() { fwrite(obuf, 1, op - obuf, stdout); op = obuf; }
inline void pc(char c) { if (op == obuf + BUF) flushOut(); *op++ = c; }
inline void writeInt(int x) {
char tmp[12]; int len = 0;
do { tmp[len++] = char('0' + x % 10); x /= 10; } while (x);
while (len) pc(tmp[--len]);
pc('\n');
}
}
using IO::readInt;
int A[500005]; // 当前序列,初始全 0(全局数组默认为 0)
int main() {
int n = readInt(), q = readInt();
/* alive:保存所有满足 A[i] >= 1 的下标,且保证【互不重复】。
* 维护方式:
* - A[x] 由 0 变 1 时 push_back(x)(这是唯一的“从零变非零”时机)
* - A[i] 由 1 变 0 时把它从 alive 中删除
* 因为 A[i] = 0 对异或没有贡献,所以只关心非零元素即可。
*/
vector<int> alive;
alive.reserve(min(n, q)); // 非零元素个数不会超过 min(N, 操作1次数)
int cur = 0; // cur = A[1] ^ A[2] ^ ... ^ A[n],实时维护
while (q--) {
int op = readInt();
if (op == 1) {
/* -------- 操作 1:A[x] += 1 -------- */
int x = readInt();
if (A[x] == 0) alive.push_back(x); // 从 0 变成非零,加入集合(不会重复)
cur ^= A[x]; // 先把旧值的贡献异或掉(旧值为 0 时是空操作)
++A[x];
cur ^= A[x]; // 再把新值的贡献异或上去
} else {
/* -------- 操作 2:所有非零元素 -1 --------
* 直接遍历 alive 暴力做。单次代价 = |alive|,
* 而这次操作让 sum(A) 恰好减少 |alive|,
* 由于 sum(A) 的总增量 <= 操作 1 的次数 <= Q,
* 所以所有操作 2 的总代价 <= Q,均摊 O(1)。
*/
int m = 0; // m 是“原地压缩”后新数组的长度
for (int idx : alive) {
cur ^= A[idx]; // 去掉旧值贡献
--A[idx];
cur ^= A[idx]; // 加上新值贡献(变成 0 时异或 0,无影响)
if (A[idx] > 0) alive[m++] = idx; // 仍非零则保留;归零的自然被覆盖删除
}
alive.resize(m); // 截断,完成删除
}
IO::writeInt(cur); // 每次操作后输出当前全局异或值
}
IO::flushOut();
return 0;
}
```
:::
::: 源代码
```cpp
```
:::
## 心路历程(WA,TLE,MLE……)