简介
总结一些非常经典的套路
一些注意事项
用 $priority\underline{}queue$ 实现的可删除堆比 $multiset$ 要快接近一倍
$O(1)$ 计算二进制位的几个内置函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14int __builtin_ffs (unsigned int x)
返回x的最后一位1的是从后向前第几位
int __builtin_clz (unsigned int x)
返回前导 0 的个数
int __builtin_ctz (unsigned int x)
返回后面的 0 的个数，和 __builtin_clz 相对。
int __builtin_popcount (unsigned int x)
返回二进制表示中 1 的个数。
int __builtin_parity (unsigned int x)
返回 x 的奇偶校验位，也就是 x 的 1 的个数模 2 的结果
注意上面的函数都有对应 long long 版本
例如:
long long __builtin_popcountll
一些小技巧
对 $2^{64}$ 左右的数取模的乘法，俗称龟速乘，不要出现负数
1
2
3
4
5
6inline ll mul(ll x, ll y, ll p) { return (x * y - (ll) ((long double) x / p * y) * p + p) % p; }
inline ull mul(ull x, ull y, ull p) {
ll s = x * y - p * (ull)(1.L / p * x * y);
return s + p * (s < 0) - p * (s >= (ll)p);
}
// 两种做法应该都是没错的, 但第二种更快, 常数大概是 1/2 左右以时间为种子生成随机数
1
2
3
4
5mt19937_64 gen(chrono::system_clock::now().time_since_epoch().count());
uniform_int_distribution<T> (L,R)
uniform_real_distribution<T> (L,R)
template<typename T> T rd(T l, T r) { return std::uniform_int_distribution<T>(l, r)(gen); }取模优化
1
2
3
4inline int add(int x, int y) { return (x += y) >= p ? x - p : x; }
inline int mul(int x, int y) { return 1ll * x * y % p; }
inline int add(initializer_list<int> lst) { int s = 0; for (auto t : lst) s = add(s, t); return s; }
inline int mul(initializer_list<int> lst) { int s = 1; for (auto t : lst) s = mul(s, t); return s; }递归计算 $\sum_{i=0}^na^i$，时间复杂度 $O(\log n)$
1
2
3
4
5
6
7
8int calc(int x, int n) {
if (n == 0) return 1;
if (n & 1) return mul(calc(x, n / 2), 1 + pow_mod(x, n / 2 + 1));
else {
int res = pow_mod(x, n / 2);
return add(mul(calc(x, n / 2 - 1), 1 + mul(res, x)), res);
}
}光速幂，已知 $x$ 和模数 $p$，求 $x^n\bmod p$，可以 $O(\sqrt n)$ 预处理，$O(1)$ 回答
1
2
3
4
5
6
7
8
9
10
11namespace GSM {
const int N = 100000;
int a[N], b[N], x, n;
void init(int _x, int _n) {
n = ceil(sqrt(_n)); x = _x;
for (int i = 0, t = 1; i <= n; ++i) a[i] = t, t = mul(t, x);
for (int i = 0, t = 1; i <= n; ++i) b[i] = t, t = mul(t, a[n]);
}
inline int gsm(int m) { return mul(b[m / n], a[m % n]); }
}dfs $O(B_n)$ 枚举集合划分
1
2
3
4
5
6int id[maxn];
void dfs(int q, int k) {
if (q == n) return calc();
id[q] = k + 1, dfs(q + 1, k + 1);
for (int i = 1; i <= k; ++i) id[q] = i, dfs(q + 1, k);
}$\lfloor \frac{n}{i}\rfloor$ 的 $hash$ 方法，需要 $2\sqrt n$ 的空间
1
2
3
4
5
6struct Div_hash {
int n, sn;
void init(int _n) { n = _n; sn = sqrt(n); }
int get(int x) { return x <= sn ? x : sn * 2 - n / x + 1; }
} _;
位运算
一定要每一位单独考虑
简要题意：给定一个有 $n$ 个点的完全图，无向边 $
$n\le 10^5,m\le 5\times 10^5$
简要题解：我们对于特殊的边按位考虑，也就是把边拆开，对于点 $u$，向 $u~xor~2^i$ 连边，边权为 $C\cdot2^i$
简要题意：给定两个长度为 $n$ 的序列 $a_i$ 和 $b_i$，求 $\forall i\in[1,n],j\in[1,n],a_i+b_j$ 的异或和
$n\le 2\times 10^5$
简要题解：我们先将 $x$ 和 $y$ 对 $2^{k+1}-1$ 取模
那么 $x+y$ 的第 $k$ 位是 $1$ 的条件为 $2^k\le a_i+b_j<2^{k+1},2^{k}+2^{k+1}\le a_i+b_j$
简要题意：给定一个长度为 $n$ 的序列 $a_i$，将其划分成 $m$ 段连续区间，每段区间的费用为这段区间的异或和，求所有段的费用的或的最小值
$n\le 5\times 10^5$
简要题解：我们考虑分成 $m$ 段相当于除了 $n$ 以外，再选 $m-1$ 个右端点
然后我们考虑按位贪心，注意到如果某一位出现了奇数次那么它一定要算到答案里
否则我们维护合法的右端点，注意到对于第 $k$ 位，所有前缀异或和为 $0$ 的点都可以作为一个右端点，而这个时候注意到点 $n$ 的前缀异或和一定是 $0$，所以我们只需要判断右端点的数量是否大于等于 $m$ 即可，然后每次做完将前缀异或和为 $1$ 的点标记为不能选为右端点
简要题意：给定 $n$ 个数，求有多少对数，满足异或有奇数个 $1$
$n\le 10^7$
简要题解：异或不会改变两个数二进制下 $1$ 的个数的奇偶性
Luogu P2114 [NOI2014]起床困难综合症 从高位到低位贪心
简要题意：给定一个边权均为 $1$ 的有向图，如果 $a_i~and~a_j=a_j$，则有一条 $i$ 连向 $j$ 的边，额外再给 $m$ 条有向边，求 $1$ 到其它所有点的最短路
$n\le 2\times 10^5,m\le 3\times 10^5,1\le a_i < 2^{20}$
简要题解：一个显然的思路是建 $2^{20}$ 个点，然后每个点向自己的子集连边，复杂度 $O(3^{20})$ 爆炸
考虑优化边的数量，每个点只向自己去掉一个二进制一个 $1$ 的点连边，这样复杂度 $O(20\cdot 2^{20})$，$01~bfs$ 即可
简要题意：给定一个长度为 $n$ 的序列 $a_i$，求所有子区间的和的异或和
$n\le 10^5,\sum a \le 10^6$
简要题解：将区间和变成前缀和相减，然后按位考虑
假设现在在考虑第 $k$ 位，我们把包括第 $k$ 位在内的高位都扔掉
然后我们考虑 $x - y$
如果 $x$ 的第 $k$ 位是 $1$，那么 $y$ 的 $k$ 位是 $1$ 且 $x<y$ 或 $y$ 的第 $k$ 位是 $0$ 且 $x\ge y$ 才能保证 $x-y$ 的第 $k$ 位是 $1$
$x$ 的第 $k$ 位是 $0$ 的情况正好相反
这个大小关系可以用树状数组维护，时间复杂度 $O(n\log^2 \sum a_i)$
Luogu P3760 [TJOI2017]异或和 相减和相加的情况类似
简要题意：给定一个长度为 $n$ 的非降序列 $a_i$，每次操作可以选择两个相邻的数 $a_i$ 和 $a_{i+1}$ 然后将这两个数移除，放回 $a_i\oplus a_{i+1}$，求最少多少次操作可以使其不在是非降序列，注意 $n=1$ 时仍然认为是非降
$n\le 2\times 10^5,a_i\le 10^9$
简要题解：注意到如果有连续三个数的最高位相同，则我们异或后面两个就能使得序列不合法
由于原题保证数列递增，所以相邻数的最高位至少相等
那么如果 $n>60$，答案一定为 $1$ 次，否则我们直接暴力即可
简要题意：给定一个长度为 $n$ 的序列 $a_i$，求有多少子区间是合法的，定义一个子区间 $[l,r]$ 合法，当且仅当 $a_l\oplus a_r=\sum_{i=l}^ra_i$，其中 $\oplus$ 表示异或
$n\le 2\times 10^5,a_i <2^{30}$
简要题解：注意到答案可能很少
我们考虑一种计数方式将答案分成两类，第一种是 $a[l]$ 和 $a[r]$ 的最高位不相等，第二种是 $a[l]$ 和 $a[r]$ 的最高位相等
首先考虑第一种，我们枚举 $l$，然后向右枚举 $r$，直到 $\sum_{i=l+1}^{r-1}a[i]\ge 2^{k+1}$，其中 $k$ 为 $a[l]$ 的二进制最高位
能够证明这样的时间复杂度为 $O(n\log a_i)$，我们倒着再次枚举一遍，注意到这样的话第一类答案只会算一次，第二类答案则会算两次，所以我们再多判一下最高位即可
时间复杂度证明：对于每个 $k$，最多枚举 $O(n)$，我们可以将每个含有 $2^k$ 的数当成一个隔板
简要题意：给定一个长度为 $n$ 的序列 $a_i$，求有多少子区间满足区间或等于区间最大值
$n\le 2\times 10^5,a_i\le 10^9$
简要题解：首先我们知道区间或是大于等于区间最大值的
然后我们考虑枚举作为区间最大值的点，那么我们用单调栈可以求出一个数左边和右边第一个大于它的数
然后我注意到当且仅当区间中存在一个值，它有一个 $1$ 是区间最大值所没有的
所以我们求一下每个数左边和右边第一个这样的值，然后就可以愉快的求答案了，时间复杂度 $O(n\log c)$
简要题意：给定 $n$ 个点，编号依次为 $[0,n-1]$，对于任意两个点 $u,v$，边 $(u,v)$ 的权值为 $u\oplus v$，其中 $\oplus$ 为异或，求最小生成树
$n\le 10^{12}$
简要题意：一个结论，答案为 $\sum_{i=1}^{n-1} i ~\&~ (-i)$，换句话讲点 $i$ 连向点 $i~xor~ (i ~\&~ (-i))$
我们考虑 $Boruvka$，首先第一次连边一定是 $0$ 到 $1$，$2$ 到 $3$，且边权为 $1$
下一次连边的边权为 $2$，在下一次为 $4$，稍微画画大概就能找到规律，正规证明
CF 981D Bookshelves 从高位到低位贪心即可，对于之前的局面只需要存储值即可
CF 986C AND Graph 当且仅当两点的权值的与为 $0$，两点之间连边，求连通块个数
2021牛客多校3 I Kuriyama Mirai and Exclusive Or 连续数字的 $2^i$ 这个二进制位是按照 $2^{i+1}$ 为循环节，且这种情况下的每个二进制位的差分标记是每隔 $2^i$ 打一个
简要题意：给定 $n$ 个数 $a_i$ 和 $m$ 次询问，每次询问给定四个参数 $b,x,l,r$，表示从 $a[l]$ 到 $a[r]$ 选择最大的 $b\oplus (a_i+x)$，其中 $\oplus$ 表示异或
$n,m\le 2\times 10^5,0\le a,b,x\le 10^5$
简要题解：我们考虑从高位到低位贪心，我们不妨假设现在已经选出的数的大小为 $ans$，那么现在要选第 $i$ 位，根据 $b$ 是否有 $i$ 这个二进制位，$a+x$ 的区间是 $[ans,ans+2^i-1]$ 或 $[ans+2^i,ans+2^{i+1}-1]$，区间查询是否有一个数的大小属于某个区间可以用主席树维护，时间复杂度 $O(n\log ^2n)$
简要题意：给定 $n$ 个物品和 $m$ 个属性以及常数 $w$，第 $i$ 个物品有一个价值 $c_i$ 以及其所拥有的属性 $S_i$，现在要依次选择若干个物品，满足相邻两个物品 $i$ 和 $j$ 满足 $i<j\wedge w+c_i\ge c_j\wedge S_i\subseteq S_j$，求最多选择多少个物品
$n\le 10^5,m\le 18$
简要题解：首先考虑 $cdq$ 分治解决第一个和第二个限制，对于第三个限制，我们考虑每次 $cdq$ 分治的时候将左部的每个点都贡献到自己的超集，这样可以做到 $O(2^m)$ 预处理，$O(1)$ 查询，或者我们考虑用右部的每个点求子集查询，这样是 $O(1)$ 预处理，$O(2^m)$ 查询，我们可以平衡一下，前 $\frac n 2$ 位贡献到超集，后 $\frac n 2 $ 子集查询，这样做的时间复杂度为 $O(2^{\frac n 2}n\log n+n\log^2 n)$
二进制平衡
简要题意：给定 $n$ 个点完全图，第 $i$ 个点的权值是 $a_i$，对于连接 $(u,v)$ 边，它的权值是 $a[u]~xor~a[v]$ 求最小生成树
$n\le 2\times 10^5$
简要题解：我们考虑 $kruskal$ 按照边的权值加边
我们考虑利用 $01Trie$ 的分治过程，对于分治的左右部分，因为每个部分内部的边的权值一定小于跨过两边的权值，所以内部肯定已经练好，为了将两边连接，我们只需要找一条最小的边即可，这个可以用 $01Trie$ 来做
时间复杂度 $O(n\log^2 n)$
简要题意：给定一个棵有 $n$ 个点的无根树，现在有 $m$ 次操作，操作有两种，给定 $x,y$ 求 $x$ 到 $y$ 的简单路径上所有点组成的可重集合的子异和；给定 $x,y,z$ 将 $x$ 到 $y$ 上每个点异或上 $z$，其中集合 $S$ 子异和的定义为子集 $S$ 的所有子集的异或和的和
$n,m\le 2\times 10^5$
简要题解：我们考虑集合 $S=\lbrace a_1,a_2\cdots,a_n\rbrace$ 的子异和，我们按位考虑对于第 $i$ 个二进制位，我们不妨假设有 $x$ 个 $1$ 和 $y$ 个 $0$，我们有 $x+y=n$，容易得到异或和为 $1$ 的子集个数为 $2^y\sum_{i=0}^x\binom{x}{i}[i\equiv 1(\bmod 2)]=2^{x+y-1}=2^{n-1}$，另外需要注意如果 $x$ 为 $0$，则答案为 $0$，这样容易得到答案就是 $2^{n-1}$ 乘上 $S$ 的所有数的或
我们首先树剖，那么现在只需要支持求区间或和区间异或，我们用线段树维护区间或、区间与和区间异或标记，能推出如下的转移，时间复杂度 $O(n\log^2 n)$
1
2
3
4
5
6inline void Update(int i, int v) {
int a = T[i].orsum, b = T[i].andsum;
T[i].orsum = a & ~v | ~b & v;
T[i].andsum = b & ~v | ~a & v;
T[i].tag ^= v;
}简要题意：给定一个长度为 $n$ 的序列 $a_i$，求 $\sum_{i=1}^n\sum_{j=i+1}^{n}cnt_{a_i\oplus a_j}$，其中 $cnt_x$ 表示 $x$ 的二进制表示下 $1$ 的个数， $\oplus$ 表示异或
$n\le 36666666,a_i\le 2^{64}-1$
简要题解：首先容易得到 $O(n\log n)$ 的做法，即我们对于每一位统计 $0$ 和 $1$ 的数量 $s$ 和 $t$，这一位的贡献就是 $s\times t$
类比这个做法，我们一次枚举 $w$ 位，然后记录这 $w$ 位的结果，最后 $O(\frac{64}{w}(2^w)^2)$ 统计答案即可，时间复杂度为 $O(\frac{64}{w}(n+2^{2w}))$，取 $w = 8$ 即可通过此题
简要题意：现在有 $n$ 堆石子 $a_i$，$Alice$ 和 $Bob$ 准备玩最经典的取石子游戏，但是现在 $Bob$ 可以作弊，$Bob$ 在游戏开始前，可以选择移除 $k\in [0,n-1]$ 堆石子，现在再给定一个整数 $d$，求 $Bob$ 移除 $k$ 堆后先手必败的方案数，要求 $k$ 是 $d$ 的倍数
$n\le 5\times 10^5,d\le 10, a_i\le 10^6,\sum_{i=1}^na_i\le 10^7$，空间限制 $64MB$
简要题解：稍微转换一下题意能够得到我们需要求选了 $m\in [0,n-1]$ 堆，异或和为 $t$ 的方案数
首先 $d$ 的倍数等价于模 $d$ 为 $0$，所以我们不需要维护具体选了几堆，直接维护模 $d$ 为多少
另外注意到 $\sum_{i=1}^n a_i\le 10^7$，我们将 $a_i$ 排序，那么前面所有数的异或和是不会超过 $2^{hb+1}-1$ 的，$hb$ 为当前数二进制最高位的 $1$，那么我们直接做背包的复杂度就为复杂度为 $O(d\sum_{i=1}^na_i)$，注意需要特判所有数都选的情况
简要题意：现在有 $n$ 次询问，每次询问给定 $[l,r]$，求 $[l,r]$ 异或和/与和/或和
$n\le 5\times 10^6, 0\le l\le r< 2^{64}$
简要题解：异或显然，或和与的公式就不在推导了，直接给出
1
2
3if (opt == 1) write(l & -1ull << __lg(l ^ r)); // 与
else if (opt == 2) write(r | (1ull << __lg(l ^ r)) - 1); // 或
else write(get_xor(r) ^ get_xor(l) ^ l);简要题意：给定一个长度为 $n$ 的 $01$ 序列 $a_i$，现在要执行 $k$ 次操作，每次操作将所有 $a_i$ 异或上 $a_{i-1}$ 得到 $a’_i$，求最终的序列
$n\le 3\times 10^6,k\le 10^9$
简单分析容易得到 $a_i=\sum_{j=0}^i\binom{k}{i-j}a_j\bmod 2$，注意到模 $2$，那么组合数 $\binom{k}{x}$ 不等于 $0$ 当且仅当 $x$ 是 $k$ 的子集
那么如果我们取 $k=2^t$，那么 $\binom{k}{x}$ 只有当 $x$ 等于 $k$ 和 $0$ 是才为 $1$，那么我们可以将 $k$ 二进制拆分，每次做 $2$ 的次幂次操作，操作可以用 $bitset$ 加速，时间复杂度 $O(\frac{n\log k}{64})$
2022 Jiangsu Collegiate Programming Contest H Super Gray Pony
字典序
CF 1453B Suffix Operations 前后缀操作将数组转换成差分数组之后相当于只操作一个位置
差分
简要题意：给定两个长度为 $n$ 的数列 $a_i,b_i$，现在有 $m$ 个操作，每次操作给定一个区间 $[l,r]$ 以及将要操作的数列是 $a$ 还是 $b$，然后将区间内的数按顺序加上 $f_i$，其中 $f$ 是斐波那契数列，求每次操作后 $a$ 数列是否和 $b$ 数列完全相同
$n,m\le 3\times 10^5$
简要题解：我们考虑差分，注意到 $a_{i+2}$ 所增加的数恰好为 $a_i$ 和 $a_{i+1}$ 所增加的数的和，那么我们构造一个这样的差分，令 $d_i=a_{i}-a_{i-1}-a_{i-2}$，那么这样一个区间加的操作，我们只需要修改 $a_{l},a_{l+1},a_{r+1},a_{r+2}$ 这四个位置即可
至于如何判断相等，我们只需要将其看做 $a-b$，然后维护 $0$ 的个数即可
双指针
2020年广西省CCPC大学生程序设计竞赛 A Landlord 求有多少子矩阵的值小于给定数字
简要题意：给定一个长度为 $n$ 的字符串 $S$ 和一个整数 $k$，定义两个长度相同的字符串 $k$ 匹配为它们对应位置不同不超过 $k$ 次，求对于所有 $i\in[1,n-1]$，求出 $S$ 的 $pre_i$ 和 $suf_{i+1}$ 的 $k$ 匹配子串有多少个
$n,k\le 3000$
简要题解：我们考虑对于起始位置间隔为 $m$ 的两个起点 $s_1$ 和 $s_2$，满足 $s_2-s_1=m$，求最远的延伸长度 $l$，满足 $S[s_1,s_1+l-1]$ 与 $S[s_2,s_2+l-1]$ $k$ 匹配，注意到这个东西是有单调性的，即如果将 $s_1$ 和 $s_2$ 均向后一位，终点也会向后移动
对于所有 $m\in[1,n-1]$ 都求完答案后，我们会得到 $O(n^2)$ 个三元组 $(s_1,s_2,l)$ 表示两个起点和延伸长度，一个三元组对答案的贡献可以轻松得到，对于这个贡献，我们可以差分两次来做到 $O(1)$ 累加
时间复杂度 $O(n^2)$
无删除双指针
模板
1 | int l = 0, mid = 0, r = 1, ans = 0; R.setone(); |
调和级数
Uoj #21【UR-1】缩进优化 找到一个 $k$ 使得 $\sum_{i=1}^n a_i-(k-1)\sum_{i=1}^n\lfloor \frac{a_i}{k}\rfloor$ 最小，其中 $a_i$ 和 $n$ 同阶
括号序列
简要题意：给定一个包含 $?$ 的长度为 $n$ 的括号序列，求有多少子区间 $[l,r]$ 可以通过将 $?$ 转换成 $($ 或 $)$ 变成一个合法的括号序列
$n\le 3000$
简要题解：如果区间 $[l,r]$ 合法，那么一定有对于 $[l,r]$ 中的任何一个前缀，都存在 $(+?\ge)$，任何一个后缀都存在 $)+?\ge($
那么我们对于每个左端点预处理出最长合法的右端点，每个右端点预处理出最长合法的左端点即可
时间复杂度 $O(n^2)$
一些比较杂的东西
$(\sum a_i)^k$ 的分解
简要题意：给定一个 $n\times n$ 的矩阵 $a$，$a$ 中每个位置上有一个数。你要从左上角 $(1,1)$ 走到右下角 $(n,n)$，每次只能向下或者向右走。将沿途的格子上的数组依次记录下来，可以得到一个长度为 $2n-1$ 的序列，选择的路线不同，可能会得到不同的序列，要求对于每一个序列 $Q$，计算有多少条路线对应这个序列 $Q$，路线的个数记为 $f(Q)$。求 $\sum f^2(Q)$
$n\le 300$
简要题解：首先我们尝试将平方给干掉，假设 $f(Q)$ 为 $x$，那么它的贡献为 $x^2$
我们将其认为对于每条在 $x$ 中的路线，它与其它属于 $x$ 的路线都记一次贡献，那么一共还是 $x^2$ 次
那么我们现在得到了另一种计算贡献的方式，相当于两个人从 $(1,1)$ 走到 $(n,n)$，得到序列相同的走法
这个东西显然可以 $O(n^2)$ $dp$
简要题意：给定一个长度为 $n$ 的序列 $a_i$，求 $\sum_{i=1}^n\sum_{j=1}^n(a_i\oplus a_j)^2$，$\oplus$ 代表异或运算
$n\le 5\times 10^5$
简要题解：我们考虑平方分解：$(\sum_{i=1}^na_i)^2=\sum_{i=1}^n\sum_{j=1}^na_ia_j$
那么对于 $(a_i\oplus a_j)^2$，我们可以看做是若干个二进制的和的平方，那么我们现在只需要枚举两个二进制位进行计算即可，时间复杂度 $O(n\log ^2n)$
对于两个区间 $[a,b]$ 和一个固定长度的区间 $L$，他们的交的最大值是两个区间中点距离最近的时候
换句话讲，区间中点的距离和交的值是负相关的，区间中点的距离越小，交的值不降 CF 1452E Two Editorials
CF 1405C Balanced Bitstring 给定一个 $01$ 串，串中有一些位置可以随便填 $0$ 或 $1$，要求每个长度为 $k$ 的子串均有相等的 $0$ 和 $1$
每个物品的重量大于等于小于它的物品的重量的二倍，这个东西类似于二进制
2020-2021 ACM-ICPC Brazil Subregional Programming H SBC’s Hangar
简要题意：给定一个 $n$ 个 $m$ 条边的无向连通图。现在每个点有一个限制 $d_i$，表示这个点的度数需要为奇数或偶数或者没有限制($d_i=-1$ 表示无限制)，问是否能从原图中选出若干条边满足所有限制。
$n,m\le 3\times 10^5$
简要题解：注意到选择边无法改变点的度数和的奇偶性，所以如果有限制的点的度数和为奇数则必须将一个 $d_i=-1$ 变成 $d_i=1$，这样做一定有解
因为原图是联通的，所以我们将问题转换成了一个经典问题
有一棵点的颜色为黑色或白色的树，现在有偶数个黑点，每条边选择与否可以翻转连接的两个点的颜色，需要求一个可行的选择方案使所有点都变成白色，注意到只要黑点的个数为偶数则一定有解
所以我们随便搞出一棵生成树就行了
将第 $k$ 位变成 $v+k-1$，可以直接抹平
统计所有数对 $(l,r)$ 的价值，其中 $(l,r)$ 的价值为 $[l,r]$ 中的最小值乘以最大值
CF gym 102562B Bitwise Party 最大值或上最小值，求所有区间的价值的异或和
简要题意：给定一个长度为 $n$ 的序列，求有多少区间 $[l,r]$ 满足，区间 $[l,r]$ 的最小值 $mn$ 和最大值 $mx$ 的二进制表示 $1$ 的个数相同
$n\le 10^6, a_i\le 10^{18}$
简要题解：我们考虑经典的最小值最大值分治，枚举左端点，维护左边区间的后缀 $max$ 和 $min$，同时维护两个位置 $pm$ 和 $pn$ 表示左边当前位置的后缀 $max$ 和 $min$ 在右边区间仍然是最大值和最小值的最靠右的位置
对于右端点在 $[m+1,\min\lbrace pn,pm\rbrace]$，区间最大值和最小值都在左边，直接判断 $max$ 和 $min$ 的位数是否相等即可
右端点在 $[\min\lbrace pn,pm\rbrace+1,\max\lbrace pn,pm\rbrace]$，区间最大值或者最小值在左边，另一个在右边，我们相当于要统计 $[\min\lbrace pn,pm\rbrace+1,\max\lbrace pn,pm\rbrace]$ 内二进制表示 $1$ 的个数为定值的个数，这个东西如果我们预处理前缀和的话复杂度是 $O(n\log ^2 n)$，但如果我们离线下来做一个差分，这样就能做到 $O(n\log n)$
右端点在 $[\max\lbrace pn,pm\rbrace +1,r]$，可以预处理，时间复杂度 $O(n\log n)$
所有区间覆盖的情况都可以通过将相交区间变成一个大区间和一个被大区间包含的小区间，从而使得区间覆盖变成括号序列（存疑
简要题意：给定一个长度 $n$ 的序列 $a_i$，现在有一个机器人，它可以任何点为起点，每次可以选择向左或向右移动一格，但不能离开 $[1,n]$，现在它会走 $k$ 步，定义一条路径的权值为机器人经过的所有点的点权和，点被多次经过算多次。现在有 $q$ 个询问，每次给定 $x,y$，修改 $a_x=y$，求机器人的所有路径的权值和
简要题解：路径可逆
我们令 $f[i][j]$ 表示走了 $i$ 步在点 $j$ 的路径条数
注意到因为我们开始的起点是所有点且路径可逆，所以 $f[i][j]$ 同样可以表示从 $j$ 开始走 $i$ 步的方案数
那么所有路径中经过点 $j$ 的次数就是 $\sum_{i=0}^kf[i][j]\times f[k-i][j]$
倒叙枚举前缀翻转可以不用平衡树
求连通块的其它方法，我们从每一个没到过的点开始 $dfs$，每次开始 $dfs$ 就代表有一个新的连通块
简要题意：给定一个长度为 $n$ 的序列 $a_i$，每个数的范围为 $[0,2^m-1]$，$x$ 和 $y$ 之间有一条无向边的条件为 $a_x$ 与 $a_y$ 的与为 $0$，求连通块个数
简要题解：我们从每一个没到过的点开始 $dfs$，每次开始 $dfs$ 就代表有一个新的连通块
现在我们考虑什么情况下 $x~and~y=0$，当且仅当 $x$ 取反后，$y$ 是 $x$ 的子集，那么我们考虑将 $x$ 取反，然后每次扔一个 $1$，向下 $dfs$ 即可
简要题意：给定一个 $n$ 个点 $m$ 条边简单无向图，求该图的补图的连通块个数
$n,m\le 2\times 10^5$
简要题解：我们考虑每次从一个没有到过的点开始 $dfs$，$dfs$ 的次数即为连通块的个数
那么我们全局维护一个当前没有到过的点的集合 $S$，与一个点连通的点即为 $S$ 中与其没有边的点，我们遍历 $S$ 中所有点，保留有边的点，然后其他点全部删除，这样每次暴力做的时间复杂度为 $O(n+m)$
笛卡尔树启发式合并
简要题意：给定一个长度为 $n$ 的序列 $a_i$，求有多少子区间 $[l,r]$ 满足 $[1,r-l+1]$ 中的所有数都出现一次
$n\le 3\times 10^5$
简要题解：首先转换一下子排列的定义：
- 没有重复数字
- 最大值为 $r-l+1$
我们考虑按照每个数作为最大值的区间来构建笛卡尔树
然后我们对于每个数，枚举小的那一半，知道左端点就能得到右端点
注意到这里枚举小的那一半的时间复杂度仅为 $O(n\log n)$，类似于启发式合并
至于如何判断没有重复数字，我们可以用最简单的方法，查询区间 $pre$ 的最大值
只要满足区间 $pre$ 的最大值小于 $l$ 就一定不存在重复数字
我们使用 $st$ 表做到 $O(1)$ 询问区间最值，这样总的复杂的就是 $O(n\log n)$
如果加点均满足 $(l,r),l\le r$ 那么二维树状数组可以用来做矩阵查询
2020-2021 ACM-ICPC, Asia Seoul Regional Contest I Stock Analysis
连通块的个数等于点的个数减掉边的个数（某些情况下
将矩阵看成邻接矩阵从而转化成图论问题
询问在正向操作时很难处理，逆向操作时较为简单
每次转移可以看做是从所有点 $s$ 以相同的方法跳 $k$ 次，且我们只需要记录是否可达
那么显然当我们跳到一个已经到过的点就可以直接停止，因为之后会从这个点接着跳
通过交换 $a_i$ 最大化 $\sum_{i=1}^n |a_i-b_i|$
首先我们思考如何求可以交换无限次后这个东西的最大值
我们首先考虑将绝对值拆开，那么相当于在 $a_i$ 和 $b_i$ 上分别加上正号和负号，且只需要总的正号的数量等于负号的数量即可，不要求 $a$ 中的正号等于负号的数量，那么这个时候最大值就是将 $a$ 和 $b$ 中的所有数拿出来排序然后前 $n$ 个取正号，后 $n$ 个取负号
另外我们需要知道，有可能出现正负号和实际绝对值相反的情况，但是如果交换这一对正负号，只会使得解变优，所以在题目求最优的前提下，正负号是可以随意分配的
接下来我们考虑给定 $a$ 和 $b$ 后如何求最小需要交换多少次可以达到最大值
我们按照之前的想法将符号分配好，那么需要交换的都是 $(+a_i,+b_i)$ 和 $(-a_i,-b_i)$，所以我们每次换一下 $++$ 和 $—$ 即可，注意到 $++$ 的数量一定等于 $—$ 的数量
然后我们在思考给定 $a$ 和 $b$ 以及可以交换的次数 $k$ 之后，如何求恰好交换 $k$ 次后的最大值
首先给出一个结论，在 $n>2$ 的情况下，恰好交换 $k$ 次和至多交换 $k$ 次是一样的
不妨假设我们交换了 $s(s<k)$ 次就得到了最优答案且已经分配好了符号，那么 $a$ 中至少有两个 $a$ 是同符号的，我们只需要交换这两个 $a$ 即可
那么在有这个结论之后，我们考虑如何交换，对于 $(a_i,b_i)$ 和 $(a_j,b_j)$，如果交换之后答案更优，需要这两个区间没有交点，且交换之后的价值会增加 $2\times (min\lbrace a_i,b_i\rbrace-max\lbrace a_j,b_j\rbrace)$，通过这个式子我们发现可以将贡献拆开，那么我们直接对于 $min\lbrace a_i,b_i\rbrace $ 和 $-max\lbrace a_i,b_i\rbrace$ 排序取前 $k$ 大相加即可
拆绝对值分配正负号
简要题意：给定 $2n$ 个数对 $(a_i,b_i)$，现在要求将这 $2n$ 个数对分成 $n$ 组，如果 $x$ 和 $y$ 分到一组，那么这一组的贡献是 $max\lbrace|a_i-a_j|,|a_i-b_j|,|b_i-a_j|,|b_i-b_j|\rbrace$，求最大分配
简要题解：不妨令 $a_i\le b_i$，我们考虑拆掉绝对值，那么这 $2n$ 个数对中，一定有 $n$ 个的贡献是 $-a_i$，另外 $n$ 个贡献是 $+b_i$
关于如何选择每个数对的是负贡献还是正贡献，我们任取两个数对来考虑，$-a_1+b_2>a_2+b_1$ 等价于 $a_1+b_1<a_2+b_2$，那么我们按照 $a_i+b_i$ 来排序，前 $n$ 个取 $-a$，后 $n$ 个取 $b$ 即可
2021 ICPC Southeastern Europe Regional Contest G Max Pair Matching
一个经典的拆 $max$ 的做法
$f_i=max(f_{i-1}+d_i,u_i)$，其中 $f_l=u_l$ 且需要满足 $f_i\le v_i$，问区间 $[l,r]$ 是否满足
我们拆开这些 $max$，可以得到下面这个式子
$u_l\le v_l,max(u_l+d_l,u_{l+1})\le v_{l+1},max(u_l+d_l+d_{l+1},u_{l+1}+d_{l+1},u_{l+2})\le v_{l+2},\cdots$
简要题解：给定长度 $n$ 和若干个前缀的单调栈的大小，要求构造一个满足条件的排列
$n\le 10^6$
构造排列时，我们可以考虑构造符合大小关系的有向图，然后跑拓扑序
简要题意：给定 $n$ 个区间和 $k$，求将所有区间划分成 $k$ 组的最大价值和，每组区间的价值为它们的交，交不能为空，如果无法划分输出 $-1$
$1\le k\le n\le 5000$
简要题解：将包含其它的区间去掉，然后就可以保证相邻若干个分一组，令 $f[i][j]$ 表示前 $i$ 个分了 $j$ 组，单调队列优化可以做到 $O(nk)$
将包含其它区间的大区间去掉后，按左端点排序可保证右端点也单调
简要题意：给定一个 $n\times m$ 的矩形，要求在每个位置填 $0$ 或 $1$，要求每一行和每一列的异或和都是 $k$，求方案数
$1\le n,m\le 10^{18}$
简要题解：注意到我们前 $n-1$ 行 $m-1$ 列无论怎么填，最后一行和最后一列都能选择对应的数字满足条件
需要注意的是如果 $|n-m|$ 是奇数且 $k=-1$ 的情况是无解的
其他情况下答案就是 $2^{(n-1)\times (m-1)}$
前面乱选，只通过调整最后一部分来满足约束
简要题意：给定一棵 $n$ 个点的无根树和 $k$，求所有划分成 $k+1$ 个连通块的方案的价值和，一个划分方案的价值定义为 $k+1$ 的连通块的大小的乘积
$n\le 5\times 10^4,k\le 100$
简要题解：
最朴素的 $dp$ 是 $f[u][m][S]$，表示分成了 $m$ 棵子树，$u$ 所在的子树的大小是 $S$
但是这样的时间复杂度显然无法通过此题，我们考虑求一个等价的问题，删掉 $k$ 条边，并且在每个连通块里都选恰好一个点的方案数
我们令 $f[u][m][0/1]$ 表示已经断了 $m$ 条边，$u$ 所在的子树是否已经选点，时间复杂度 $O(nk^2)$
将一棵树划分成 $k+1$ 个连通块的所有方案数 等价于 删掉 $k$ 条边，并且在每个连通块里都选恰好一个点的方案数
简要题意：简要题意：给定两棵大小均为 $n$ 的树，求一个最大的点集满足，这些点在第一棵树上构成一条深度递增的链，即满足所有点之间都存在祖宗关系，在第二棵树上任意两点不存在祖宗关系
$n\le 3\times 10^5$
简要题解：我们考虑对于每个点求其作为链的最底端的答案，我们令 $h[u]$ 表示 $u$ 作为最底端时，深度最深的点满足在第二颗树上与 $u$ 存在祖先关系的点的深度
那么答案显然是 $max\lbrace dep[u]-h[u]\rbrace$
我们考虑如何求 $h$，注意到两个点 $u$ 和 $v$ 如果存在祖先关系，当且仅当 $u$ 的子树和 $v$ 的子树有交，那么我们在第一棵树上 $dfs$，然后每到一个点 $u$，我们就将线段树上 $in[u]$ 到 $out[u]$ 都与 $dep[u]$ 取 $max$，但是取 $max$ 并不能撤回，所以我们考虑直接用主席树，时间复杂度 $O(n\log n)$
树上两点 $u$ 和 $v$ 如果存在祖先关系当且仅当 $u$ 的子树和 $v$ 的子树有交
给定一个序列 $a$，有 $a_i>i$，求最长的一段子区间 $[l,r]$ 满足 $(max_{i=l}^ra_i)>r$，我们可以枚举每个点作为左端点，右端点就是 $max_{j=i}^na_j-1$
简要题意：给定一个长度为 $n$ 的序列 $a_i$，求有多少子区间存在绝对众数
$n\le 5\times 10^6$
我们考虑数字 $v$ 作为绝对众数出现的区间，我们令 $v$ 所在的位置都是 $1$，其它位置都是 $-1$，那么显然区间和大于 $0$ 的区间都是 $v$ 作为绝对众数出现的区间
$+1/-1$ 序列的前缀和的逆序对可以 $O(n)$，甚至可以在 1 的个数 或者 $-1$ 的个数 的时间复杂度内完成
简要题意：给定一张 $n$ 个点 $m$ 条边的无向连通图，每个点有一个权值 $a_i$，每次操作可以使一条边相连的两个点同时增加任意一个整数值，求是否能使所有点的权值都为 $0$
$n,m\le 2\times 10^5$
简要题解：首先注意到我们的操作不能改变权值总和的奇偶性，所以如果和为奇数则一定不行
然后我们注意到我们可以将距离为奇数的两个点同时增加相同的数值，距离为偶数的点一个增加另一个减少相同的数值
这启示我们考虑二分图的性质，首先我们将这张图分成两种情况考虑，二分图和不是二分图
如果该图是二分图，那么我们只需要看一下两边点的总和是否相等，相等则一定有解，不相等则一定无解
如果该图不是二分图，那么就一定存在奇环，对于一个存在奇环的图，任意两个点都存在一条长度为奇数的路径，所以一定有解
简要题意：给定一个 $n$ 个点 $m$ 条边的带权无向图，现在有 $k$ 次询问，每次询问给定一个常数 $x$，求如果将边权改为 $|w-x|$，$w$ 为改之前的边权，求最小生成树
$n\le 50,m\le 300,k\le 10^7$
简要题解：对于求最小生成树，我们优先考虑 $kruskal$ 算法，另外注意到询问非常多，我们考虑离线处理
注意到如果我们使用 $kruskal$ 的话，那么我们只需要关注所有边的边权的相对关系，注意到只有当 $x$ 为 $\lceil\frac{w_i+w_j}{2}\rceil$ 时，$w_i$ 和 $w_j$ 这两条边的位置会发生变化，那么容易得到只有 $O(m^2)$ 种顺序，且每种顺序的 $x$ 都是一个区间&
然后我们考虑如何处理询问，我们离线后对于每种顺序的左端点为 $x$ 将边排序后做 $kruskal$ 即可，记录选中的边原本的权值是否大于 $x$，然后就可以求出答案
有几个需要注意的地方，分界点除了 $\lceil\frac{w_i+w_j}{2}\rceil$ 以外，还要加入每种边的权值，这样可以防止边原本的权值和 $x$ 的大小关系发生变化，另外排序过程中第二关键字要按照边原本权值降序排序，保证答案尽量小
时间复杂度 $O(m^3\log m+k\log m^2)$
简要题意：给定两个长度为 $n$ 的串 $S$ 和 $T$，现在可以将 $T$ 的某一个子串翻转，求翻转后 $S$ 和 $T$ 最多有多少个对应位置相等
$n\le 1000$
简要题解：对于这种区间翻转的问题，我们考虑区间 $dp$ 的思路，$f_{i,j}$ 由 $f_{i+1,j-1}$ 转移过来即可
The 2021 ICPC Asia Taipei Regional Programming Contest B Maximum Sub-Reverse Matching
简要题意：给定 $n$ 个点，对于每个点求一个离它最近且不是给定点的点，距离是曼哈顿距离
$n\le 2\times 10^5,x_i,y_i\le 2\times 10^5$
简要题解：注意到答案的点一定是距某个给定点为 $1$ 的点，我们把这些点都加进来跑多关键点最短路即可
简要题意：给定一个长度为 $n$ 的序列 $a_i$，令 $d_i=max(a_1, a_2, \cdots, a_i)-min(a_1, a_2, \cdots, a_i)$，现在要求重新排列 $a$，使得 $\sum_{i=1}^nd_i$ 最小
$n\le 2000$
简要题解：我们考虑向一个序列中添加一个最值，那么最值一定要放在序列的最后面，我们考虑用区间 $dp$ 来排序
这里我们容易想到将 $a_i$ 排序，令 $f_{i,j}$ 为区间 $[i,j]$ 重拍后的最小代价，容易得到 $f_{i,j}=\min(f_{i+1,j},f_{i,j-1})+a_i-a_j$
时间复杂度 $O(n^2)$
简要题意：现在有一个长度为 $n$ 的序列 $a_i$，定义 $F_0(l,r)$ 为区间 $[l,r]$ 内的逆序对个数，同时 $F_k(l,r)=\sum_{i=l}^r\sum_{j=i}^rF_{k-1}(i,j)$，给定 $k$，求 $F_k(1,n)$
$n\le 3\times 10^5$
简要题解：观察 $F_k(l,r)=\sum_{i=l}^r\sum_{j=i}^rF_{k-1}(i,j)$，容易发现这个东西类似于前缀和，区间前缀和
我们考虑一个逆序对 $(x,y)$，它对 $F_k(l,r)$ 的贡献是相当与令 $a_y=1$，同时向后做 $k+1$ 次前缀和到 $r$ 的答案乘上令 $a_x=1$，同时向前做前缀和到 $l$ 的答案，那么就是 $\binom{r-x+k}{k}\times\binom{x-l}{k}$，这些东西用树状数组维护即可
简要题意：现在有 $n$ 堆石子 $a_i$，$Alice$ 和 $Bob$ 准备玩最经典的取石子游戏，但是现在 $Bob$ 可以作弊，$Bob$ 在游戏开始前，可以选择移除 $k\in [0,n-1]$ 堆石子，现在再给定一个整数 $d$，求 $Bob$ 移除 $k$ 堆后先手必败的方案数，要求 $k$ 是 $d$ 的倍数
$n\le 5\times 10^5,d\le 10, a_i\le 10^6,\sum_{i=1}^na_i\le 10^7$，空间限制 $64MB$
简要题解：稍微转换一下题意能够得到我们需要求选了 $m\in [0,n-1]$ 堆，异或和为 $t$ 的方案数
首先 $d$ 的倍数等价于模 $d$ 为 $0$，所以我们不需要维护具体选了几堆，直接维护模 $d$ 为多少
另外注意到 $\sum_{i=1}^n a_i\le 10^7$，我们将 $a_i$ 排序，那么前面所有数的异或和是不会超过 $2^{hb+1}-1$ 的，$hb$ 为当前数二进制最高位的 $1$，那么我们直接做背包的复杂度就为复杂度为 $O(d\sum_{i=1}^na_i)$，注意需要特判所有数都选的情况
简要题意：给定一个 $n$ 个点 $m$ 条边的简单无向图，求是否存在一条链，使得将这条链上的点以及这些点的所有边都去掉后，剩下的点可以划分成两个集合，满足不同集合的点之间没有连边，链至少需要包含一个点，集合可以是空集
$n,m\le 2\times 10^5$
简要题解：我们考虑一种神奇的 $dfs$ 的方法
一开始我们令所有点都属于集合 $A$，我们从任意一个点开始 $dfs$，每当我们 $dfs$ 到一个点，我们将就其从 $A$ 中删除，加入到我们所选择的这条链中，当我们回溯到某一个点的时候，我们将其从链中删除，加入到集合 $B$，显然集合 $A$ 和集合 $B$ 中的点之间不会存在连边，同时每次我们会将集合 $A$ 的大小减一或者将集合 $B$ 的大小加一，那么一定有存在一个时刻，满足 $A$ 的大小等于 $B$ 的大小
时间复杂度 $O(n)$
简要题意：给定一张 $n$ 个 $m$ 条边的简单无向连通图，现在有 $q$ 次询问，每次询问给定若干条边，求将这些边的删掉后原图是否连通，询问之间独立，强制在线
$n\le 10^5,m\le 5\times 10^5$
简要题解：注意到只有删边，我们考虑对原图建立一棵生成树，首先只有删掉这棵生成树上的边时才有可能导致原图不连通，那如果我们删掉树上的一条边 $(u,v)$ 使原图不连通，则说明所有能够连接 $u$ 和 $v$ 这两个连通块的非树边都被删掉了
那么相当于是每次删掉一个树边后判断是否该树边对应的非树边集合是否已经全部被删到，我们可以为每条非树边随机一个 $ull$ 范围内的整数，同时树边的值为它所对应的非树边的值的异或和，那么每次删边我们需要把边加入线性基，之后只需要判断线性基中是否出现 $0$ 即可
简要题意：现在你有一个集合 $S$，$S$ 中只有一个元素 $0$，同时有 $q$ 次操作，操作有三种，第一种操作向集合中加入一个数 $x$；第二种操作从集合中删掉数 $x$；第三种操作给定 $k$，询问集合的 $k-mex$，$k-mex$ 表示最小的数 $x$，满足 $x$ 是 $k$ 的倍数，且在 $S$ 中不存在
$q\le 2\times 10^5,x,k\le 10^{18}$
简要题解：我们首先考虑不存在删除操作如何做，容易发现我们对于每个 $k$ 维护答案即可，即我们记录最大的 $x$，满足 $0,k,\cdots,x-k$ 都存在且 $x$ 不存在，这个东西的具体操作就是在每次询问的时候暴力检查，注意到链的总长度大概是 $O(n\log )$ 的级别
然后我们考虑删除，对于每个 $k$ 我们依然记录最大的 $x$，不过我们记录的 $x$ 是历史最大，同时我们考虑对于每个 $k$ 记录 $k$ 到 $x$ 之间后来被删掉的数 $y$，这样我们每次询问的时候暴力判断每个被记录的 $y$ 是否被重新加入，如果全部被重新加入则从 $x$ 开始再次暴力判断
那么我们考虑当我们删掉一个数 $x$，我们如何找到 $x$ 作为 $y$ 的所有 $k$，这个东西其实非常简单，我们对于每个数 $x$ 开一个 $set$ 记录数 $x$ 所在的所有链的链尾，这样如果我们删掉 $x$，就在它所在的所有链尾将其作为 $y$ 加入，对于这个 $set$ 的维护，我们在询问暴力的时候维护即可
简要题意：给定一个 $n$ 个点 $m$ 条边的有向图，同时给定 $k$ 个点，求这 $k$ 个点两两最短距离的最小值
$n\le 10^5,m\le 5\times 10^5$
简要题解：我们考虑按照二进制的每一位为 $0$ 或 $1$ 将这 $k$ 个点划分成两个集合，$s$ 连其中一个集合，$t$ 连另一个，然后求 $s$ 到 $t$ 的最短路，注意到这样一定可以求出最小值
时间复杂度 $O(n\log m\log n)$