小 S 排座位
一对同桌的成绩之差的绝对值必须大于等于给定的常数 $K$，请你求出他最多能排出几对同桌。
答案的配对方式肯定是一段前缀和一段后缀按顺序进行匹配。
然后没有想到，就用了二分答案，
非常精简的做法：
cin >> n >> k, mid = n >> 1;
for (int i = 1; i <= mid; i++) {
cin >> a[i];
}
while (l <= mid && mid + 1 <= n--) {
int x; cin >> x;
if (x >= k + a[l]) l++;
}
cout << l - 1 << endl;
就，很，
小 K 的外挂
棋盘是一行共 $n$ 个格子，编号依次为 $1\sim n$。小 K 有外挂，所以他会通过外挂来前进，他共有 $m$ 个外挂，第 $i$ 个外挂能让他从第 $l_i$ 格瞬移到第 $r_i$ 格，并花费 $1$ 的时间，并且他不需要外挂就能往回走（即从第 $i$ 格走到第 $i−1$ 格，且往回走不需要时间）。
但是小 K 的 rp 不太好，现在发生了 $q$ 次事件，每次事件中，小 K 的某一个挂会坏（这次事件结束后又会恢复），而你需要帮他求出此时他从 $s$ 走到 $t$ 要花费的最小时间。
令 $f_i$ 表示现在在第 $i$ 格，跳到“往左走若干格后能跳到的最右侧的点”经过的挂的编号。
$g_i$ 表示现在在第 $i$ 格，跳到“往左走若干格后能跳到的次右侧的点（不严格）”经过的挂的编号。
每次查询时 ban 了一个挂，所以每次跳的边要么是 $f$ 要么是 $g$。只要先倍增跳 $f$，当要跳的 $f$ 边被 ban 了时就倍增跳 $g$，直到 $f$ 不再被 ban 然后就接着倍增跳 $f$ 即可。
struct jump {
int to, id;
jump(int to = 0, int id = 0) : to(to), id(id) {}
};
struct node {
jump mx1, mx2;
void upd(jump b) {
if (b.to > mx1.to) {
mx2 = mx1, mx1 = b;
}
else if (b.id != mx1.id and b.to > mx2.to) {
mx2 = b;
}
}
};
int n, m, q, l[maxn], r[maxn], f[maxn][maxl+1][2];
node a[maxn];
int main() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= m; i++) {
scanf("%d %d", &l[i], &r[i]);
a[l[i]].upd({r[i], i});
}
for (int i = 1; i <= n; i++) {
a[i].upd(a[i-1].mx1);
a[i].upd(a[i-1].mx2);
f[i][0][0] = a[i].mx1.to;
f[i][0][1] = a[i].mx2.to;
}
for (int j = 1; j <= maxl; j++) {
for (int i = 1; i <= n; i++) {
int t = a[f[i][j-1][1]].mx1.id==a[i].mx1.id;
f[i][j][0] = f[f[i][j-1][0]][j-1][0];
f[i][j][1] = f[f[i][j-1][1]][j-1][t];
}
}
scanf("%d", &q);
for (int i = 1; i <= q; i++) {
int id, s, t;
scanf("%d %d %d", &id, &s, &t);
int ans = 0;
if (t < l[id]) {
id = 0;
}
if (s < l[id]) {
for (int i = maxl; i >= 0; i--) {
if (f[s][i][0] < l[id]) {
ans += (1<<i), s = f[s][i][0];
}
}
ans++, s = f[s][0][0];
}
if (s >= t) {
printf("%d\n", ans);
continue;
}
for (int i = maxl; i >= 0; i--) {
if (f[s][i][ a[s].mx1.id==id ] < t) {
ans += (1<<i), s = f[s][i][ a[s].mx1.id==id ];
}
}
ans++, s = f[s][0][a[s].mx1.id==id];
if (s < t) {
puts("-1");
} else {
printf("%d\n", ans);
}
}
}
奇数计数
在集合中找出 $k$ 个出现了奇数次的正整数。保证集合中有且仅有 $k$ 种出现了奇数次的正整数。
$k\in{1,2}$，内存限制：$\texttt{4 MiB}$
对于 $k=1$ 的情况直接异或；
考虑 $k=2$ 的情况：
然后发现两个数异或起来很难拆开，考虑二进制，对每一位开个桶，在桶里面再次异或，就会神奇的发现对于出现偶数次的数的贡献神奇的抵消了，而合法解也能在 $\log n$ 的空间内记录。