Trick小计
数论
筛法
- 埃氏筛复杂度 \(O(nloglogn)\)。奇快无比。
容斥原理
- minmax容斥同时适用于期望。
2. 容斥原理的逆向使用，将容斥形式的式子转化为判断属性的式子
3. 如果大力讨论的难度较小。可以试试容斥。
思路技巧
- 不行就随机化。
- 对于两个数之积为完全平方数的条件，考虑分解成 \(n^2p\) 的形式
- 对于期望的平方的题目，考虑拆成两个互相独立的。或者二项式定理乱搞？？？
- 斐波拉契数列的整体偏移和线段树之间的关系
数据结构
区间数颜色问题
题目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)\)
图论
- 答案是寄
- tarjan，每一个强连通分量的编号就是它的拓扑逆序
谔谔！
- 解的唯一性 ： 令 \(a,b\) 均为解，由一系列变化得 \(a=b\)。而不用证明充分性和必要性。
- 贪心和拟阵。
- 差分数组 与 原数组一一对应。差分对于具有可加性和可减性的运算均有效。
DP
- 求满足xx条件的排列数量时，可以考虑依次插入。
- 注意差分对应转移的关系
树上问题
- 离线常见思路就是把询问挂在点上，选择自下而上或者自上而下进行转移。
- 连通块个数 点数-边数。树上的连通块是个森林！！！
- 对于一类 \(k\) 距离的题目，考虑转化为rmq问题
- 换根和dfn序之间的关系！！！！！
- 考虑树分块的常见形式。边分块//点分块
- trie带个log！！！！！！！！！！！（虽然不知道应不应该放在树上问题这里）