ABC-470-C - Inc, Dec, Xor 增减异或（注意题目条件限制：初始时 A 的所有元素均为 0，以及操作的摊还分析）

题目大意

Inc, Dec, Xor

有一个长度为 $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$ 的顺序无关。

输入从标准输入按以下格式给出：

N Q
query_1
query_2
⋮
query_Q

其中每个操作为以下两种格式之一：

1 x

2

输出 $Q$ 行。

第 $i$ 行（$1\le i\le Q$）输出第 $i$ 个操作处理完毕后 $A_1,A_2,\ldots,A_N$ 的按位异或值。

• $1\le N\le 5\times 10^5$

• $1\le Q\le 5\times 10^5$

• $1\le x\le N$

• 输入的所有值均为整数

2 5
1 2
1 2
1 1
2
2

1
2
3
1
0

处理第 $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$。

3 8
1 2
1 3
1 1
1 2
1 1
2
1 3
1 1

1
0
1
2
1
0
1
2

思路讲解

那么这道题目的关键点就是这个，初始时 $A$ 的所有元素均为 $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;
}

AC代码

https://atcoder.jp/contests/abc470/submissions/78274919

AI 代码

#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;
}

源代码

心路历程（WA，TLE，MLE……）