# 搜索和基础套路
## 搜索
- A\*/IDA\*
- IDDFS的重要问题是每层搜索量大，因此使用类似A\*的启发式方法找到剪枝策略（往往是深度相关的）
- 而A\*主要解决搜索路径上的启发式优先级问题，可以是在DFS里根据分支情况的优劣先选择较优分支，也可以是在BFS里把普通队列换成优先队列。
- 双向BFS
```cpp
int st[2], ed[2];
int step1[N][N];
int step2[N][N];
// 先特判起终点一致的情况
if (st[0] == ed[0] && st[1] == ed[1]) {
// ...
}
// 然后初始化队列
queue<node> q1, q2;
step1[st[0]][st[1]] = 0;
q1.push(node(st[0], st[1]));
step2[ed[0]][ed[1]] = 0;
q2.push(node(ed[0], ed[1]));
int result = -1;
while(result == -1 && (!q1.empty() || !q2.empty())) {
if (!q1.empty()) {
// q1上带有step1和step2碰撞检测的一步BFS，以result为结束...
}
if (result != -1) break;
if (!q2.empty()) {
// q2上带有step1和step2碰撞检测的一步BFS，以result为结束...
}
}
```
## 分块
类似线段树的思想，但是更简单暴力，可以仅有单层
对于区间$[a,b]$，将其分成$n$块，前$n-1$块每块 $\lfloor\frac{b-a}{n}\rfloor$ 个元素，第$n$块 $\left(n-n\cdot\lfloor\frac{b-a}{n}\rfloor\right)$ 个元素。
每个块都有任务特定的块记录$S_i$和$U_i$，记录块全局状态$S_i$，并以lazy形式记录和处理块全局更新$U_i$，如：
- 查询区间和
- $S_i$维护区间和
- 左右不完全区间暴力遍历求和，中间完全区间直接使用$S_i$
- 区间每个数都加x
- $U_i$维护区间更新
- 左右不完全区间暴力加，中间完全区间直接给$U_i$上记录
- 注意不完全区间出现时，计算前可能要先把其所在完全区间的$U_i$记录进行pushdown（去掉lazy）；对于特定任务，如$U_i$和实际值的性质具有平行性，则可以使用永久标记而非懒标记。
- 加法是典型的具有平行性的例子，因此可以直接带着$U_i$计算所有东西而无需下放。
- 区间每个数都变成x
- $U_i$维护区间统一新值，若没有则可以置inf
- 这个是典型的需要pushdown的例子
- 查询区间中大于x小于y的数个数
- $S_i$维护该区间的排序后副本
- 左右不完全区间暴力计数
- 中间完全区间使用$S_i$进行二分查找统计
![]()