Codeforces Round 1123 (Div. 2)

点击查看题面

A. Turn Into a Palindrome

题目大意

给定一个长度为 $n$ 的由小写英文字母组成的字符串 $s$，以及一个指定的小写英文字符 $c$。

每次操作可以花费 $1$ 枚硬币，选择字符串中的任意一个位置 $i$（$1\le i\le n$），并将其替换为字符 $c$。

求将字符串 $s$ 转换为回文字符串所需花费的最少硬币数量。

数据范围：

• 测试用例组数 $t$ 满足 $1\le t\le 500$。
• 字符串长度 $n$ 满足 $1\le n\le 100$。
• 字符 $c$ 及字符串 $s$ 均由小写英文字母组成。

---

思路

根据回文字符串的定义，对于所有对称位置的下标对 $(l,r)$（其中 $l<r$ 且 $l+r=n-1$，以 $0$-indexed 为准），必须满足 $s[l]=s[r]$。

1. 对称位置的独立性： 对于任意一对对称位置 $\{l,r\}$，对其字符的修改完全独立，不会影响其他位置的字符匹配状态。因此，可以采用双指针法，从两侧向中间逐对考察 $(s[l],s[r])$。
2. 操作特性的限制： 每次操作只能将字符修改为给定的字符 $c$，而无法修改为其他任意字符。这意味着：

• 若要让对称位置的一对不同字符相等，其最终字符必须都变为 $c$（因为只能向 $c$ 转化）。

3. 分类讨论：

• 情况 1：$s[l]=s[r]$ 该对位置天然对称，无需进行任何修改，代价为 $0$。
• 情况 2：$s[l]\ne s[r]$ 必须使两端字符均变为 $c$：
• 若其中恰好有一个字符已经是 $c$（即 $s[l]=c$ 或 $s[r]=c$），则只需将另一个字符变为 $c$，花费 $1$ 枚硬币。
• 若两者均不为 $c$，则必须将两端的字符都变为 $c$，花费 $2$ 枚硬币。

使用艾弗森括号（Iverson bracket）可统一表示为：

$$\text{cost}=2-[s[l]=c]-[s[r]=c]$$

4. 奇数长度中心点： 若 $n$ 为奇数，中心位置字符 $s[\lfloor n/2\rfloor ]$ 与自身对称，不需要进行任何变换，花费为 $0$。

遍历所有对称对并累加代价，即为最小花费。

---

复杂度分析

• 时间复杂度：每个测试用例中双指针从两端向中心遍历，一共检查 $\lfloor n/2\rfloor$ 对字符，单次判定与转移为 $O(1)$。故单组用例时间复杂度为 $O(n)$，总时间复杂度为 $O(\sum n)$，在给定范围内运算量极小，可在 $1\text{ s}$ 内轻松通过。
• 空间复杂度：仅使用常数个辅助变量维护双指针与统计和，额外空间复杂度为 $O(1)$（若计入存储字符串本身的空间，则为 $O(n)$）。

---

参考代码

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

void fc() {
    int n;
    char c;
    std::cin>>n>>c;
    std::string s;
    std::cin>>s;
    int l=0,r=n-1;
    int ans=0;
    while(l<r){
        if(s[l]==s[r]){
            l++,r--;continue;
        }

        ans+=2-(s[l]==c)-(s[r]==c);
        l++,r--;
    }
    std::cout<<ans<<"\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    std::cin>>t;
    while (t--) fc();
    return 0;
}

B. Fashionable Array

题目大意

定义一个数组的众数（Mode）为出现次数最多的元素；若存在多个元素出现次数相同且均为最多，则取其中数值最大的元素作为众数。

现给定一个包含 $n$ 个整数的数组 $a$。允许将数组 $a$ 中的元素按任意顺序重新排列。目标是寻找一种排列方式，使得重排后所有前缀的众数之和最大，即最大化：

$$\sum _{i=1}^n\text{mode}(a[1\dots i])$$

输出任意一种能够达到最大和的重排方案。

数据范围：

• 测试用例组数 $t$ 满足 $1\le t\le 500$。

• 数组大小 $n$ 满足 $1\le n\le 100$。

• 数组元素 $a_i$ 满足 $1\le a_i\le 100$。

---

思路

1. 众数判定机制分析

根据题目定义，当多个数值的频次并列最高时，众数选取数值最大者。这意味着在相同频次下，较大数值天然具备更高的优先级。

设当前前缀中元素的最大出现频次为 $k$。若要使前缀的众数尽可能大，应优先让当前剩余元素中数值最大的数率先达到频次 $k$；而在后续引入其他同样达到频次 $k$ 的元素时，只要这些元素的值均小于该最大值，根据打破平局（tie-breaker）的规则，众数将始终锁定在最先到达频次 $k$ 的那个最大值上。

