前言
快省选了，在复习，但是不知道干什么。
所以就写点东西吧。
就是瞎写写，所以可能有很多错误，如果发现了欢迎指出。
常见错误 & 注意事项
-
数组不能开大，也不能开小
-
题目要求什么千万不能读错，最好手算一下样例
算法复习
树状数组进阶
原本是树状数组二分的模板题，但是用树状数组 + 二分水过去了。
其实就是要求冰火两方消耗能量较少的 2 倍，所以要让这个最小值最大。
发现其实冰系战士消耗的能量关于温度是一个上升的斜线（本质上是一个前缀和），火系下降（本质上是一个后缀和）。
所以它们的最小值最大应该是在交点处。但线不连续，所以要找两个位置，一个是最后一个 \(sf_i\geq sc_i\) 的位置，一个是第一个 \(sc_i>sf_i\) 的位置，很显然的二分。带修所以树状数组维护前缀和。
这样二分是在整个树状数组上的，根据树状数组的结构可以用类似倍增的方式 \(O(\log n)\) 过去。而不需要 \(O(\log ^2 n)\) 的树状数组 + 二分
树状数组二分可以抽象成这样一类问题：存在分割点 \(q\)，使得 \(\leq q\) 的位置满足某个限制，而 \(> q\) 的位置不满足该限制，求 \(q\)。
从大到小考虑 \(1\leq 2^k \leq n\)，每次尝试将 \(p\) 加上 \(2^k\)，由于从大到小枚举，根据树状数组的结构，\(c_{p+2^k}\) 存的值即为 \(\sum_{i=p+1}^{p+2^k} a_i\)，所以直接加上这个值判断一下，若满足就 \(p\leftarrow p+2^k,s\leftarrow s+c_{p+2^k}\)，否则不动，然后继续枚举。其实就是一个倍增。
但是树状数组二分只适用于在整个树状数组上二分，如果是局部，就没办法利用树状数组的结构了。所以还是需要树状数组 + 二分
整体二分 + 树状数组二分
似乎并不需要树状数组二分。
这题主要难在结论的推导，推出性质之后似乎就是一个简单的离线维护了。
二维树状数组的模板。
二维树状数组维护二维前缀和。
设 \((i,j)\) 差分数组为 \(d_{i,j}\),\(s_{i,j}\) 表示 \((i,j)\) 的二维前缀和
\[s_{x,y}=\sum_{i=1}^x \sum_{j=1}^y a_{i,j} \]\[=\sum_{i=1}^x \sum_{j=1}^y \sum_{k=1}^i \sum_{l=1}^j d_{k,l} \]\[=\sum_{i=1}^x \sum_{j=1}^y d_{i,j} \cdot (x-i+1)\cdot(y-j+1) \]\[=\sum_{i=1}^x \sum_{j=1}^y d_{i,j} (xy-xj+x-yi+ij-i+y-j+1) \]\[=\sum_{i=1}^x \sum_{j=1}^y d_{i,j} [(xy+x+y+1)-i(y+1)-j(x+1)+ij] \]所以维护 \(d_{i,j},d_{i,j} \cdot i,d_{i,j} \cdot j,d_{i,j}\cdot ij\) 四个二维树状数组就可以了。。
放一个二维树状数组的代码
struct BIT{
int s[maxn][maxn];
void add(int x,int y,int z){
for(int i=x;i<=n;i+=lowbit(i))
for(int j=y;j<=m;j+=lowbit(j)) s[i][j]+=z;
return ;
}
int ask(int x,int y){
int res=0;
for(int i=x;i;i-=lowbit(i))
for(int j=y;j;j-=lowbit(j)) res+=s[i][j];
return res;
}
};
根号分治
就是利用根号平衡的思想，对于不同的数据用不同的维护方法。本质是数据分治
咕
莫队
莫队板题。首先把区间异或和转为两个异或前缀和的异或，然后维护一个区间内异或前缀和值 为 \(i\) 的数个数。
莫队 + 值域分块
发现对于一些没法 \(O(1)\) 插入删除的东西，如果使用 \(\log\) 数据结构，整体复杂度就变为了 \(O(n\sqrt n \log n)\)，无法接受。
但是其实对于所有询问，修改操作有 \(n \sqrt n\) 次，但是询问操作只有 \(n\) 次，所以我们考虑继续运用根号平衡的思想，找一些 \(O(1)\) 修改，\(O(\sqrt n)\) 查询的方式，即值域分块。
但是有的时候我们有不同的需求，比如有时候二次离线需要 \(O(\sqrt n)\) 修改，\(O(1)\) 查询，此时换一种值域分块的方式，见 P5501 的二离部分，要注意区分。
有的时候我们没有办法 \(O(1)\) 实现插入删除，也没法值域分块（比如每次插入删除会考虑一个点对一个区间的贡献），所以我们需要把这些点对区间的贡献的询问离线下来再做，即莫队二次离线。
每一次端点移动可以看为一堆点对于一些区间的贡献，一般来说这种东西具有可减性。
记 \(f(i,[l,r])\) 表示点 \(i\) 对 \([l,r]\) 的贡献，假设某次移动右端点由 \(r\) 移动到 \(r'\)，贡献为
\[\sum_{i=r+1}^{r'} f(i,[l,i-1])=f(i,[1,i-1])-f(i,[1,l-1]) \]前半部分东西可以扫一遍预处理，对于后半部分，看成一段区间对一段前缀的贡献。
考虑将 \(g([r+1,r'],[1,l-1])\) 挂到 \(l-1\) 上，然后再从前往后扫加入每个点，然后暴力回答挂在这个点上的询问，由于莫队端点移动的总长度是 \(O(n\sqrt n)\) 所以可以接受。
P5501 中二次离线部分依然不能 \(O(1)\) 处理，此时发现添加点（即修改操作）是 \(n\) 次，查询是 \(O(n\sqrt n)\) 次，此时我们需要修改根号，查询 \(O(1)\) 的数据结构。
注意：
-
贡献的符号
-
有时候要注意贡献的含义，比如逆序对，是查区间内比某个数大还是比某个数小。
有的时候我们维护的信息不支持删除，比如最大值最小值，这个时候需要一种不用删除的莫队，即回滚莫队。
回滚莫队的思想是，把左端点在一个块内的询问按右端点从左到右排序（所以不能奇偶排序优化了，悲），每次把左端点放在块尾，然后向右移动右端点，遇到询问就暴力左移左端点，询问完后再撤回，把左端点放回块尾。
看上去很暴力，但是复杂度是对的。
较为复杂的莫队。
咕