CDQ分治
CDQ
使用cdq分治的条件：
修改操作对询问的贡献独立，修改操作相互不影响 题目可以使用离线算法，不必强制在线（询问次数可以保存在数组）
cdq分治的性质：
cdq分治通过对时间复杂度增加一个log来降维 cdq可以用来代替复杂的数据结构 在cdq分治中，对于划分出来的两个区间，前一个子问题需要用来解决后一个子问题。
cdq使用步骤：
将整个操作序列分为两个长度相等的部分。 递归处理前一部分的子问题（治1） 计算前一部分子问题的修改操作对后一部分子问题的影响（治2） 递归处理后一部分的子问题（治3）
离线，处理点对关系，常用于降维度，归并排序（合并左右区间，逐级向上）：
12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include<bits/stdc++.h>using namespace std; int temp[500005],a[500005],n;long long ans;inline int read(){ int x ...
【数据结构2-2】线段树与树状数组 题解
头一次老老实实写完一个官方题单，发篇题解纪念一下。
@[TOC]
P3372 【模板】线段树 1令人惆怅，第一个模板题就有延迟标记。
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788#include<bits/stdc++.h>using namespace std;int n,m,a[100010];struct segment_tree{ int l,r; long long sum,add;}tree[100010*4];void build(int p,int l,int r){ tree[p].l=l,tree[p].r=r; //cout<<"p:"<<p<<" l:"< ...
Soduku
166. 数独
显然要用到DFS，对于每个未填的空格，要排除掉同行同列同九宫内出现过的数字。不加优化不出意外的话会T飞︿(￣︶￣)︿。
考虑剪枝：
优化搜索顺序
排除冗余信息
可行性剪枝（照当前分支这样走后面不可能达成）
最优性剪枝（照当前分支这样走的最优解都比当前解差）
记忆化搜索
这里我们主要考虑优化搜索顺序。这其实是跟大家做数独的时候的朴素感知是一样的，从可选的数少的空格开始试探。所以我们在每次搜索时都判断一下哪个格子的可选到数最小（可以预先处理出来可能会用到的所有二进制数里1的个数，用时直接调用）。
记录每个格子可选的数，可以用二进制状态压缩，开九位表示九个数。为了方便，我们把1~9映射成0 ~8。开三个数组$row[N],col[N],cell[N/3][N/3]$分别记录每行、每列、每个九宫格内有哪些数不能填。对于位置在$(x,y)$的数，用 row[x] & col[y] & cell[x/3][y/3] 可以查到该空格可以填哪些数，那就老老实实搜索这些数吧233，可以用lowbit获得二进制下为1的每一位，将其转化成十进制数（1的位置对应的位数，可 ...