科技/套路/总结

目录

• 组合/概率期望
  • 容斥
  • 期望
  • 数列
    • 斯特林数
    • 阶乘/组合数
  • 反演
  • 偏序集
  • 杂
  • 计数
    • 图
      • DAG
• 多项式/生成函数/形式幂级数
• 动态规划
  • 树形DP
  • DP优化
    • 斜率优化
    • 决策单调性
    • 四边形不等式
    • 凸优化
    • 杂
  • 杂
• 贪心
• 数据结构
  • 线段树
    • 线段树合并/分裂
    • 线段树区间最值操作
    • 均摊分析
  • 全局平衡二叉树
  • 重链剖分
  • 长链剖分
  • 树相关
  • 分块
  • CDQ分治/整体二分
• 二分图/网络流/费用流
  • 经典模型
• 字符串
  • KMP
  • AC自动机
  • 后缀数组
  • 后缀树
  • 后缀自动机
  • 后缀平衡树
  • 子串
  • 回文自动机
  • 杂题
• 图论
  • 强连通分量
  • 优化建图
  • 杂
• 数论
  • 同余方程与二次剩余
  • 模意义下的环
  • GCD和LCM
  • 杜教筛
• 博弈
• 线性代数
  • 矩阵树定理
  • 消元
  • 线性基
  • 综合
• 数值计算
• Reference

大多都从reference里搬来的

组合/概率期望

容斥

• 基本的容斥
  \(\sum\limits_{i = 0}^k \binom{k}{i} (-1)^i = [k = 0]\)
  \(\sum\limits_{i = 1}^k \binom{k}{i} (-1)^{i - 1} = [k > 0]\)

• 对双射方案的容斥
  uoj#185. 【ZJOI2016】小星星

• 每次在剩下的物品中选一种拿走一个，求拿走的最后一个物品是第一种物品的概率的问题
  loj#2541. 「PKUWC2018」猎人杀
  uoj#390. 【UNR #3】百鸽笼

• min-max容斥
  \(min(S) = \sum\limits_{T \subseteq S \land T \neq \varnothing} (-1)^{|T| - 1} max(T)\)
  \(max(S) = \sum\limits_{T \subseteq S \land T \neq \varnothing} (-1)^{|T| - 1} min(T)\)
  期望下也是对的
  \(kthmax(S) = \sum\limits_{T\subseteq S \land T \neq \varnothing}{\binom{|T| - 1}{k - 1}} (-1)^{|T| - k} min(T)\)
  用二项式反演即可证明
  同理期望下也是对的

可应用于求LCM
\(lcm(S) = \prod\limits_{T\subseteq S \land T \neq \varnothing} \gcd(T)^{(-1)^{|T| - 1}}\)

期望

概率期望相关

• 图上随机游走
  HNOI2013游走
  JSOI2009有趣的游戏
  SDOI2017硬币游戏
  ZJOI2019开关

数列

• 数列求解的一些思路

• 求解斐波那契数列模p意义下最短循环节

斯特林数

Bandit Blues

阶乘/组合数

一般在模意义下

求阶乘当然可以\(O(n)-O(1)\)了，也可以分段打表
\(O(\sqrt{n} \log n)\) 阶乘模大质数

求单个组合数，展开后变成求阶乘，取决于求阶乘的复杂度

若是上指标求和，有恒等式\(\sum\limits_{i = 0}^n \binom{i}{m} = \binom{n + 1}{m + 1}\)，变成了求单个组合数
若是下指标求和，如果是单个询问，有\(O(\sqrt{n} \log n)\)或\(O(\sqrt{m} \log m)\)的优秀做法loj #6386. 组合数前缀和；如果是多组询问，可以考虑莫队，设\((n, m) = \sum\limits_{i = 0}^m \binom{n}{i}\)，可以\(O(1)\)转移到\((n, m - 1), (n, m + 1), (n - 1, m), (n + 1, m)\)，就可以\(O(n \sqrt{q})\)了

反演

• 二项式反演
  \(f(n) = \sum\limits_{i = 0}^{n} (-1)^{i}\binom{n}{i}g(i) \Leftrightarrow g(n) = \sum\limits_{i = 0}^{n} (-1)^{i} \binom{n}{i}f(i)\)
  \(f(n) = \sum\limits_{i = 0}^{n}\binom{n}{i}g(i) \Leftrightarrow g(n) = \sum\limits_{i = 0}^{n} (-1)^{n - i} \binom{n}{i} f(i)\)
  均可用生成函数证明（乘上\(e^x\)和\(e^{-x}\)）