2. 分层贪心构造策略

考虑按“频次层级”将所有元素进行分轮构造：

• 第 1 轮：取出所有当前出现次数 $\ge 1$ 的不同元素，按从大到小（降序）排列输出。

• 设当前各相异元素为 $x_1>x_2>\cdots >x_m$。

• 放入 $x_1$ 后，前缀众数为 $x_1$（频次为 $1$）。

• 依次放入 $x_2,x_3,\dots ,x_m$ 时，所有已加入元素的频次均为 $1$；因 $x_1$ 为其中的最大值，在接下来的整个区间内，每个前缀的众数均保持为 $x_1$。

• 第 $r$ 轮（$r\ge 2$）：取出所有剩余频次 $\ge 1$ 的不同元素，同样按从大到小（降序）排列输出。

• 此时放入的元素频次均从 $r-1$ 提升至 $r$。

• 设本轮最大元素为 $y_1$，它率先达到当前最高频次 $r$，众数立即切换为 $y_1$。

• 随后依次填入的 $y_2,y_3,\dots$ 虽然也相继达到最高频次 $r$，但均满足 $y_i<y_1$。因此在该轮结束前，众数始终被最大元素 $y_1$ 牢牢锁定。

通过这种“每一轮将所有剩余的相异元素按降序排列输出”的贪心策略，每一轮中的众数在所有可能达到的最高频次元素中均取到了理论极大值，从而保证了全局前缀众数之和最大。

---

复杂度分析

• 时间复杂度：

• 使用红黑树结构的 std::map 统计频次并维护有序性，插入与查找复杂度为 $O(n\log k)$，其中 $k\le n$ 为相异元素个数。

• 每次逆向遍历并擦除频次归零的节点，每个元素被访问并输出 $1$ 次，删除操作总计发生 $k$ 次，每次删除耗时 $O(\log k)$。

• 单组测试用例的时间复杂度为 $O(n\log n)$，在 $\sum n\le 5\times {10}^4$ 的规模下，整体运行耗时远低于 $1\text{ s}$。

• 空间复杂度：

• std::vector<int> a 存储原始输入需 $O(n)$ 空间。

• std::map<int, int> b 存储相异元素及其频次，最多占用 $O(n)$ 额外空间。

• 整体空间复杂度为 $O(n)$。

---

参考代码

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

void fc() {
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    std::map<int, int> b;  
    for (int i = 0; i < n; i++) std::cin >> a[i], b[a[i]]++;
 
    while (b.size()) {
        auto it = b.end();
        it--;  
        while (true) {
            std::cout << it->first << " ";  
            if (--it->second == 0) {
                it = b.erase(it);
            } 
            if (it == b.begin()) break;
            --it; 
        }
    }
    std::cout << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    std::cin >> t;
    while (t--) fc();
    return 0;
}

---

C. GCD Treasury

题目大意

海盗 Dimash 发现了一座宝库，内有 $n$ 堆硬币，第 $i$ 堆包含 $a_i$ 枚硬币。Dimash 初始持有一个正整数 $x$（代码中记为 $g$）。

盗取过程按如下规则循环进行：

1. 选择一个下标 $i$（$1\le i\le n$），满足当前该堆硬币数 $a_i>0$ 且 $gcd(a_i,x)\ne 1$。若不存在这样的堆，则盗取终止。

2. 令公约数 $g^{\prime }=gcd(a_i,x)$，从第 $i$ 堆盗取 $g^{\prime }$ 枚硬币（$a_i\leftarrow a_i-g^{\prime }$）。

3. 将手中的数字更新为 $g^{\prime }$（$x\leftarrow g^{\prime }$），并继续循环。

求 Dimash 最多可以盗取的硬币总数量。

数据范围：

• 测试用例组数 $t$ 满足 $1\le t\le {10}^4$。

• 堆数 $n$ 与初始数字 $x$ 满足 $1\le n,x\le 3\cdot {10}^5$。

• 硬币数 $a_i$ 满足 $1\le a_i\le 3\cdot {10}^5$。

• 所有测试用例的 $n$ 之和满足 $\sum n\le 3\cdot {10}^5$。

---

思路

1. 单堆完全盗取的不变量

设当前持有的数值为 $x$，选定满足 $gcd(a_i,x)=g^{\prime }>1$ 的第 $i$ 堆。 由于 $g^{\prime }\mid a_i$，盗取 $g^{\prime }$ 枚后该堆剩余 $a_i-g^{\prime }$ 枚硬币，仍为 $g^{\prime }$ 的整数倍。此后手牌变为 $g^{\prime }$，Dimash 可以针对这同一堆连续操作，每次公约数稳定为 $g^{\prime }$，直到将该堆全部 $a_i$ 枚硬币取空。因此：凡是参与盗取的硬币堆，其内部硬币均能被全部盗出。

