如题所述，专门记录自己在各类考试、做题中出现的花式错误。
算法思想
-
分块相关算法写挂的：
-
[Ynoi2019模拟赛] Yuno loves sqrt technology II
写莫队发现自己没有排序，T 飞了。大致可以描述为：
void Init() { //对 Q 数组进行排序 } int main() { Init(); ...... //读入 Q return 0; }处理方式：一定要将数据读入完之后再预处理 。
-
题目见上。
写分块的时候对边角块处理不当......void UpdateBlock( int id, int l, int r, ... ); //块内处理 void UpdateAll( int L, int R ); //全局处理 { if( 左边有边角块 ) UpdateBlock( 块编号, L, R, ... ); ...... }事实上应该将左右边界限制在块的范围内。
-
-
数据结构写挂的：
-
使用了俩优先队列的 " 可删堆 " ，结果在
push和erase的时候都没有清除多余元素，于是堆中冗余元素就超多，结果 TLE 了：typedef priority_queue<int, vector<int>, greater<int> > Heap; struct RHeap { Heap q, rub; void Push( const int v ) { q.push( v )/*这里需要 Maintain 一下*/; } void Erase( const int v ) { rub.push( v )/*这里需要 Maintain 一下*/; } int Size() { Maintain(); return q.size() - rub.size(); } int Top() { Maintain(); return q.empty() ? 0 : q.top(); } RHeap() { while( ! q.empty() ) q.pop(); while( ! rub.empty() ) rub.pop(); } void Maintain() { while( ! q.empty() && ! rub.empty() && q.top() == rub.top() ) q.pop(), rub.pop(); } } -
这道题用单调栈维护所有位置的最值的和的时候，细节很多。尤其注意的是，每个点管辖的区间实际上是从栈内的上一个元素开始的，也就是 \((stk_{i-1},i]\) ，而不能将自己作为自己那一段的终点。请参考以下这段代码：
while( top1 && a[stk1[top1]] > a[i] ) mn -= 1ll * ( a[stk1[top1]] - a[stk1[top1 - 1]] ) * ( i - stk1[top1 - 1] - 1 ), top1 --; // 这里不能写 i-stk[top1] ，不然就会少算一些位置 mn += 1ll * ( a[i] - a[stk1[top1]] ) * ( i - stk1[top1] - 1 ) + a[i], stk1[++ top1] = i;
-
-
图论算法写挂的：
-
使用 Boruvka 算法的时候，一定要注意，找出的是点，对应的是连通块，并查集维护的根与连通块的编号没有任何关系，千万不要用混了！
-
-
思考不全面的：
-
发呆想了半天才发现枚举的那一天可以放在钦定的前 \(k\) 个里面。
处理方法：思路一定要全，分清问题的主从关系。
-
-
其它算法各种乱七八糟铁锅乱炖导致写挂的：
-
关于整体二分的写法问题。
这里由于我们不能简单地修改要求，所以在进入右区间的时候，我们必须保证左区间的边已经被加入。
如果写法是在离开区间时删除新加入的边，且在进入右区间之前将所有的左边的边加入，那么没有问题。
但是如果写法是在叶子的位置加入边，并且之后不删除，那么就必须保证叶子可以到达（现在外层相当于是遍历线段树的过程）。因此如果：
void Divide( const int qL, const int qR, const int vL, const int vR ){ if( vL > vR || qL > qR ) return ; ...}那么就有问题（因为很有可能询问区间为空就返回，没有到叶子节点）。
-
实现细节
-
编译过程出错的：
-
由于
g++的版本与现行版本不一致，库的包含关系就不完全相同。这个时候如果缺少头文件也有可能会本地通过编译，但是提交后可能会 CE。典型例子就是
Dev-C++上cmath还包含在algorithm里面。如果仅包含algorithm并且使用cmath内部的函数，在新版的g++下编译就会报错。 -
经典的“隐形”库函数
x1(),y1(),j0(),j1()，这几个小混蛋都在cmath里面。问题是，它们几乎找不到踪迹。如果去 C++ reference 里面查你根本找不到它们。
如果在 Windows 环境下使用 9.3.0 版本的
g++编译也不会检查出问题，但是，但是，一旦包含cmath并且自定义了重名的变量/函数，那么在Linux环境下编译的时候才会 CE。
-