• 单位根反演
  Loj #6358. 前夕

偏序集

反链是一种偏序集，其任意两个元素不可比；而链则是一种任意两个元素可比的偏序集

• Dilworth定理
  在有穷偏序集中，任何反链最大元素数目等于任何将集合到链的划分中链的最小数目（也即DAG点和边可交的最小链覆盖）
  loj#6197. 法克

• 偏序集最小反链覆盖等于最长链
  设\(f_i\)为链尾为元素\(i\)的最长链，那么只需将\(f_i\)相同的元素放在一个集合内，显然同一个集合内不会有包含关系
  luogu P4934 礼物

杂

• 求第\(k\)个符合条件的序列
  逐位确定
  逆序对为m,字典序第k小的排列
  字典序第k小的错排2018 BACS Contest Replay Problem H-Little T2 and Derangements

• 隔线法统计合法方案
  合法括号序列方案
  你有\(a\)个\(+1\)，\(b\)个\(-1\)，把它们排成一个序列，要使得任意的前缀和都大于或等于\(-c(0 \le c \le b)\)，求合法排列数
  特殊情况当\(a = b, c = 0\)时就是合法的括号序列
  当\(b - a > c\)时，方案为\(0\)，否则方案为\(\binom{a + b}{a} - \binom{a + b}{b - c - 1}\)
  JLOI2015 骗我呢
  Code+#3 博弈论与概率统计

常用数列/公式/定理

计数

图

• 有标号简单连通无向图的个数 bzoj3456 城市规划 Solution

DAG

https://blog.csdn.net/u014609452/article/details/56771436
bzoj3812 主旋律 Solution

多项式/生成函数/形式幂级数

• 多项式算法汇总

• \(exp(x) = \sum\limits_{i = 0}^{\infty} \frac{x^i}{i!}\)
  \(ln(1 - x) = - \sum\limits_{i = 1}^{\infty} \frac{x^i}{i}\)

• 如果要把多项式的指数模\(k\)相同的项系数加起来放在一起，可以把该多项式模\(x^k - 1\)
  luogu 5224 Candies

• 长度为\(n\)的序列逆序对数的生成函数\(\frac{\prod\limits_{i = 1}^n (x^i - 1)}{(1 - x)^n} = \frac{exp(\sum\limits_{i = 1}^{\infty} (\sum\limits_{j = 1}^n [j | i] \frac{j}{i}) x^i)}{(1 - x)^n}\)
  2017 山东一轮集训 Day7 逆序对

• 特殊多项式在整点上的线性插值方法
  The Sum of the k-th Powers

• \(\sum\limits_{i = 1}^n \prod\limits_{i \neq j} (x + a_j) = (\prod\limits_{i = 1}^n (x + a_i))'\)

• 有\(a_i, b_i(1 \le i \le n)\)，求\(f_i(1 \le i \le m)\)满足\(f_k = \sum\limits_{i = 1}^n b_i {a_i}^k\)
  令\(F(x) = \sum\limits_{k = 0}^{\infty} f_k x^k = \sum\limits_{k = 0}^{\infty} \sum\limits_{i = 1}^n b_i {a_i}^k x^k= \sum\limits_{i = 1}^n b_i \sum\limits_{k = 0}^{\infty} (a_j x)^k = \sum\limits_{i = 1}^n \frac{b_i}{1 - a_i x} = \frac{\sum\limits_{i = 1}^n b_i \prod\limits_{i \neq j} (1 - a_j x)}{\prod\limits_{i = 1}^n (1 - a_i x)}\)
  分子和分母都可以分治FFT

• 浅谈 OI 中常用的一些生成函数运算的合法与正确性

动态规划

树形DP

• 一类每个点状态数为子树大小与定值\(k\)的最小值的树形DP
  \(f_{i,j}\)为以\(i\)为根的子树，选出来的点数为\(j\)时的方案数/贡献，这里\(j \le k\)
  转移时要枚举两边各选了多少点，直接做是\(O(n k^2)\)的
  注意到当选的点数$ \le size\(时才有意义，这样转移时两棵子树选的点数可以只枚举到\)\min(size, k)\(，这样就是\)O(n k)$的了
  证明：

1. 两棵子树大小都\(> k\)，只有\(O(\frac{n}{k})\)次转移，复杂度为\(O(\frac{n}{k} \times k^2) = O(n k)\)
2. 一棵子树大小\(le k\)，另一颗子树大小$ > k\(，合并以后的子树大小就\)> k\(了，显然每个点最多被这样转移一次，复杂度为\)O(n k)$
3. 两棵子树大小都\(\le k\)，考虑每个点的贡献，每个点的贡献为最后一次都是\(\le k\)的合并后子树大小，\(\le 2k\)，所以复杂度为\(O(n k)\)
   Hello 2019 G. Vladislav and a Great Legend

DP优化

斜率优化

决策单调性

四边形不等式

动态规划加速原理之四边形不等式
https://blog.csdn.net/noiau/article/details/72514812
https://blog.csdn.net/qq_41695941/article/details/83025188

凸优化

经常与斜率优化结合

• luogu P4072 [SDOI2016]征途

杂

• 记\(l_i, r_i]\)为\(i \in g(k?1)\)可以转移到的\(g(k)\)中的区间（或者能转移到\(g(k)\)的区间）。要求任意两个\([l_i, r_i], [l_j, r_j]\)不互相严格包含。（这里严格包含指的是包含且左端点不同且右端点不同）
  我们可以把\(g(k)\)切成若干个区间，满足\([l_i, r_i]\)不被任意一个区间严格包含，且\([l_i, r_i]\)最多与两个区间相交。
  方法如下：对于一个区间的左端点，找到最右的右端点使得这个区间不严格包含任何\([l_i, r_i]\)。可以证明，这个方法满足条件。
  这样，一个\([l_i, r_i]\)一定是一个区间的前缀或后缀，分两部分DP一下就好了。DP过程类似决策单调性优化DP。
  copy from yww