2. 公约数整除链的传递性

设整个操作序列中依次生成的手牌数值为 $x_0=x,x_1,x_2,\dots ,x_k$。根据操作定义有整除链：

$$x_k\mid x_{k-1}\mid \cdots \mid x_1\mid x_0$$

因为操作终止前必须满足手牌大于 1，最终的手牌 $x_k$ 必定含有至少一个质因子 $p$。由整除的传递性可知：

$$p\mid x\text{且}\mathrm{\forall }m\in [1,k],p\mid a_{i_m}$$

这表明，所有被盗取的硬币堆与初始手牌 $x$ 之间，必定共同拥有至少一个公共质因子 $p$。

3. 质因子的包含单调性与贪心决策

若选取一个由多个质因数组合而成的因数 $s=p_1\cdot p_2\cdots p_m$（$m\ge 2$），所有满足 $s\mid a_i$ 的元素集合显然是满足单个质因子 $p_1\mid a_i$ 的元素集合的子集：

$$\{a_i\mid s\mid a_i\}\subseteq \{a_i\mid p_1\mid a_i\}$$

由于所有 $a_i>0$，更大的集合必然产生不劣的累加和：

$$\sum _{s\mid a_i}{a}_i\le \sum _{p_1\mid a_i}{a}_i$$

因此，全局最优解必然可以在 $x$ 的某一个单独质因子处取得。无需枚举合数因数组合，只需分解出 $x$ 的所有相异质因子，分别统计数组中整除该质因子的元素之和，取其最大值即为答案：

$$\text{ans}=\underset{p\mid x,p\in \mathbb{P}}{max}\sum _{p\mid a_i}{a}_i$$

当初始值 $x=1$ 时，无法满足初始非互质条件，答案为 0。

---

复杂度分析

• 时间复杂度：

• 分解质因子：试除法耗时 $O(\sqrt{x})$。

• 质因子遍历统计：在 $x\le 3\cdot {10}^5$ 范围内，相异质因子个数极少（前 7 个质数乘积 $2\times 3\times 5\times 7\times 11\times 13\times 17=510510>3\cdot {10}^5$，故相异质因子个数 $\omega (x)\le 6$）。对于每个质因子，单次线性扫描数组统计耗时 $O(n)$。

• 单组数据时间复杂度为 $O(\sqrt{x}+\omega (x)\cdot n)$。总运算量不超过 $6\times \sum n\approx 1.8\cdot {10}^6$，在 2.0 秒的时限内运行效率极高。

• 空间复杂度：

• 全局静态数组存储 $a$ 占用固定内存 $O(N)$（$N=3\cdot {10}^5$）。

• 质因子列表 res 长度不超过 6，占用常数空间。

• 额外空间复杂度为 $O(1)$（计入输入数组为 $O(n)$）。

---

参考代码

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 3e5 + 5;
int n, g;
int a[N];
 
std::vector<int> f(int x) {
    std::vector<int> res;
    for (ll i = 2; i * i <= x; i++) {
        if (x % i == 0) {
            res.push_back(i);  
            while (x % i == 0) x /= i; 
        }
    }
    if (x > 1) res.push_back(x);  
    return res;
}

void fc() {
    std::cin >> n >> g;
    for (int i = 0; i < n; i++) std::cin >> a[i];
     
    if (g == 1) {
        std::cout << 0 << "\n";
        return;
    }

    auto b = f(g);  
    ll ans = 0;
     
    for (auto x : b) {
        ll sum = 0;
        for (int i = 0; i < n; i++) {
            if (a[i] % x == 0) sum += a[i];
        }
        ans = std::max(ans, sum); 
    }

    std::cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    std::cin >> t;
    while (t--) fc();
    return 0;
}

D. Backrooms Hill

题目大意

定义一个长度为 $m$ 的数组 $b$ 为 hill（山峰数组），当且仅当存在一个分割位置 $k$（$1\le k\le m$），使得：

• 前 $k$ 个元素严格单调递增：对于所有 $1\le i<k$，均有 $b_i<b_{i+1}$；

• 后 $m-k+1$ 个元素严格单调递减：对于所有 $k\le i<m$，均有 $b_i>b_{i+1}$。

现给定一个由 $n$ 个互不相同的正整数构成的数组 $a$（$1\le a_i\le n$）。每次操作可以任选一个下标 $i$（$1\le i\le n-2$），交换 $a_i$ 与 $a_{i+2}$ 的位置。该操作可以执行任意多次。

试判断能否通过上述操作将数组 $a$ 转换为一个 hill 数组。

数据范围：

• 测试用例组数 $t$ 满足 $1\le t\le {10}^4$。

