fun facts about sequences

Posted on Edited on In

  1. 一个和为\(0\)的随机序列\(\{a_n\}\), \(E(\max_i(\sum_{j\le i}a_j))=O(\sqrt N)\). 常用于DP, 通过随机化降低时间.

  2. 任意一个序列, 其中满足\(\max(A[l,r])\gt \max(A[l',r']),[l,r]\subsetneq [l',r']\)的极大子段个数是\(O(n)\)的. 求法: 单调栈

  3. 对于一个排列, 对逆序对连边, 形成的连通块一定是区间.

  4. 一个在\([0,1]\)之间随机的实数序列, 长为\(n\), 则第k小数的期望 \(=\frac k {n+1}\).