杂

• Codeforces Round #313 (Div. 1) Problem E. Gerald and Path

• 2017 山东一轮集训 Day7 逆序对

• Slope Trick
  维护函数图像
  Tutorial
  Sonya and Problem Wihtout a Legend
  APIO2016烟火表演
  2019省选联合训练9 T3 桥（bridge）

• DP值比状态小的最优化DP
  一道 DP 思路好题

贪心

• 一类打怪
  bzoj3709 [PA2014 ]Bohater
  Problem H. Monster Hunter Solution
  uoj#418. 【集训队作业2018】三角形

• loj#6321. 「雅礼国庆 2017 Day5」Repulsed

• 树上覆盖问题
  给出一棵树，每一个关键点可以覆盖周围距离其的点，问最少多少个点可以覆盖这棵树
  Solution

数据结构

线段树

• 线段树上维护形式单调栈
  例题 luogu P4198 楼房重建
  应用 luogu P4425 [HNOI/AHOI2018]转盘
  Little Sub and Piggybank

• 括号序列
  Codeforces Round #556 (Div. 1) C. Tree Generator?
  luogu P2056 ZJOI2007捉迷藏
  给你一颗有\(n\)个点的树 , 共有\(m\)次操作有两种类别:
  1.将树上一个点染黑/白 2.询问树上最远的两个黑点的距离

• 李超树
  关于李超树的关键细节及复杂度证明

线段树合并/分裂

• Treeland Tour 树上最长上升子序列

• 区间排序 set+权值线段树合并/分裂

线段树区间最值操作

• Luogu P4314 CPU监控
  给你一个序列，支持4种操作：
  1.查询区间最大值
  2.查询区间历史最大值
  3.区间加
  4.区间赋值
  定义标记\((a, b)\)表示先给区间内所有数加上\(a\)，再与\(b\)取\(max\)，即\(A_i = max(A_i + a, b)\)
  那么区间加操作就相当于打标记\((z, -\infty)\)，区间赋值操作就相当于打标记\((-\infty, z)\)
  处理一下标记合并即可
  uoj#164. 【清华集训2015】V 做法同上

• hdu5306 Gorgeous Sequence
  给你一个序列，支持三种操作：
  0 x y t：将\([x, y]\)内大于\(t\)的数变为\(t\)
  1 x y ：求\([x, y]\)内所有数的最大值
  2 x y ：求\([x, y]\)内所有数的和
  多组测试数据，\(\sum n,\sum m\le 10^6\)
  对于线段树上的一个节点，维护对应区间的：最大值\(mx\)，最大值个数\(c\)及严格次大值\(se\)
  那么对于一次区间最小值操作：