• 数组长度 $n$ 满足 $1\le n\le 2\cdot {10}^5$。

• 数组元素 $a_i$ 互不相同且满足 $1\le a_i\le n$。

• 所有测试用例的 $n$ 之和满足 $\sum n\le 2\cdot {10}^5$。

---

思路

1. 操作不变量与置换自由度分析

题目允许任意交换跨度为 $2$ 的两个元素（即 $a_i\leftrightarrow a_{i+2}$）。

• 下标奇偶性相同的两个位置可以通过相邻交换（如同冒泡排序）任意调整内部相对顺序。
• 奇数下标上的数永远无法移动到偶数下标，偶数下标上的数也永远无法移动到奇数下标。

因此，每个元素最终所在位置的下标奇偶性，必须与其初始下标的奇偶性严格一致。

2. Hill 数组的极值拓扑性质

一个严格单峰（先增后减）且元素互不相同的数组具有如下边界剥离性质：

• 设当前剩余元素构成的区间为 $[l,r]$。

• 考察这批元素中的全局最小值：

• 若该最小值出现在区间内部的某个位置 $j$（$l<j<r$）：

• 若 $j\le k$，由严格递增性必有 $b_{j-1}<b_j$，与 $b_j$ 是当前最小值矛盾；

• 若 $j\ge k$，由严格递减性必有 $b_{j+1}<b_j$，同样产生矛盾。

• 由此可知：当前未安放的最小值，必须且只能放置在当前剩余目标区间的两个端点之一（即最左端 $l$ 或最右端 $r$）。

3. 双指针贪心匹配策略

基于上述性质，可采取由小到大的逆向构造法：

1. 将数组 $a$ 中的所有二元组 $(a_i,imod2)$ 按数值升序排序。
2. 维护待填充区间的左右端点双指针 $[l,r]$，初始时 $l=0,r=n-1$。
3. 从小到大枚举每个元素，尝试将其安放在 $l$ 或 $r$：

• 若当前区间长度 $(r-l+1)$ 为偶数： 端点 $l$ 与 $r$ 的奇偶性必然互斥（一奇一偶）。这意味着当前元素的奇偶属性至多只能与其中一个端点相吻合：

• 若能匹配某端点，则必须且只能放入该端点，并将对应指针内缩（$l++$ 或 $r--$）；

• 若均无法匹配（实际在奇偶互斥时必然恰好匹配其一），则无解。

• 若当前区间长度 $(r-l+1)$ 为奇数： 端点 $l$ 与 $r$ 具有相同的奇偶性（同奇或同偶）：

• 若当前元素的奇偶性与两端点均不相同，则该元素既不能置于 $l$ 也不能置于 $r$，直接判定无法构成，输出 NO；

• 若当前元素的奇偶性与两端点相同，无论是置于左端还是右端，消耗的都是一个该奇偶性的空位，剩余未填充位置集合的奇偶配额完全对称无异。因此直接贪心放置在左端（令 $l++$）不会影响后续决策的最优性。

4. 若全部 $n$ 个元素均能成功就位，则说明存在合法构造，输出 YES。

---

复杂度分析

• 时间复杂度：

• 排序包含 $n$ 个元素的 vector 耗时 $O(n\log n)$。

• 双指针线性遍历并根据奇偶性判定匹配耗时 $O(n)$。

• 单组测试用例时间复杂度为 $O(n\log n)$，整体时间复杂度为 $O(\sum n\log n)$。在 $\sum n\le 2\cdot {10}^5$ 条件下，运行耗时约数十毫秒，远优于 2.0 秒的时限要求。

• 空间复杂度：

• 存储元素及其下标奇偶性的 std::vector<std::pair<int, int>> 需要 $O(n)$ 空间。

• 双指针及循环控制变量占用常数空间 $O(1)$。

• 整体额外空间复杂度为 $O(n)$。

---

参考代码

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5 + 5;
int n;
void fc() {
    std::cin >> n;
    std::vector<std::pair<int,int>>a(n);
    for (int i = 0; i < n; i++) {
        std::cin>>a[i].first;
        a[i].second=i&1;
    }
    std::sort(a.begin(),a.end());
    int l=0,r=n-1;
    for(int i=0;i<n;i++){
        if((l&1)==a[i].second)l++;
        else if((r&1)==a[i].second)r--;
        else {
            std::cout<<"NO\n";return;
        }
    }
    std::cout<<"YES\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    std::cin >> t;
    while (t--) fc();
    return 0;
}

E. Clean Substrings

题目大意

定义一个二进制字符串 $t$ 是 clean 的，当且仅当其所有字符均相同（即全部由 '0' 或全部由 '1' 组成）。

