数据结构

分块

• [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, ... );
      ......
  }
  

  事实上应该将左右边界限制在块的范围内。

• 「LG P3863」序列

  其一：分块修改时，应该枚举完整个 \([lef, rig]\) 的区间，而不是只枚举 \([qL, qR]\) 内的数。这种情况主要出现在区间的元素被重排了的情况。

  其二：无论是分块还是线段树，一定要注意将交集为空的情况判掉!

堆

• [ARC097F]Monochrome Cat

  使用了俩优先队列的 " 可删堆 " ，结果在 push 和 erase 的时候都没有清除多余元素，于是堆中冗余元素就超多，结果 TLE 了：

  typedef priority_queue, greater > 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(); }
  }
  

  上面的“问题”已经破案了，真正的原因是数组开小了。

  但是谨慎起见，最好还是每次加入 maintain 一下。??

  额外提醒一点，惰性删除堆千万不要删除不存在的元素。

线性结构

• [CF817D]Imbalanced Array

  这道题用单调栈维护所有位置的最值的和的时候，细节很多。尤其注意的是，每个点管辖的区间实际上是从栈内的上一个元素开始的，也就是 \((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;
  

线段树

• 写了两棵线段树，大小不一致，并且查后继时如果没有后继则默认为 \(siz+1\)（但实际上应该是 \(+\infty\)）。这就导致了在较小的树上查后继的时候，得到了较小的范围，而在较大的树上查询时会查漏一些点。

  处理方法：注意大小关系，注意某些特殊值的取值（无穷大无穷小等），尤其是大小不一致时容易翻车。

• 笑麻了，这都 1202 年了，居然还可以写错线段树。

  具体来说，线段树区间修改，因为递归边界有锅，导致运行起来与暴力无异：

  void Update( const int x, const int l, const int r, const int segL, const int segR, const int delt )
  {
      if( segL > segR ) return ;
      if( l == r /*segL <= l && r <= segR*/ ) { Add( x, delt ); return ; } // 这里写错了
      int mid = ( l + r ) >> 1; Normalize( x );
      if( segL <= mid ) Update( x << 1, l, mid, segL, segR, delt );
      if( mid  < segR ) Update( x << 1 | 1, mid + 1, r, segL, segR, delt );
      Upt( x );
  }
  

平衡树

• [NOI2021] 密码箱

  第一次犯错：以为区间反转对应的端点可以直接算出来，结果需要用 kth() 来找；注意相对顺序会改变。

  第二次犯错：kth() 的时候没有下传标记。

  序列平衡树很久没碰过了 qwq ......

• 怎么又是平衡树：

  写非旋 Treap（或者其它任何结构）在结构变化的时候，一定要在结构确定下来后，更新维护的信息。

  例如，非旋 Treap 就需要在子树分裂完成和子树合并完成后及时更新信息。

并查集

• 带权并查集相关：

  例如 「LG P5787」二分图这道题，很多时候，带权并查集维护的是一棵生成树上，某个结点到根的信息。那么在连接 \((u,v)\) 这条边的时候，从 \(u\) 所在的根 \(r_u\)，到 \(v\) 所在的根 \(r_v\)，实际上是先到 \(u\)，再经过 \((u,v)\) 到 \(v\)，最后到 \(r_v\)，因此合并信息的时候，也应该按照这条路径来合并。

• 可撤销并查集相关：

  其一，断开从 \(u\) 到 \(v\) 的父子边的时候，\(u\) 的父亲应该还原成 \(u\) 而不是 0。

  其二，可撤销并查集不能写路径压缩，不能写路径压缩，不能写路径压缩！！！

标记问题

• 标记处理的问题：

  • 「JLOI2015」城池攻占

    注意：左偏树删除堆顶的时候，它的标记可能还没有下传。因此需要下传标记之后再合并左右子树。

    有的数据结构也是同样的。如果在删除的时候，被删除的节点对于其他节点的影响需要全部清除。

图论

生成树

• [AT4569]Connecting Cities

  使用 Boruvka 算法的时候，一定要注意，找出的是点，对应的是连通块，并查集维护的根与连通块的编号没有任何关系，千万不要用混了！

网络流

• 网络流的建图：

  「UOJ77」A+B Problem

  调了一个半小时，终于发现问题所在：竟然是反向边弄错了，最初 cnt 赋值为 0 而非 1 ！！！

  处理方法：单个变量不要忘记初始化！

• 「ABC214H」Collecting

  一定要注意，如果用 Dijkstra 跑费用流，那么每次最短路求完之后一定要修改势为当前最短路的结果。

  设在当前完成了最短路之后，结点 \(u\) 的最短路标号为 \(d_u\)，那么在一次增广后，原先图上的边 \((u,v,w)\) 仍然满足 \(d_v\le d_u+w\)。而如果当前边有流经过，反向边 \((v,u,-w)\) 被加入图中，那么 \((u,v,w)\) 必然在原图最短路上，也即 \(d_v=d_u+w\)，反过来也可以得到 \(d_u=d_v-w\)，所以此时 \(w'=w+d_v-d_u=0\)，仍然是非负的。

  最初的时候我们会跑一次最短路求出势，而这个势只是对于原图有效，增广后就不能再使用它了。由于原图上可能有一些特殊性质，因而我们可以用非 Bellman-Ford 类算法求出它，以获得较好的复杂度。

最短路

• 关于 SPFA 判断有无负环的注意事项：

  • SPFA 只能判断从起点出发能不能遇到负环。如果有一个负环不能从起点出发达到，这个负环就碰不到。

  • 一些简单的优化有极佳的效果，例如 dist[] 初值设置为 0 和 DFS 版 SPFA 在负环判断中表现良好。

二分图匹配

• 二分图匹配的匈牙利算法：

  枚举点搜索增广路的时候，理论上如果点已经匹配，那么再去搜索就是无效的，甚至可能导致错误。

  ......然而我没有判掉这种情况，甚至愉快地通过了 uoj 的模板题.....

• 二分图最大权匹配的 KM 算法：

  话说这个东西貌似也可以叫做匈牙利算法。

  如果某些点的 slack 还不够小，那么记得修改 slack 而不是让它保持原样。

  rep( i, 1, N ) if( ! visY[i] )
  {
      if( slk[i] > delt ) slk[i] -= delt;
      // REMEMBER to reduce slack due to change of labX !!!!!
      else { ... }
  }
  

树上操作

• 「SPOJ」Free Tour II

  分治过程中，如果在点上有信息或限制，并且运算不满足幂等性，那么应当保证分治重心的信息不会被重复统计，在“统计”和“存入”的时候需要注意是否应当计入分治重心。

• 一道重链剖分的题目，写错了两个地方：

  • 其一，居然把重链剖分写成了轻链剖分??，就一个符号写错了；

  • 其二，中途某个位置没有开 long long，一直没有检查到；

  处理方法：第一个问题属于写错了只会影响复杂度的类型，应该多测一下极限数据，什么样子的都应该测一下；第二个问题则应该检查每一个变量类型开得是否合理。

• 关于不同颜色计数的树上差分方式。

  如果按照 DFN 排序之后，某个颜色之前和之后都有颜色出现了，那么应该选择一个较低的 LCA 来删除多于贡献，而不应该在两个 LCA 上都删除一遍。

其它

• 判断（半）欧拉图、求欧拉（回）路一定要检查图是否连通！！！

• 在图上进行记忆化搜索的时候，如果没有搜索到需要的结果，那么也要声明某个状态已经被搜索过了，不能把状态留在那里等着其它起点再去找一遍，浪费时间。

数学

• Pollard Rho 模板 LGP4718

  注意，Pollard Rho 的原理是，假如 \(n=p\times q,p，那么我们随机生成一组数 \(x_1,x_2,\dots,x_k\) 之后，如果 存在 \(i,j,x_i\equiv x_j\pmod p,x_i\not\equiv x_j\pmod n\)，那么 \(\gcd(x_i-x_j,n)\) 一定会生成一个 \(n\) 的一个非平凡因子。

  因此，朴素做法是枚举环长，也即 \(j-i\)，并取 gcd；而加上 Floyd 判环法之后则是枚举 \(i\) 并检查 \(2i,i\) 两个元素。加上了倍增，其实也就是在倍增环长，因此需要每次和路径首个元素做差，而非和前一个元素做差。

  ---

  又把 Pollard Rho 写错一遍.jpg。

  错误一：对于迭代方程 \(x_{i+1}=x_i^2+c\)，其中初始值 \(x_0\) 和 \(c\) 都应该在范围 \([1,n-1]\) 中生成，否则在 \(n\) 非常小的时候会翻大车。

  比如，当 \(n=4\) 的时候，很容易直接陷入死循环。

  错误二：如果样本累积若干次后，变成了 0，就应该直接退出该次取样，而不能取 \(\gcd\) 之后以为找到了非平凡因子。

• 旋转卡壳模板 LGP1452

  注意，旋转的时候是寻找 \((i,i+1)\) 这条边的对踵点，因此假如为 \(j\)，那么应该检查 \(\operatorname{dist}(i,j)\) 和 \(\operatorname{dist}(i,j+1)\)。

  当然将四个点对全部检查一遍自然没什么问题

• 关于网格图上高斯消元的问题。

  设网格大小为 \(n\times m\)，且 \(n,m\) 同阶。这类问题一般有两种解决方案：

  • 带状矩阵高斯消元，本质上就是利用位置 hash 的性质偷了个懒，大大减少了所需扫描的范围。复杂度为 \(O(nm\times \min\{n,m\}^2)\)。

    但是这个方法在网格图消元之外比较危险。网格图上可以保证对角线上系数为 1，但是其它问题中就不一定了。如果出现了需要换行的情况就比较麻烦，不好好处理很容易直接破坏掉带性质；一般来说，如果需要换，那么我们会选择换列而非换行，这是因为如果某一列之下有超出带的范围的系数，我们可以在之后的消元中解决掉它。

  • 确定主元，这个相对来说适用性更广，效率更高，可以做到 \(O(n^3)\)，但是写起来较为复杂......

• 关于 BSGS 算法和扩展 BSGS 算法：

  一句话：求离散对数的时候一定要注意 \(p=1\) 和 \(b=1\) 的特殊情况！！！

• 数学真奇妙；没有交换律真奇妙。

  \(n\) 阶方阵群是一个典型的半群，这上面没有交换律。

  相应地，系数为 \(n\) 阶方阵的多项式群也是半群，这上面也没有交换律。

  在这上面进行多项式求逆的时候，传统步骤中的一步：

  \[(G_0-G)^2\equiv O\pmod {x^n} \]

  展开之后得到的就是：

  \[G_0^2-GG_0-G_0G+G^2\equiv O\pmod {x^n} \]

  没错！半群上没有交换律，完全平方公式失效了！！！

  由于 \(GG_0\) 和 \(G_0G\) 同时存在，这个方法已经走不下去了。可行的方法是从 \(G_0F-I\equiv O\pmod {x^{\lceil\frac n 2\rceil}}\) 出发：

  \[\begin{aligned} (G_0F-I)^2&\equiv O\\ G_0FG_0F-2G_0F+I^2&\equiv O\\ G_0FG_0-2G_0+G&\equiv O\pmod {x^n} \end{aligned} \]

  最后移项即可得到 \(G\)。又有一点需要注意，半群上 \(a^2b^2\not=(ab)^2\)，所以中途出现了 \(G_0FG_0F\) 这种东西。

• 关于高斯消元。

  之一：高斯-约旦消元的精度似乎比高斯消元的精度要高。但是据说如果高斯消元不处理精度误差那么就不会出现问题。

  之二：跟行列式不同，需要将单行的主元系数化一。

• 多校赛某题。

  \(n=10^{10}\) 的时候做杜教筛，预处理范围只有 \(10^6\)，导致杜教筛跑得非常慢......

  处理方法：熟悉时间复杂度原理，杜教筛需要预筛到 \(n^{\frac{2}{3}}\) 才可以。

思考的漏洞

• [AGC034C] Tests

  发呆想了半天才发现枚举的那一天可以放在钦定的前 \(k\) 个里面。

  处理方法：思路一定要全，分清问题的主从关系。

• 「IOI2021」地牢游戏

  注意一点，当 \(t> \max \{\lfloor\log_2 s\rfloor\}\) 的时候，此时倍增长度不再由 \(\log_2 s\) 决定，而是由 \(\log_2 n\) 决定。注意边界的细节。

• 「POJ3304」Segments

  注意当直线的方向向量为 \(\vec 0\) 的时候，这样的直线一般来说需要特判。

其它

• [AGC002D] Stamp Rally

  关于整体二分的写法问题。

  这里由于我们不能简单地修改要求，所以在进入右区间的时候，我们必须保证左区间的边已经被加入。

  如果写法是在离开区间时删除新加入的边，且在进入右区间之前将所有的左边的边加入，那么没有问题。

  但是如果写法是在叶子的位置加入边，并且之后不删除，那么就必须保证叶子可以到达（现在外层相当于是遍历线段树的过程）。因此如果：

  void Divide( const int qL, const int qR, const int vL, const int vR ){	if( vL > vR || qL > qR ) return ;    ...}
  

  那么就有问题（因为很有可能询问区间为空就返回，没有到叶子节点）。

• 后缀数组模板。

  注意中间的“桶”数组大小与字符串长度相同，而非与字符集大小相同！

  const int MAXN = 1e6 + 5, MAXC = 300;int buc[MAXN]; // 注意不是 MAXC
  

• DP 的转移：

  比较下面的两种转移写法：

  #define rep( i, a, b ) for( int i = (a) ; i <= (b) ; i ++ )
  #define per( i, a, b ) for( int i = (a) ; i >= (b) ; i -- )
  
  int h[][];
  //other codes omitted.
  
  per( p, N, 0 ) per( q, N + 1, 0 ) {        
  	int tmp = 0;        
      for( int k = 0, up = 1 ; i * k <= p && j * k <= q ; k ++ )                
          Upt( tmp, Mul( h[p - i * k][q - j * k], Mul( ifac[k], up ) ) ),        
      	up = Mul( up, Add( g[i][j], k ) );        
      h[p][q] = tmp;
  }
  

  #define rep( i, a, b ) for( int i = (a) ; i <= (b) ; i ++ )
  #define per( i, a, b ) for( int i = (a) ; i >= (b) ; i -- )
  
  int h[][];
  //other codes omitted.
  
  for( int k = 1, up = 1 ; i * k <= N && j * k <= N + 1 ; k ++ ) {	    
      up = Mul( up, Add( g[i][j], k - 1 ) );	    
      for( int p = N - i * k ; ~ p ; p -- )		        
          for( int q = N + 1 - j * k ; ~ q ; q -- )			            
              Upt( h[p + i * k][q + j * k], Mul( Mul( ifac[k], up ), h[p][q] ) );
  }
  

  如果要求用 g[i][j] 将所有 k 都转移一遍之后，h[][] 才能发生变动，那么第二种写法就有问题。这是因为，转移过程中较小的 k 会对较大的 k 造成影响，相当于是按照 k 划分而不是按照 g[i][j] 划分。

  总而言之，明确 DP 过程的阶段，同时找出合适的写法。

• 二分的结果：

  如果在二分过程中计算方案，那么最终二分出来的答案是 l 而不是上一次代入的参数。因此，输出方案之前需要重新构造一遍！！！

• 关于 WQS 二分。

  我们二分的是切凸包的斜率。如果目标位置被共线的边卡住了，那么我们只能二分出正确的斜率，而多半不能找到正确的切点。但是我们只需要知道截距和斜率就可以算出答案，所以此时的答案不是切点的结果，而是目标位置在该斜率下的结果。