1. 如果\(t \ge mx\)，则这个操作不会对区间产生影响，直接退出
2. 如果\(se < t < mx\)，则这个操作只会对区间最大值产生影响，区间和减小\(c (mx ? t)\)，最大值变为\(t\)，打标记退出
3. 否则，无法直接计算贡献，递归子树处理
   其中第二种情况的 “打标记” 实际上就是下传新的最大值，因此可以不打标记，直接将最大值下传
   这样做的时间复杂度是\(O(n \log n)\)的，证明参考吉老师的Segment tree Beats!
   bzoj4355 Play with sequence
   bzoj4695 最假女选手

均摊分析

• 区间开方uoj#228. 基础数据结构练习题 Solution
• 区间整除loj#6029. 「雅礼集训 2017 Day1」市场

全局平衡二叉树

每条重链取带权中位数\(m\)，分成\([l, m - 1], m, [m + 1, r]\)或者和线段树一样\([l, m], [m + 1, r]\)复杂度都是\(n \log n\)
对于虚儿子也这么建二叉树
可以支持合并
ZJOI2019 语言

• 优化链剖+NTT
  如果 \(f_x\)的次数\(x\)子树的深度有关，就可以直接长链剖分+分治NTT做到\(O(n \log^2 n)\)
  否则就要用重链剖分+分治NTT，复杂度为\(O(n \log^3 n)\)
  但是我们可以在全局平衡二叉树上面合并
  一个点\(x\)有\(size_{ls} \le \frac{1}{2} size_x, size_{rs} \le \frac{1}{2} size_x, \max(size_v) \le \frac{1}{2} size_x\)（这里\(v\)是\(x\)的轻儿子（虚儿子））
  这样只会跳\(O(\log n)\)次实边
  那虚边呢？
  如果是和子树深度有关的题，直接把\(f_v\)加起来就好了。总复杂度为\(O(n \log^2 n)\)
  如果是和子树大小有关的题，可以再用一次全局平衡二叉树的思想：找到一个点\(v\)满足\(size_{ls} \le \frac{1}{2} \sum size_v, size_{rs} \le \frac{1}{2} \sum size_v\)，但是中间那个儿子的\(size_y\)可能会\(> \frac{1}{2} \sum size_v\)。但这并不影响复杂度，因为\(size_y < \frac{1}{2} size_x\)，所以从一个点的某个虚儿子\(v\)跳到\(x\)需要的步数是\(O(\log \frac{\sum size_v}{size _v} + 1) = O(\log \frac{size_x}{size_v})\)，所以总的复杂度就是\(O(n \log^2 n)\)
  copy from yww
  loj #6289. 花朵

重链剖分

长链剖分

\(O(n \log n) - O(1)\)K倍祖先
优化Dp
bzoj 4543 [POI2014]Hotel加强版

树相关

• \(dep(LCA(u, v))\)等价于将\(x\)到根的路径加一，询问\(y\)到根的路径和
  loj#2558. 「LNOI2014」LCA

• [树上联通块非空] = 点数 - 边数
  PKUWC2019 D1T2
  给你一棵\(n\)个点的树，每一个点有个颜色\(c_i\)。定义一种颜色的树是：把该颜色的点两两路径上的点和边都拿出来构成的图形。你可以选出\(k\)种颜色来，求：有多少种方案可以使每种颜色交集产生的树非空。对\(k \in [1,m]\)分别回答。\(n \le 10^5\)，模998244353

分块

莫队、带修莫队、树上莫队详解

• bzoj4765: 普通计算姬

• 把莫队强制在线，可以考虑先预处理出每两个块之间的信息（有\(O(n)\)个），每次询问先定位到中间整块的信息，再加上左右两边剩余的元素
  luogu P4135 作诗
  luogu P5048 [Ynoi2019模拟赛]Yuno loves sqrt technology III

CDQ分治/整体二分

整体二分及cdq分治学习小结

二分图/网络流/费用流

• 二分图最小点覆盖及方案
  二分图最大匹配的K?nig定理及其证明

• 判断二分图上的一个点是否一定在最大匹配中
  loj#536. 「LibreOJ Round #6」花札
  solution

注意到一个点\(i\)一定在最大匹配中等价于所有最大流中\(S\)到该点\(i\)的边有流量。
这个命题等价于：在某个最大流中\(S\)到\(i\)的边有流量，且残量网络上不存在\(S\)到\(i\)的路径。
证：
充分性：若残量网络上存在\(S\)到\(i\)的路径，则将这条路径和\(i\)到\(S\)的边取反即可得到一个新的，\(S\)到\(i\)无流量的最大流。
必要性：假设存在一个\(S\)到\(i\)无流量的最大流，考虑该最大流与现在的最大流之差，每个点的流量必定平衡。于是由欧拉回路定理，该图必定可分解为若干简单环的和，取其中包含\(S\)到\(i\)边的一个即可构造出原来残量网络上\(S\)到\(i\)的路径。
故我们只需在残量网络上从源点开始搜索能到达的点即可。这部分时间复杂度\(O(n)\)。
另一个方法是建立二分图的交替路图，并分析每个点所能到达的点中是否有未匹配点。但直接利用这种方法判定的时间复杂度为\(O(n^2)\)（二分图的边数）。不过利用和网络流图类似的优化方法也可降低图的边数，并解决本问题。