每次操作可以选择 $t$ 的任意一个 clean 子串并将其所有字符取反（'0' 变 '1'，'1' 变 '0'），代价为 $1$ 枚硬币。定义字符串 $t$ 的美丽度 $\text{beauty}(t)$ 为将其变为 clean 字符串所需的最小硬币数；定义字符串 $t$ 的权值 $\text{power}(t)$ 为其所有子串的美丽度之和。

给定一个长度为 $n$ 的二进制字符串 $s$ 以及 $q$ 次单点字符翻转操作。要求在初始状态及每次翻转操作后，输出当前字符串 $s$ 的权值 $\text{power}(s)$。

数据范围：

• $t$ 组测试用例，满足 $1\le t\le {10}^4$。
• $1\le n,q\le 2\cdot {10}^5$，且所有测试用例的 $\sum n,\sum q\le 2\cdot {10}^5$。
• 字符串仅包含字符 '0' 与 '1'。

---

思路

1. 单个子串的美丽度分析

设子串 $t$ 的长度为 $m$。定义相邻不同字符的“跳变次数”为：

$$c(t)=\sum _{i=1}^{m-1}[t_i\ne t_{i+1}]$$

将同色连续段缩为一个块，整个串可以看作由 $c(t)+1$ 个交替同色块连接而成。

• 翻转内部的某个同色块，可以使该块与左右两相邻块合并，从而使跳变次数减少 $2$。
• 翻转边界的同色块，可以使跳变次数减少 $1$。
• 最终使字符串变为 clean 等价于将跳变次数减少到 $0$。

因为每次操作至多减少 $2$ 次跳变，贪心地消除内部块可知最小操作代价为：

$$\text{beauty}(t)=\lceil \frac{c(t)}{2}\rceil$$

2. 上取整的奇偶拆解

由于整数上取整可表示为 $\lceil \frac{x}{2}\rceil =\frac{x+(xmod2)}{2}$，我们来考察跳变次数 $c(t)$ 的奇偶性。

从子串起点 $t_1$ 走到终点 $t_m$，每经过一次跳变，字符的状态就交替变换一次。因此，$c(t)$ 为奇数当且仅当首尾字符不同：

$$c(t)\equiv [t_1\ne t_m](\mathrm{mod}2)$$

由此可将美丽度拆解为：

$$\text{beauty}(t)=\frac{c(t)+[t_1\ne t_m]}{2}$$

3. 全局子串权值求和

对原串 $s$ 的所有子串求和，由期望与求和的线性性质：

$$\text{power}(s)=\sum _{1\le l\le r\le n}\text{beauty}(s[l\dots r])=\frac{1}{2}(\sum _{1\le l\le r\le n}c(s[l\dots r])+\sum _{1\le l\le r\le n}[s_l\ne s_r])$$

两部分可以分别独立计算：

1. 相邻跳变贡献之和： 考虑原串中的相邻位置 $i$ 和 $i+1$（$0\le i<n-1$）。若 $s_i\ne s_{i+1}$，则该跳变落在子串 $s[l\dots r]$ 中当且仅当 $l\le i$ 且 $r\ge i+1$。 合法的左端点有 $i+1$ 个，右端点有 $n-1-i$ 个。每个跳变的贡献即为 $(i+1)(n-1-i)$。 记所有跳变贡献之和为：

$$r=\sum _{i=0}^{n-2}[s_i\ne s_{i+1}]\cdot (i+1)(n-1-i)$$

2. 端点不同点对贡献之和： 考虑所有满足 $l\le r$ 且 $s_l\ne s_r$ 的点对 $(l,r)$。显然当 $l=r$ 时 $s_l=s_r$，故必然有 $l<r$。 每一个满足条件的点对 $(l,r)$ 恰好对应在原串中选出一个 '0' 和一个 '1'。 设串中 '0' 的总数量为 ${\text{cnt}}_0$，'1' 的总数量为 ${\text{cnt}}_1$，则满足条件的点对总数恰为：

$$\sum _{1\le l\le r\le n}[s_l\ne s_r]={\text{cnt}}_0\times {\text{cnt}}_1$$

结合两部分，整个字符串的权值即为：

$$\text{power}(s)=\frac{r+{\text{cnt}}_0\times {\text{cnt}}_1}{2}$$

4. 动态单点维护

每次单点翻转位置 $x$ 的字符：

• 仅会影响至多两个相邻位置的跳变状态：$(x-1,x)$ 和 $(x,x+1)$。通过异或状态更新跳变数组 $b$，并相应增减 $r$。
• 更新 ${\text{cnt}}_0$ 与 ${\text{cnt}}_1$。
• 修改和查询均可在 $O(1)$ 复杂度内完成。

---

复杂度分析

• 时间复杂度：

• 构建阶段：扫描字符串统计字符频数及初始相邻跳变，时间复杂度为 $O(n)$。

