数论
筛法
- 埃氏筛复杂度 $O(nloglogn)$。奇快无比。
容斥原理
- minmax容斥同时适用于期望。
2. 容斥原理的逆向使用，将容斥形式的式子转化为判断属性的式子
3. 如果大力讨论的难度较小。可以试试容斥。
思路技巧
- 不行就随机化。
数据结构
区间数颜色问题
题目1：
给定长度为 $n$ 的序列，每个点有颜色 $c_i$ ，有 $q$ 次询问，询问区间 $[l_i,r_i]$ 的不同颜色数。
解法1：
莫队 $O(q\sqrt{n})$
#### 解法2：
定义序列 $b$ , $b_i$ 表示值与 $c_i$ 相同的前驱位置。
于是实际上询问区间内有多少个 $b_i\leq l_i$ 。
转化为二维数点问题即可。
根据题目要求选择数据结构。在线则可持久化。
题目2 : 给定长度为 $n$ 的序列，每个点有颜色 $c_i$ ，有 $q$ 次询问，询问区间 $[l_i,r_i]$ 的不同颜色数。带修。
解法1：
莫队 $O(qn^{\frac{3}{2}})$
解法2（离线）：
同问题一解法二。此时点改为 $(i,b_i,t_i)$。三维数点问题，离线算法套数据结构即可
解法3 （在线）：
此时同问题1解法2，维护二维点对。需要数据结构，支持在线加点，在线删点，区间统计。
稀疏二维线段树，$O(nlog^2n)$
题目3：
给定一个 $n$ 个节点的树，每个点有个颜色，求每个点的子树有多少不同颜色
解法1：
把树扒成序列，然后乱搞 $O(nlogn)$
解法2：
DSU on tree。$O(nlogn)$
题目4：
给定一个 $n$ 个节点的树，每个点有颜色。询问 $u,v$ 路径上有多少种颜色，带修。
解法1：
树上莫队，记得特判起点和lca
解法2：
边分治，太暴力了不解释。
题目5：
给定一个 $n$ 个节点的树，每个点有颜色。询问 $u$ 子树种与 $u$ 距离不超过 $d$ 的点的颜色数。
解法：
我太弱了，只会离线。
对于每个节点维护一颗线段树，记录子树内每个颜色出现的最浅深度。
再对全局开一颗树状数组，下标为深度，权值为种类数
当进入某节点时，查询该节点所有询问，即子树外对答案的影响
当即将离开某节点时，再次查询，将本次查询值减去上次查询值即为ans
至于线段树，线段树合并即可
题目6：
给定一个长度 $n$ 的序列和定值 $k$。定义 $f$ 为该序列覆盖了颜色 $[1,k]$ 的子区间数量。有两种操作，将某点修改为0，或询问此时 $f$ 值
解法：
定义 $R$ 序列，$R_i$ 表示满足条件的最左坐标，且 $R_i>i$。
显然该函数为递增函数，可以线性预处理。
则有 $f=\sum(n-R_i+1)$
考虑修改。定义与 $a_i$ 相同颜色的前驱后继为 $pre_i,suc_i$。
删除某点的操作为对 $R\in[pre_i,i]$ 进行 chkmax $suc_i$
SegBeat（无脑大复杂度）！或者线段树二分。
题目7：
给定 $n\times m$ 的矩阵。某 $k$ 个点被着色了，求所有包含了所有颜色的子矩阵个数。$(1\leq n,m \leq 10^9,1\leq k \leq 2000)$
解法
二维问题。不会。
只能扫描线扫掉两维。然后统计答案。
考虑枚举上下边界，我们可以 $O(k)$ 统计答案。
假定现在上下边界已经确定。考虑设函数 $R(x)$ 表示以 $x$ 为左端点时，最近的右端点。$Ans=\sum(n-R_i+1)$
可随着上下两端的移动，答案的变化量很大,没什么单调性。看起来只能 $O(k^3)$？
考虑回滚思想，让下端点单调上移。此时问题变成题目6的删点问题。
时间复杂度 $O(k^2logk)$
图论
- 答案是寄
2. tarjan，每一个强连通分量的编号就是它的拓扑逆序
谔谔！
- 解的唯一性 ： 令 $a,b$ 均为解，由一系列变化得 $a=b$。而不用证明充分性和必要性。
2. 贪心和拟阵。