• 最小割的唯一性（不是很懂）
  bzoj 1797 [Ahoi2009]Mincut 最小割
  bzoj 3258 秘密任务

jcvb：
在残余网络上跑tarjan求出所有SCC，记id[u]为点u所在SCC的编号。显然有id[s]!=id[t]（否则s到t有通路，能继续增广）。
对于任意一条满流边(u,v)，(u,v)能够出现在某个最小割集中，当且仅当id[u]!=id[v]；
对于任意一条满流边(u,v)，(u,v)必定出现在最小割集中，当且仅当id[u] == id[s]且id[v] == id[t]。
证明：
①<将每个SCC缩成一个点，得到的新图就只含有满流边了。那么新图的任一s-t割都对应原图的某个最小割，从中任取一个把id[u]和id[v]割开的割即可证明。
②<假设将(u,v)的边权增大，那么残余网络中会出现s->u->v->t的通路，从而能继续增广，于是最大流流量（也就是最小割容量）会增大。这即说明(u,v)是最小割集中必须出现的边。

• 二分图完美匹配求字典序最小的方案：先一遍匈牙利求出任意一组完美匹配。再跑一遍逐位确定，要求不能修改编号比它小的匹配
  luogu 4100 [HEOI2013]钙铁锌硒维生素

• 模拟费用流(To Learn)
  uoj#455. 【UER #8】雪灾与外卖

• 选取'L'形的格子
  PACNW 2013 Problem K Tile Cut
  bzoj 5403 marshland

经典模型

• DAG最小链覆盖
  拆点成二分图，点数-最大匹配
  若点可交：二分图转成网络流，\(i \in [1, n]\)连边\((i + n -> i)\)，流量为\(+ \infty\)
  若边可交：原图的边的流量为\(+ \infty\)
  点和边可以相交：求传递闭包转化成不相交路径覆盖

• 最大（小）权闭合子图/最大（小）密度子图
  后者二分答案即可转化为前者

• 区间K覆盖
  费用流

• 离散变量
  P3227 [HNOI2013]切糕
  bzoj4657 tower

字符串

KMP

• \(O(\log n)\)跳\(next_i\)
  IOI2018中国国家候选队论文集 《Fim 4》命题报告 吴瑾昭
  HNOI2019 JOJO

AC自动机

后缀数组

后缀树

后缀自动机

后缀平衡树

对于一类全序关系，可以用一个\([0, 1]\)之间的实数（或者用long long）来表示每个元素，用替罪羊树来维护，新加的元素的权值为他前驱后继的平均值。树的深度为\(O(\log n)\)，就不会炸精度了
借助这个思想，我们可以动态维护后缀数组
支持的操作：
1.在字符串前插入字符c（相当于加入一个后缀）
2.在字符串前删除字符c（相当于删除一个后缀）
3.询问一个后缀在平衡树中的排名
4.询问一个字符串在平衡树中的排名

luogu P5212 SubString
luogu P5346 【XR-1】柯南家族

子串

• HackerRank How Many Substrings?
  询问区间本质不同子串个数
  离线+扫描线+后缀自动机（后缀树）+LCT+线段树（树状数组）

• 每\(k\)化为一段，相邻两端之间\(LCS\)或\(LCP\)计算，时间复杂度\(O(n \log n)\)
  luogu P1117 [NOI2016]优秀的拆分

回文自动机

Palindromic tree
luogu P3649 [APIO2014]回文串

杂题

luogu P4248 [AHOI2013]差异
luogu P5161 WD与数列

图论

强连通分量

Kosaraju算法
Kosaraju算法的证明
对于完全图，可以用bitset优化到\(O(\frac{n^2}{w})\)

2-SAT
【算法学习】2-SAT
2-SAT 解法浅析ppt
2-SAT 解法浅析pdf