• 维护阶段：每次修改仅更新常数个相邻跳变与字符计数，单次查询时间复杂度为 $O(1)$，$q$ 次操作总耗时 $O(q)$。

• 总时间复杂度为 $O(n+q)$。

• 空间复杂度：

• 需要维护原始字符串和相邻跳变状态数组 $b$，空间复杂度为 $O(n)$。

---

参考代码

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, q;
std::string s;

struct ST {
    int m;
    ll r = 0, cnt0 = 0, cnt1 = 0;
    std::string t;
    vector<int> b;
    ST(int m, std::string& s) : m(m),t(s){
        b.resize(s.size() - 1);

        for (char c : s) {
            c == '0' ? cnt0++ : cnt1++;
        }

        for (int i = 0; i < s.size() - 1; i++) {
            b[i] = s[i] != s[i + 1];
            if (b[i]) {
                r += 1LL * (i + 1) * (m - i - 1);
            }
        }
        print();
    }
    void f(int x) {
        if (x < 0 || x >= m - 1) return;
        if (b[x]) {
            r -= 1LL * (x + 1) * (m - x - 1);
        } else {
            r += 1LL * (x + 1) * (m - x - 1);
        }
        b[x] ^= 1;
    }
    void modify(int x) {
        f(x);
        f(x - 1);

        if (t[x] == '0')
            cnt0--, cnt1++, t[x] = '1';
        else
            cnt0++, cnt1--, t[x] = '0';

        print();
    }

    void print() { std::cout << ((r + cnt1 * cnt0) >> 1) << " "; }
};
void fc() {
    std::cin >> n >> q >> s;

    ST st(n, s);
    while (q--) {
        int x;
        std::cin >> x;

        st.modify(x - 1);
    }
    std::cout << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    std::cin >> t;
    while (t--) fc();
    return 0;
}

---

F1. XOR Transformations (Easy Version)

题目大意

给定一个长度为 $n$ 的非负整数数组 $a$。定义一次“变换”如下：

1. 计算所有满足 $1\le i<j\le n$ 的数对异或值 $a_i\oplus a_j$，共有 $\frac{n(n-1)}{2}$ 个值；
2. 取其中最小的 $n$ 个数值；
3. 用这 $n$ 个数值替换原数组 $a$。

现有 $q$ 次独立询问，每次给出一个非负整数 $x$，要求计算对原数组执行 $x$ 次变换后数组的极差，即 $max(a)-min(a)$。

数据范围：

• 测试用例数：$1\le t\le 100$
• 数组大小及查询数：$5\le n\le 2000$，$1\le q\le 2000$
• 元素及查询操作数：$0\le a_i<2^{30}$，$0\le x<2^{30}$
• 保证单个测试点内 $\sum n\le 2000$，$\sum q\le 2000$

---

思路

1. 状态的快速收敛性： 考虑异或运算的高位抵消性质。两两做异或时，具有相同二进制最高有效位（MSB）的数对异或后该位会变为 $0$。变换后只保留最小的 $n$ 个数，这意味着高位被消除的较小数值优先保留下来。 随着变换次数的递增，数组中相同元素的数量会急剧上升，从而产生大量的 $0$（两个相同数异或得 $0$）。当数组中存在 $k$ 个 $0$ 时，单次变换会产生 $(\genfrac{}{}{0ex}{}{k}{2})$ 个 $0$。一旦 $(\genfrac{}{}{0ex}{}{k}{2})\ge n$（即 $k\approx \sqrt{2n}$），下一步变换的前 $n$ 小元素将全部坍缩为 $0$。 因此，整个数组的所有元素退化至全 $0$ 所需的变换次数 $\text{lim}$ 极小（通常在 $30$ 轮以内即可完全终止）。
2. 终止态与离线预处理： 当数组最大值变为 $0$（即升序排序后 $a_{n-1}=0$）时，意味着数组内所有数均为 $0$。此后无论再进行多少次变换，数组元素始终全为 $0$，极差恒满足 $max(a)-min(a)=0-0=0$。 基于此性质，可以对每一次变换进行直接模拟，并预处理记录步数 $0,1,2,\dots ,\text{lim}$ 对应的极差 $\text{ans}[\text{step}]=a_{n-1}-a_0$。
3. 回答询问： 对于每次给定的变换次数 $x$：

• 若 $x\ge \text{lim}$，则数组已处于全 $0$ 的稳态，极差直接输出 $0$；
• 若 $x<\text{lim}$，直接输出预处理好的 $\text{ans}[x]$。

---

复杂度分析

• 时间复杂度：

