## 总体情况
第一题 $100$ 分，第二题 $100$ 分，第三题 $10$ 分，表现良好。
## 题目解析
### 宝石管理系统
#### 简要题意
初始有 $m$ 个数，$q$ 次操作，每次操作有两种：
- 输出第 $n$ 大的数；
- 添加指定大小的数。
#### 解法
由于需要动态地插入某个数、询问第 $k$ 大的值，因此可以使用平衡树来解决。使用 fhq Treap 来实现平衡树，需要注意的是 split 和 merge 函数不能有任何的偏差（不论是背诵下来还是画草稿纸想）。
#### 注意事项
虽然 $m\le 1\times 10^5$，但是实际上平衡树当中最多会有 $n+q$ 个元素（还有 $q$ 次操作），因此数组不能只开 $1\times 10^5$，起码是 $1.3\times 10^5$。
#### 赛时代码
```cpp
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
const int kMaxN = 1e6 + 5;
struct {
int ch[2], siz, val, pri;
} t[kMaxN];
int n, q, root, cnt;
int newNode(int val) {
t[++cnt] = {{0, 0}, 1, val, rand()};
return cnt;
}
void update(int x) {
t[x].siz = t[t[x].ch[0]].siz + t[t[x].ch[1]].siz + 1;
}
void split(int x, int &a, int &b, int val) {
if (!x) {
a = b = 0;
return;
}
if (t[x].val >= val) {
a = x;
split(t[x].ch[1], t[x].ch[1], b, val);
} else {
b = x;
split(t[x].ch[0], a, t[x].ch[0], val);
}
update(x);
}
int merge(int a, int b) {
if (!a || !b) {
return a ^ b;
}
if (t[a].pri < t[b].pri) {
t[a].ch[1] = merge(t[a].ch[1], b);
update(a);
return a;
}
t[b].ch[0] = merge(a, t[b].ch[0]);
update(b);
return b;
}
void insert(int x) {
int a, b, c = newNode(x);
split(root, a, b, x);
a = merge(a, c);
root = merge(a, b);
}
int query(int k) {
int x = root;
while (t[t[x].ch[0]].siz + 1 != k) {
if (t[t[x].ch[0]].siz + 1 < k) {
k -= t[t[x].ch[0]].siz + 1;
x = t[x].ch[1];
} else {
x = t[x].ch[0];
}
}
return t[x].val;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
srand(time(nullptr));
cin >> n >> q;
for (int i = 1, x; i <= n; i++) {
cin >> x;
insert(x);
}
for (int o, x; q; q--) {
cin >> o >> x;
if (o == 1) {
cout << query(x) << '\n';
} else {
insert(x);
}
}
return 0;
}
```
### Rmq Problem / mex
#### 简要题意
有一个长度为 $n$ 的数列，给出 $m$ 个询问 $[l,r]$，询问 $[l,r]$ 区间中最小的没有出现过的自然数。
#### 解法
由于数列是静态的没有任何修改，而区间两边在添删元素的时候都可以以较快的时间复杂度完成，因此可以使用莫队算法来解决此问题。
对于标准的动态 mex 模拟，使用数组记录每个数是否出现过，可以构造数据使算法超时（如添加数 ${} 0\sim V$，然后删除 $0$，再添加 $0$，反复操作会使答案指针移动得特别快）。
另一种方式是使用 set 动态维护所有没有出现过的元素，那么 begin() 迭代器上的数就是答案了。但是单次移动时间复杂度 $\mathcal O(\log_2 n)$，总时间复杂度 $\mathcal O(n\sqrt n\log_2 n)$。
此时可以使用 STL 中的神器 bitset 来存储所有没有出现过的元素（当下标存）。有个成员函数叫 \_Find\_first() 可以快速地找到第一个 1 位的下标，该函数时间复杂度 $\mathcal O\left(\cfrac{n}{w}\right)$，$w$ 在评测机上是 $64$。
但是答案的期望值大概是 $\sqrt n$ 级别的，因此实际上单次修改只需要大概 $\cfrac{\sqrt{2\times 10^5}}{64}$，也就是大约七次操作，比 $\log_2 n$ 要优得多，因此可以通过该题目。
#### 赛时代码
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int a[N], n, m, k, ans, sum[N], vis[N];
bitset<N> b;
struct S {
int l, r, id;
} s[N];
bool cmp(S X, S Y) {
if ((X.l - 1) / k == (Y.l - 1) / k) {
return X.r < Y.r;
}
return X.l < Y.l;
}
void D(int x) {
vis[x]++;
if (vis[x] == 1) {
b[x] = 0;
}
}
void E(int x) {
vis[x]--;
if (vis[x] == 0) {
b[x] = 1;
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 0; i <= n; i++) {
b[i] = 1;
}
k = sqrt(n);
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 1; i <= m; i++) {
cin >> s[i].l >> s[i].r;
s[i].id = i;
}
sort(s + 1, s + 1 + m, cmp);
for (int i = 1, l = 1, r = 0; i <= m; i++) {
for (; r < s[i].r; D(a[++r])) {
}
for (; l > s[i].l; D(a[--l])) {
}
for (; r > s[i].r; E(a[r--])) {
}
for (; l < s[i].l; E(a[l++])) {
}
sum[s[i].id] = b._Find_first();
}
for (int i = 1; i <= m; i++) {
cout << sum[i] << "\n";
}
return 0;
}
```
### 美好的每一天
#### 简要题意
给定长度为 $n$ 的字符串，$m$ 个询问 $[l,r]$，问你 $[l,r]$ 当中有多少个子字符串满足重新排列之后可以成为一个回文字符串。
#### 解法
首先要弄清楚什么样的字符串在经过重新排列之后可以成为回文字符串。经过简单的思考之后，可以得到一个奇数次出现的字符最多为一中的字符出可以满足条件，而偶数次出现的不用考虑。
偶数次出现不用考虑？由此可以想到异或运算具有这个性质（一个数异或偶数次会变成 $0$）。我们把二十六个字符压缩成二进制，对应位上的 $0$ 表示出现偶数次，$1$ 表示出现奇数次。
由于我们需要访问子串，而异或运算有差分运算——它自己，因此我们不难想到莫队做法。做一个二进制异或前缀和为 $p$。
假设一个区间 $[l,r]$ 满足条件，那么 $p_r\operatorname{xor}p_{l-1}$ 最多只能有一个二进制位。移项得到 $p_r\operatorname{xor}任意一个二进制位上只有一个一的数=p_{l-1}$。而 $p_r$ 就是新加入的数， $p_{l-1}$ 是之前加入的数，我们通过 $f$ 记录每个 $p_{l-1}$ 之前加入过的数，然后枚举哪一位为一就行了。
#### 赛后代码
LRH 给我改的
```cpp
#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;
using LL = long long;
const LL kMaxN = 6e4 + 5, N = 6.72e7 + 5;
struct Q {
LL l, r, id;
} q[kMaxN];
LL p[kMaxN], ans[kMaxN];
short f[N];
LL n, m, len, res;
char a[kMaxN];
void add(LL x) {
LL t = p[x];
res += f[t];
for (LL i = 0; i < 26; i++) {
res += f[t ^ (1 << i)];
}
f[t]++;
}
void del(LL x) {
LL t = p[x];
f[t]--;
res -= f[t];
for (LL i = 0; i < 26; i++) {
res -= f[t ^ (1 << i)];
}
}
bool cmp(Q X, Q Y) {
if (X.l / len == Y.l / len) {
return X.r < Y.r;
}
return X.l < Y.l;
}
int main() {
cin >> n >> m >> (a + 1);
len = sqrt(n);
for (LL i = 1; i <= n; i++) {
p[i] = p[i - 1] ^ (1 << (a[i] - 'a'));
}
for (LL i = 1; i <= m; i++) {
cin >> q[i].l >> q[i].r;
q[i].id = i;
}
sort(q + 1, q + 1 + m, cmp);
for (LL i = 1, l = 0, r = -1; i <= m; i++) {
for (; r < q[i].r; r++, add(r)) {
}
for (; l > q[i].l; l--, add(l)) {
}
for (; r > q[i].r; del(r), r--) {
}
for (; l < q[i].l; del(l), l++) {
}
ans[q[i].id] = res;
// 补加一大坨玩意
ans[q[i].id] += f[p[q[i].l - 1]];
for (int j = 0; j < 26; j++) {
ans[q[i].id] += f[p[q[i].l - 1] ^ (1 << j)];
}
}
for (LL i = 1; i <= m; i++) {
cout << ans[i] << '\n';
}
return 0;
}
```
自己改的
```cpp
#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;
using LL = long long;
const LL kMaxN = 6e4 + 5, N = 6.72e7 + 5;
struct Q {
LL l, r, id;
} q[kMaxN];
LL p[kMaxN], ans[kMaxN];
short f[N];
LL n, m, len, res;
char a[kMaxN];
void add(LL x) {
LL t = p[x];
res += f[t];
f[t]++;
for (LL i = 0; i < 26; i++) {
res += f[t ^ (1 << i)];
}
}
void del(LL x) {
LL t = p[x];
f[t]--;
res -= f[t];
for (LL i = 0; i < 26; i++) {
res -= f[t ^ (1 << i)];
}
}
bool cmp(Q X, Q Y) {
if (X.l / len == Y.l / len) {
return X.r < Y.r;
}
return X.l < Y.l;
}
int main() {
cin >> n >> m >> (a + 1);
len = sqrt(n);
for (LL i = 1; i <= n; i++) {
p[i] = p[i - 1] ^ (1 << (a[i] - 'a'));
}
for (LL i = 1; i <= m; i++) {
cin >> q[i].l >> q[i].r;
q[i].id = i;
}
sort(q + 1, q + 1 + m, cmp);
for (LL i = 1, l = 1, r = 0; i <= m; i++) {
for (; r < q[i].r; r++, add(r)) {
}
for (; l > q[i].l - 1; l--, add(l)) {
}
for (; r > q[i].r; del(r), r--) {
}
for (; l < q[i].l - 1; del(l), l++) {
}
ans[q[i].id] = res;
}
for (LL i = 1; i <= m; i++) {
cout << ans[i] << '\n';
}
return 0;
}
```
**区别**：我改的代码实际上询问的区间是 $[l-1,r]$，因为差分运算需要用到 $p_{l-1}$，而前面的代码补加了一大坨玩意用来把 $p_{l-1}$ 缺失的答案加上。
## 问题分析
- 第一题：在写 spit 函数和 merge 函数的时候仍然不熟练，merge 还写错了调了一个多小时；
- 第二题：不知道寻找第一个一位的函数是什么；
- 第三题：没有搞清楚询问是 $[l-1,r]$，并且 add 函数顺序写错。
## 赛事解决方案
- 第一题：穷举 merge 函数的所有写法，找出了正确写法；
- 第二题：翻标准库源代码翻出了；
- 第三题：穷举所有可能，但是失败。
## 赛后解决方案
- 第一题：多练习平衡树的题目，见到题目重敲一遍模板而不是套用模板；
- 第二题：记住该函数；
- 第三题：多练习这种询问连续子数组的莫队题目。