知识回顾
-
巩固：线段树，贪心
-
深入研究：数论，容斥，除法分块，根号分治
-
简单了解：lucas，prufer序列，莫比乌斯反演
练题
可以发现这符合小根堆的性质，把它建出来。
定义 \(f_u\) 为以 u 为根的子树的方案数，转移方程为：
\[f_u=\dbinom{siz_u-1}{siz_{2\cdot u}}\cdot f_{2\cdot u} \cdot f_{2\cdot u+1} \]由于模数可能小于 n，所以求组合数时要用到 lucas 定理。
容斥问题。
定义 \(f_i\) 为最多用 i 种颜色构造出的合法方案数。那么答案为：
\[ans=\sum\limits_{i=1}^{c}\dbinom{c}{i}\cdot f_i \cdot (-1)^{c-i} \]对于 \(f_i\)，我们可以枚举考虑多少列，然后再做一遍容斥，即：
\[f_i=\sum\limits_{j=1}^{m}\dbinom{m}{j}\cdot ((i+1)^j-1)^n \cdot (-1)^{m-j} \]复杂度 \(O(mc \log m)\)。
prufer序列的定义：
我们需要重复进行以下操作，直至树中只剩下两个点：
-
找到一个度数为1，且编号最小的点。（其中编号最小保证了后面将会提到的 prufer 序列的唯一对应性，同时也方便从 prufer 序列转化回无根树）
-
把这个点的父亲节点加入序列，然后把这个点从树中删除。
然后我们就得到了一个长度为 n-2 的序列，这就是 prufer 序列。
如果一个节点的度数为 d，那么这个节点的编号会在序列里出现 d-1 次。
于是我们可以用组合数算出每个节点的情况，即：
\[\frac{(n-2)!}{\prod\limits_{i=1}^{n}(d_i-1)!} \]组合数 \(O(n^2)\) 预处理就行了。
和上一题几乎一样。
假设有 k 个点的度数是定的，度数和减去 k 的值为 s，那么这些点的排列方案数为：
\[\dbinom{n - 2}{s}\cdot \frac{s!}{\prod\limits_{i=1}^{k}(d_i-1)!} \]剩下的 n-2-s 个位置可以随便选，所以答案为：
\[\dbinom{n - 2}{s}\cdot \frac{s!}{\prod\limits_{i=1}^{k}(d_i-1)!}\cdot (n-k)^{n-2-s} \]由于没有取模，建议使用 Python（bushi。
非常常见的套路。
枚举上下界，然后从左往右扫，看有多少个白条，加上 cnt 就行了。
复杂度 \(O(n^3)\)。
简单线段树，维护区间子段和。
考虑对于每个区间定义 lmax 为最大前缀，rmax 为最大后缀，maxn 为最大子段和，d 为区间和。
询问的时候直接多种情况拼接，考虑全就行了。
复杂度 \(O(n \log n)\)。
首先要知道 sin 和 cos 的基本公式。
\[\sin(a+x)=\sin a\cdot \cos x+\cos a\cdot \sin x \]\[\cos(a+x)=\cos a\cdot \cos x-\sin a\cdot \sin x \]然后维护一个 sin 与 cos 的区间和就行了。
复杂度 \(O(n \log n)\)。
线段树，考虑怎么 pushup。
定义：
-
maxn 为 a 的最大值。
-
minn 为 b 的最小值。
-
lmax 为最大的 \(a_i - b_j\)，其中 j < i。
-
rmax 为最大的 \(a_i - b_j\)，其中 j > i。
-
ans 为答案。
合并的时候考虑一下 b 的最小值在左区间还是右区间，分类讨论。
复杂度 \(O(n \log n)\)。
采用哈希。
线段树维护区间最大值、最小值、和、平方和，然后询问的时候就 \(O(1)\) 算出标准答案对比一下。
可以用 unsigned long long 自然溢出。
复杂度 \(O(n \log n)\)。
和上一题很像。
维护区间和 sum，询问时判断首尾和 sum 是否相等。
由于数据很水，可以通过。
复杂度 \(O(n \log n)\)。
枚举 X 不好弄，考虑枚举约数。
对于约数 d，\([1,n]\) 中一共有 \(\lfloor \frac{n}{d}\rfloor\) 个数有它。
后者是个除法分块，一共有 \(\sqrt n\) 种不同的数，\([l,\frac{n}{\frac{n}{l}}]\) 中的数是相等的。
于是可以用求和公式算出，即：
\[\frac{(l+r)\cdot (r-l+1)}{2}\cdot \lfloor \frac{n}{l} \rfloor \]最后答案为 \(getans(y)-getans(x-1)\)。
复杂度 \(O(\sqrt n)\)。
除法分块板子题。
复杂度 \(O(T \log n)\)。
思维题。
可以发现，最多只需要 n-1 次操作就可以排完序。
选择一个数不动，将其它数按顺序排在这个数的左右两侧。
仔细一想可以发现，对于一组数值连续的子序列，我们也可以用类似的方式处理，所以只需要求出最大值，再拿 n 减一下就行了。
复杂度 \(O(n)\)。
枚举施展魔法的次数。
定义 \(f_{i,j}\) 为施展小于 j 次魔法 i 的最小代价。
最后取 min 值就行了。
复杂度 \(O(n^2)\)。
可以想到离散化，然后倒着判断有没有空位。
需要注意的是离散化后原来有的空位可能会被挤没，所以对于 x，还要将 x+1 和 x-1 加入离散化。
复杂度 \(O(n \log n)\)。
神奇的分治题。
对于每一个位置，找到其相同的前继和后继。
假设当前区间为 \([l,r]\)，如果其中存在位置 x，满足 \(pre_x<l\) 且 \(nex_x>r\)，那么只需要判断 \([l,x-1]\) 和 \([x+1,r]\) 是否不无聊就行了。
为了防止超时，我们可以从两端同时逼近，这样最坏的情况下 x 在区间中间。
复杂度 \(T(n)=2\cdot T(\frac{n}{2})+n\)，也就是 \(O(n \log ^ n)\)。
根号分治。
令 \(t=sqrt(n)\)。
若 \(p \le t\)，则直接输出预处理的答案。
否则直接暴力找。
复杂度 \(O((n+m)\cdot \sqrt n)\)
贪心。
先把所有项目都选上，然后找到数量最多的那个，把它禁掉，指针往后移就行了。
证明也很简单。
如果禁的不是数量最多的，那么它会一直影响，所以只能禁它。
复杂度 \(O(nm)\)。
除法分块，和约数和基本一模一样。
复杂度 \(O(\sqrt n)\)。
本来想学一下莫比乌斯反演再去做这题，结果没学懂......
然后发现不需要。
定义 \(F_d\) 为 \(\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}d|\gcd(i,j)\)
则 \(F_d=(\lfloor \frac{n}{d} \rfloor)^2\)。
定义 \(f_d\) 为 \(\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\gcd(i,j)=d\)
则 \(f_d=F_d-f_{k\cdot d}\)。
这东西是个调和级数，复杂度 \(O(n \log n)\)。
最后的答案为：
\[\frac{(\sum\limits_{i=1}^{n}f_i-\frac{n\cdot (n+1)}{2})}{2} \]上面一题的加强版。
由于有多组询问，显然需要预处理。
\[ans(n)=\sum\limits_{i=1}^{n}\sum\limits_{j=i+1}^{n}\gcd(i,j) \]\[\begin{aligned} pre(n)&=ans(n)-ans(n-1)\\ &=\sum\limits_{i=1}^{n}\gcd(i,n)\\ &=\sum\limits_{d|n}d\cdot \left( \sum\limits_{i=1}^{n}\gcd(i,n)=d \right)\\ &=\sum\limits_{d|n}d\cdot \left(\sum\limits_{i=1}^{\frac{n}{d}}\gcd(i,\frac{n}{d})=1\right)\\ &=\sum\limits_{d|n}d\cdot \varphi(\frac{n}{d}) \end{aligned} \]所以可以先线性预处理出 phi 函数，然后枚举每个 d 的倍数。
复杂度调和级数，\(O(n \log n)\)。
莫比乌斯反演入门题。
先根据题意列出式子。
\[\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}[\gcd(i,j) \in prime] \]可以先 \(O(n)\) 预处理出所有的质数，然后枚举。
\[\sum\limits_{k=1}^{cnt}\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}[\gcd(i,j)=p_k] \]考虑让 \(i,j\) 同除以 \(p_k\)。
\[\sum\limits_{k=1}^{cnt}\sum\limits_{i=1}^{\lfloor \frac{n}{p_k} \rfloor}\sum\limits_{j=1}^{\lfloor \frac{m}{p_k}\rfloor}[\gcd(i,j)=1] \]接下来就要用到莫比乌斯反演了。
\[\mu(n)=\begin{cases}1 & n=1\\0 & n \ has \ a \ square \ factor \\(-1)^k & k \ is \ the \ number \ of \ essentially \ different \ prime \ factors \ of \ n \end{cases}\]性质：
\[\sum\limits_{d\vert n}\mu(d)=[n=1] \]证明：
设 \(n=\prod\limits_{i=1}^{k}p_{i}^{c_i}\)，\(n'=\prod\limits_{i=1}^{k}p_i\)。
那么 \(\sum\limits_{d\vert n}\mu(d)=\sum\limits_{d\vert n'}\mu(d)=\sum\limits_{i=0}^{k}C_{k}^{i}\cdot (-1)^i=(1+(-1))^k\)
当且仅当 k 为 0 时，该式为 1，否则为 0。
将 n 替换成 \(\gcd(i,j)\)，就变成了 \(\sum\limits_{d\vert\gcd(i,j)}\mu(d)=[gcd(i,j)=1]\)
所以最开始的式子就变成了
\[\sum\limits_{k=1}^{cnt}\sum\limits_{i=1}^{\lfloor \frac{n}{p_k} \rfloor}\sum\limits_{j=1}^{\lfloor \frac{m}{p_k} \rfloor}\sum\limits_{d\vert \gcd(i,j)}\mu(d) \]考虑枚举 d
\[\sum\limits_{k=1}^{cnt}\sum\limits_{d=1}^{\lfloor \frac{n}{p_k}\rfloor}\mu(d)\cdot \lfloor \frac{n}{p_k\cdot d}\rfloor \cdot \lfloor \frac{m}{p_k\cdot d}\rfloor \]如果只有一组数据，推到这里就可以了，但是有多组数据......（
令 \(T=p_k \cdot d\)，然后枚举 \(T\)。
\[\sum\limits_{T=1}^{n}\lfloor \frac{n}{T}\rfloor\cdot \lfloor \frac{m}{T}\rfloor \cdot \sum\limits_{k=1,p_k \vert T}^{cnt}\mu(\frac{T}{p_k}) \]后面的东西可以预处理！
对于每个质数，枚举他的倍数，加上贡献。
前面的可以除法分块。
复杂度 \(O(n \log \log n+n \sqrt n)\)。
根号分治。
令 \(len=\sum\limits|s|\)
最暴力的方法是枚举模板串的每一个子串，然后字符串哈希求出现个数，复杂度 \(O(len^2)\)。
优化方式很简单，就是只枚举集合里有的长度。
最差情况是 \(1+2+......+t\le len\)，所以 \(t\le \sqrt{2\cdot len}\)，也就是最多有 \(\sqrt{len}\) 种不同的长度，总体复杂度平均下来就是 \(O(len\sqrt{len})\)。
可以用 set 来维护不同长度。
和哈希冲突很像。
对于 \(p\ge \sqrt n\) 的询问，可以直接暴力。
如果 \(p < n\)，就输出预处理的答案。
具体怎么预处理呢？可以对于每一种 p 计算出不同余数的和，然后以 t 为关键字从小到大排序询问，每到一个询问的时候，就将其前面的那些数减掉即可。
复杂度 \(O(n \sqrt n)\)。
要求构造一棵符合二叉搜索树和小根堆的树，本质上和平衡树一样。
我们考虑按照编号从小到大依次插入。
为了符合搜索树性质，每次插入的元素必定在这棵树的右链末端。
可以用栈来维护当前右链，并找到 \(p_v\) 最大的 v，满足 \(p_v < p_u\)，然后将 v 的右儿子更新为 u，将 v 原本的右儿子挪到 u 的左儿子上。
这样既保证了是二叉搜索树，又满足小根堆的性质。
仔细一想，会发现每个元素只会进出栈一次，所以复杂度 \(O(N)\)。
贴一下代码：
#include <bits/stdc++.h>
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*f;
}
typedef long long ll;
const int N = 1e7 + 5;
int n, p[N], ls[N], rs[N], s[N], tail = 0;
int main() {
cin >> n;
for (int i = 1; i <= n; ++i) p[i] = read();
for (int i = 1; i <= n; ++i) {
int cur = tail;
while (cur && p[s[cur]] > p[i]) --cur;
if (cur) rs[s[cur]] = i;
if (cur < tail) ls[i] = s[cur + 1];
s[++cur] = i;
tail = cur;
}
ll ansl = 0, ansr = 0;
for (ll i = 1; i <= n; ++i) ansl ^= i * (ls[i] + 1), ansr ^= i * (rs[i] + 1);
cout << ansl << " " << ansr << endl;
return 0;
}
可以用二维 st 表做。
先将整张图压缩一下，每个点 \((i,j)\) 表示以它为左上角 \(C\times D\) 矩阵内的和。
然后定义 \(st_{i,j,k}\) 表示以 \((i,j)\) 为左端点，长度为 \(2^k\) 的条里的数的和。
定义 \(st2_{i,j,k}\) 表示以 \((i,j)\) 为左上角，由 \(2^k\) 个横条拼接而成的矩形的和。
st2 可以从 st 推出来。
对于横竖分别定义是为了防止 MLE。
最后只需要对于每个 \(A\times B\) 的矩阵求一下其内部最小的 \(C\times D\) 矩阵就行了。
复杂度 \(O(n^2\log n)\)。
模拟赛
40+30+20=90 rk26
标签：frac,log,limits,省选,sum,cdot,第五,计划,复杂度 From： https://www.cnblogs.com/HQJ2007/p/17561597.html