• 预处理模拟阶段：单次变换需计算 $\frac{n(n-1)}{2}$ 个异或值并排序，复杂度为 $\mathcal{O}(n^2\log n)$。由于数组元素迅速全变为 $0$，总变换轮数 $K$ 非常小（$K\ll n$），因此单组数据的预处理耗时为 $\mathcal{O}(K\cdot n^2\log n)$。在 $\sum n\le 2000$ 的约束下，总运算量远低于时间上限（4.0 秒）。

• 查询阶段：共 $q$ 次询问，每次查询通过数组下标访问达到 $\mathcal{O}(1)$，查询总复杂度为 $\mathcal{O}(q)$。

• 总时间复杂度：$\mathcal{O}(\sum (K\cdot n^2\log n+q))$。

• 空间复杂度：

• 向量 v 存储两两异或的数值，最大元素量为 $\frac{n(n-1)}{2}$，占用空间为 $\mathcal{O}(n^2)$。

• 答案数组及原数组大小为 $\mathcal{O}(n)$。

• 总空间复杂度：$\mathcal{O}(n^2)$。

---

参考代码

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N=2005;
int n,q,a[N],ans[N];

void f(){
    std::vector<int>v;v.reserve(n*n);
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            v.push_back(a[i]^a[j]);
        }
    }
    std::sort(v.begin(),v.end());
    for(int i=0;i<n;i++){
        a[i]=v[i];
    }
}
void fc() {
    std::cin>>n>>q;
    for(int i=0;i<n;i++)std::cin>>a[i];

    std::sort(a,a+n);

    int lim=0;
    ans[lim]=a[n-1]-a[0];

    while(a[n-1]!=0){
        lim++;
        f();
        ans[lim]=a[n-1]-a[0];
    }

    while(q--){
        int x;std::cin>>x;
        std::cout<<(x>=lim?0:ans[x])<<"\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    std::cin>>t;
    while (t--) fc();
    return 0;
}

---

F2. XOR Transformations (Hard Version)

题目大意

给定一个包含 $n$ 个非负整数的数组 $a$。定义一次数组“变换”操作如下：

1. 计算所有满足 $1\le i<j\le n$ 的数对异或值 $a_i\oplus a_j$，共形成 $\frac{n(n-1)}{2}$ 个值；

2. 取其中最小的 $n$ 个数值；

3. 用这 $n$ 个数值替换原数组 $a$。

给定 $q$ 次独立询问，每次给出一个非负整数 $x$，求对初始数组执行 $x$ 次变换后数组的极差，即 $max(a)-min(a)$。

数据范围：

• 测试用例数：$1\le t\le {10}^4$

• 数组大小与询问数：$5\le n\le {10}^5$，$1\le q\le {10}^5$

• 累加和限制：$\sum n\le {10}^5$，$\sum q\le {10}^5$

• 数值与变换次数：$0\le a_i<2^{30}$，$0\le x<2^{30}$

• 资源限制：时间限制 $4.0\text{ s}$，空间限制 $512\text{ MB}$

---

思路

1. 稳态收敛性与极差截断

异或操作在按位运算上具有消除公共高位（最高有效位 MSB）的特性。每次变换只保留最小的 $n$ 个数值，这使得数组中的数值位宽迅速收窄，并在较短轮数内产生大量重复值。

• 若数组中存在 $k$ 个相同的数，它们两两异或将贡献 $(\genfrac{}{}{0ex}{}{k}{2})$ 个 $0$。
• 当相同数的数量增长至 $(\genfrac{}{}{0ex}{}{k}{2})\ge n$（即 $k\approx \sqrt{2n}$）时，下一次变换保留的前 $n$ 个值将全部为 $0$。
• 数组元素全部变为 $0$ 所需的变换轮数 $\text{lim}$ 极小（通常在 $30$ 轮以内即可达到）。一旦出现 $a_{n-1}=0$，数组达到完全稳态，后续任何轮次的极差恒为 $0$。因此只需模拟迭代直至最大值变为 $0$，即可离线预处理出所有轮次的答案。

2. 无序对到有序对的等价映射

在 $n\le {10}^5$ 的规模下，无法直接生成全部 $\mathcal{O}(n^2)$ 个无序对。 考虑全部非自反的有序对 $(i,j)$（$i\ne j$）： 每个无序对 $\{i,j\}$ 的异或值恰好在有序对集合中对称出现两次（即 $(i,j)$ 与 $(j,i)$）。 因此，前 $n$ 个最小的无序对异或值等价于前 $2n$ 个最小的非自反有序对异或值按顺序每隔一项采样的结果。

3. 01-Trie 结合优先队列的多路归并

将求解前 $2n$ 小非自反异或值的过程转化为 $n$ 个有序序列的多路归并问题：

1. 01-Trie 检索 $k$ 小异或： 将当前数组的 $n$ 个数插入一棵高度为 $30$ 位的 01-Trie，并在节点上维护子树计数。利用二叉前缀树的结构，可以在 $\mathcal{O}(\log C)$（$C=2^{30}$）的时间内查询与任意给定数值 $a_i$ 异或所得的第 $k$ 小值（$k$ 从 $1$ 开始计数）：

• 第 $1$ 小值恒为其自身异或，结果为 $a_i\oplus a_i=0$；
• 第 $2$ 小值即为以 $a_i$ 为基准的最小非自反异或值。

2. 小根堆多路归并： 维护一个小根优先队列 std::priority_queue，初始将每个位置的第 $2$ 小异或值 $(get(a[i],2),i)$ 入堆。 每次取出堆顶的全局最小值放入结果序列 $v$，并将该元素的查询位序后移一位（$cnt[i]\leftarrow cnt[i]+1$），在 Trie 中查询下一个第 $k$ 小异或值重新插入堆中。 连续提取 $2n$ 个元素后，偶数索引位置 $v[0],v[2],\dots ,v[2n-2]$ 即为下一轮数组所需的精确前 $n$ 小元素。

---

复杂度分析

• 时间复杂度：

• 单轮变换模拟：

• 将 $n$ 个元素插入 01-Trie 耗时 $\mathcal{O}(n\log C)$；

• 堆中维护 $n$ 个元素的多路归并，总共提取 $2n$ 次，每次堆操作耗时 $\mathcal{O}(\log n)$，并在 Trie 中执行一次查询耗时 $\mathcal{O}(\log C)$，归并总耗时 $\mathcal{O}(n(\log n+\log C))$；

• 单轮变换复杂度为 $\mathcal{O}(n(\log n+\log C))$。

• 全局复杂度：设收敛至全 $0$ 状态的轮数为 $K$（在给定位宽下 $K$ 为很小的常数，$K\ll \log C$），预处理模拟阶段耗时为 $\mathcal{O}(K\cdot n(\log n+\log C))$；回答 $q$ 次询问为 $\mathcal{O}(1)$ 查表。总时间复杂度为 $\mathcal{O}(\sum (K\cdot n(\log n+\log C)+q))$，在 $4.0\text{ s}$ 限制内具有充裕的运行余量。

• 空间复杂度：

• 01-Trie 存储 $n$ 个数值时最多开辟 $n\log C$ 个节点，节点状态数组空间为 $\mathcal{O}(n\log C)$；

• 优先队列及辅助数组大小为 $\mathcal{O}(n)$；

• 总空间复杂度：$\mathcal{O}(n\log C)$，在 $n={10}^5$ 时空间占用约几十兆字节，满足 $512\text{ MB}$ 空间限制。

---

参考代码

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = std::pair<int, int>;

const int N = 1e5 + 5;
int n, q, tim, a[N], ans[N], cnt[N];
int t[N * 30], son[N * 30][2];

void update(int x, int v = 1) {
    t[v]++;
    for (int i = 29; i >= 0; i--) {
        int k = (x >> i) & 1;
        if (!son[v][k]) son[v][k] = ++tim;
        v = son[v][k];
        t[v]++;
    }
}
int get(int x, int k, int v = 1) {
    int res = 0;
    for (int i = 29; i >= 0; i--) {
        int b = (x >> i) & 1;
        if (t[son[v][b]] >= k) {
            v = son[v][b];
            res += b * (1 << i);
        } else {
            k -= t[son[v][b]];
            v = son[v][b ^ 1];
            res += (b ^ 1) * (1 << i);
        }
    }
    return res ^ x;
}
void f() {
    for (int i = 1; i <= tim; i++) son[i][0] = son[i][1] = t[i] = 0;

    std::priority_queue<P, std::vector<P>, std::greater<P>> q;
    tim = 1;

    for (int i = 0; i < n; i++) update(a[i]), cnt[i] = 2;
    for (int i = 0; i < n; i++) q.push({get(a[i], 2), i});

    std::vector<int> v;
    v.reserve(n << 1);

    for (int _ = 1; _ <= (n << 1); _++) {
        auto [val, i] = q.top();
        q.pop();

        v.push_back(val);

        cnt[i]++;
        if (cnt[i] <= n) q.push({get(a[i], cnt[i]), i});
    }

    for (int i = 0; i < n; i++) a[i] = v[i << 1];
}
void fc() {
    std::cin >> n >> q;
    for (int i = 0; i < n; i++) std::cin >> a[i];

    std::sort(a, a + n);

    int lim = 0;
    ans[lim] = a[n - 1] - a[0];

    while (a[n - 1] != 0) {
        lim++;
        f();
        ans[lim] = a[n - 1] - a[0];
    }

    while (q--) {
        int x;
        std::cin >> x;
        std::cout << (x >= lim ? 0 : ans[x]) << "\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    std::cin >> t;
    while (t--) fc();
    return 0;
}

---