• 加边维护强连通分量
  如果A和B属于同一个强连通分量，B和C属于同一个强连通分量，那么A和C属于同一个强连通分量
  根据这个类传递性，求出每条边上两个点属于同一个强连通分量的最早时间，CDQ分治即可
  luogu P5163 WD与地图

优化建图

• FARIO 2014 Connect 线段树优化区间并查集连边
• loj#3097. 「SNOI2019」通信 分治/主席树优化建\(i\)到\(j(i < j)\),权为\(|a_i - a_j|\)的有向边

杂

• bzoj4398: 福慧双修

• 可交换\(k\)对边的边权
  考虑交换后的边在所有边按边权从小到大排序后有一个前缀，枚举那个前缀
  bzoj4681: [Jsoi2010]旅行

• 贡献只计算前\(k\)大的
  枚举第\(k\)大的值\(x\)，将所以边都减去\(x\)并与\(0\)取\(\max\)，最后再加上\(k \times x\)
  没有\(k\)条的另行计算
  NEERC 2017 Problem J Journey from Petersburg to Moscow

• 分别删除每一条边后两定点之间的最短路
  Codeforces Round #558 (Div. 2) F. Indecisive Taxi Fee bzoj 2725 [Violet 6]故乡的梦

数论

「学习笔记」数论

同余方程与二次剩余

同余方程与二次剩余
二次剩余及计算方法

模意义下的环

• loj#3096. 「SNOI2019」数论

GCD和LCM

• （扩展）裴蜀定理
  设\(a_1, a_2, a_3, \cdots, a_n\)为\(n\)个整数，\(d\)是它们的最大公约数，那么存在整数\(x_1, \cdots, x_n\)使得\(x_1*a_1 + x_2 * a_2 + \cdots + x_n * a_n = d\)
  luogu P4571 [JSOI2009]瓶子和燃料

• 区间加 区间gcd
  根据\(\gcd(a_1,a_2,\ldots,a_n)=\gcd(a_1,a_2-a_1,a_3-a_2,a_4-a_3,\ldots,a_n-a_{n-1})\)，维护差分后的序列即可

杜教筛

• \(n = \prod_{i = 1} ^ m p_i ^ {a_i}, \lambda(n) = (-1) ^ {\sum_{i = 1} ^ m a_i}\)，有\((\lambda \times I)(n) = [n \text{是完全平方数}]\)

博弈

• Codeforces Round #556 (Div. 1) Problem E. Election Promises
  给出一个DAG，每次操作可以选择一个非0节点减少任意值，任意修改它出边的点的值，两人轮流操作，不能操作的输，判断先手胜负，输出先手第一步的任意一个最优决策

线性代数

矩阵树定理

学习笔记

https://blog.csdn.net/a_crazy_czy/article/details/72971868
例题
https://blog.csdn.net/samjia2000/article/details/73520175

消元

Gauss–Seidel迭代 + Jacobi迭代

线性基

• 带删除的线性基
  对于线性基中的每个向量和所有\(0\)向量维护这个向量是由哪些向量异或得到的。
  在删除一个向量\(x\)时，找到一个包含\(x\)的\(0\)向量，如果没有就找线性基里位最低的包含\(x\)的向量，把这个向量的信息异或到其他包含\(x\)的向量的信息中即可。这样在删除时不会影响线性基中更高位的向量。
  在向量个数比较小或强制在线是比较有用。

• 区间询问最大异或
  http://codeforces.com/problemset/problem/1100/F
  直接套线段树，暴力合并，复杂度\(O(n \log n \log C + q \log n \log^2 C)\)
  离线，考虑分治，算出前一半的后缀和后一半的前缀，回答跨过中间的询问，剩下的递归计算，复杂度\(O(n \log n \log C + q \log^2 C)\)
  对于某个右端点，向左的本质不同的线性基只有\(O(\log C)\)个，考虑维护（目前我还不知道怎样实现，网上很多人的做法都是假的。我觉得应该是插入一个元素后出现了0，也就是出现了异或为0的等式，把那个等式中出现最早的元素换成现在插入的那个元素）
  对于某个右端点，考虑只维护一个线性基，对于每个基维护它需要的最大左端点（一般如果我们按顺序插入，得到的基是最早出现的。这里就是倒序插入）。插入当前的右端点，当遇到冲突时（最高的1相同，有一个需要被异或），显然晚插入的那个应该是这位上的基，把另一个异或上它，继续做。复杂度\(O(n \log C + q \log C)\)

综合

bzoj4766: 文艺计算姬

数值计算

• 自适应辛普森（Simpson）积分

Reference