断更原因：初三折磨人
我们用链表维护的是一个元素的前驱和后继，而这个前驱和后继是靠数组下标维护的，这意味着我们可以方便的通过将元素值当作下标的方式查找之前驱和后继，这意味着我们如果想要从大到小的对链表中的元素进行操作可以不使用雷霆的sort而是直接通过将值域中的每一个数从大到小作为下标然后乱搞。
e.g.:
for (int i = n; i >= 1; i--)
{
if (nxt[i])
{
cout << i << ' ' << nxt[i] << ' ';
// cout << nxt[pre[i]] << ' ' << nxt[nxt[i]] << '\n';
update(i);
}
}主要难点在于合并和pushup
首先我们明确哈希的计算原理。对于一个字符串 $S = s_1 s_2 s_3 \dots s_n$，它的哈希 lnum 计算公式为：
$Hash(S) = s_1 \cdot base^0 + s_2 \cdot base^1 + s_3 \cdot base^2 + \dots + s_n \cdot base^{n-1}$
一个字符就是$s[i]-'a'+1$
接下来我们合并两个相邻的子串：
左子串 $L$，长度为 $len_L$，哈希值为 $Hash(L)$
右子串 $R$，长度为 $len_R$，哈希值为 $Hash(R)$
合并后的总字符串为 $L + R$。根据上面的定义，总哈希值应该是：
$$Hash(L+R) = L_1 \cdot base^0 + \dots + L_{len_L} \cdot base^{len_L-1} + R_1 \cdot base^{len_L} + \dots + R_{len_R} \cdot base^{len_L + len_R - 1}$$
我们将这个式提取公因式，分为两部分：
$$Hash(L+R) = \underbrace{(L_1 \cdot base^0 + \dots + L_{len_L} \cdot base^{len_L-1})}_{\text{正好是 } Hash(L)} + \underbrace{base^{len_L} \cdot (R_1 \cdot base^0 + \dots + R_{len_R} \cdot base^{len_R-1})}_{\text{正好是 } base^{len_L} \cdot Hash(R)}$$
所以
$$Hash(L+R) = Hash(L) + Hash(R) \cdot base^{len_L}$$
code：
res.lnum = (ld.lnum + (pw[ld.r - ld.l + 1] * rd.lnum) % mod) % mod;有的时候我们还要反过来算一遍，还是列出反向后的柿子
$$rev(L+R) = rev(R) + rev(L)$$
注意$R$在$L$前面
所以现在，我们要计算 $rev(R) + rev(L)$ 的哈希。套用我们刚刚推导出的合并方法，有：
$$rev(L+R) = Hash(rev(R)) + Hash(rev(L)) \cdot base^{len_{rev(R)}}$$
显然有
$$revHash(L+R) = revHash(R) + revHash(L) \cdot base^{len_r}$$
故
$$rnum(L+R) = rnum(R) + rnum(L) \cdot base^{len_R}$$
code:
res.rnum = (rd.rnum + (pw[rd.r - rd.r + 1] * ld.rnum) % mod) % mod;我们感性理解一下，其实核心在于字符位置的变化。位置的变化会导致$Hash(S) = s_1 \cdot base^0 + s_2 \cdot base^1 + s_3 \cdot base^2 + \dots + s_n \cdot base^{n-1}$中$base$的变化。而其中唯一可能变化的量就是$base$。所以我们找$base$何时变化就可以了。那base何时变化呢？随着位次的的增加而变化。所以我们考虑字符所在的位次就可以了。
1.正向合并：左串不动，右串的每一位都要往后挪 $len_L$ 个位置，所以右串要乘 $base^{len_L}$。
2.反向合并：因为整体反转了，右串跑到了前面，左串跑到了后面。所以左串的每一位要往后挪 $len_R$ 个位置，所以左串要乘 $base^{len_R}$。而右串原本的hash计算$base$就是从$1$开始的，现在还是从$1$开始，所以不用考虑跑到前面带来的影响！
取模其实是一个轮回，对要取模的数进行除法操作，若结果大于$1$那就说明进位了，数字会变小。
其实就是vector<bool>牛逼的版本
看到「在模 2 意义下」，可以想到用 bitset 维护每个可重集．
对于长椅分配问题，可以考虑把整个地图隔$1$黑白染色，这样可以区分开横着和竖着的限制
然后我们在尽量把每条路分配给左边，上边的长椅。尽量让他们“居居”在左上角一个有限的区间，可以证明这是最优方案
怎么证明呢？我不会。
对于 $x,y,z(x<y<z)$，$min{x xor y,y xor z}<x xor z$。
$a ^ a ^ b = b，a ^ a = 0，a ^ b ≤ a + b$
写了一上午组合数学要吐了\kel
1.$k \times C_{n}^{k}= n \times C_{n-1}^{k-1}$ 有$n$个人，要选择其中$k$个人组成一支小队，从中再选出一个队长，不难发现等式两边都适用于这个问题
即$C_{n}^{k}= \frac{n}{k} C_{n-1}^{k-1}$
2.$\sum_{i=0}^{n} C_{n}^{i}=2^{n}$ 枚举子集的角度考虑来证明
3.$C_{n+m}^{m}=\sum_{i=0}^{n} C_{n}^{i} \times C_{m}^{m-i}$ 考虑从集合$A（有$n$个元素）和集合$B$（有$m$个元素）中选择$m$个元素，容易发现等式两边是问题的不同表达
4.$C_{2n}^{n}=\sum_{i=0}^{n} C_{n}^{i} \times C_{n}^{i}$上式$m=n$的情况
5.$\sum_{i=0}^{n}C_{m}^{i}=C_{m+1}^{n+1}$ 右式：在$0-n$中选择$m+1$个数 左式：设当前最大值为$i$,有多少种可能？
左式是把右式按照最大值分类统计后的结果，故两者相等
dp[i][0/1] $0/1$ 可以表示有向边的方向 方向也是dp中可以量化的量
刚刚发现自己不会LIS的带log写法
其实就是设$f[i]$表示长度为$len$的LIS的结尾的当前最大值。然后二分查找最小值之后第一个小于最小值的数就行了。
for (int i = 1; i <= n; i++)
{
int l = 0, r = t + 1;
while (r - l > 1)
{
int m = l + (r - l) / 2;
if (f[m] >= h[i])
l = m;
else
r = m;
}
int x = l + 1;
if (x > t)
t = x;
f[x] = h[i];
}
cout << t << "\n";见到$i$与$\lfloor \frac{i}{2} \rfloor$作为被操作的元素的下标立刻考虑建造一棵二叉树，考虑树形dp或贪心等
例题：P2606,P4785
三个相同的连续字符构成一个合法匹配的可以考虑舍去中间的那个，最左边的(第$1$个)视为左括号，最右边的(第$3$个)视作右括号，然后可以发现我们得到了一棵树和他的一个括号序，记每个点的颜色表示其被谁拿走，不难发现树上每个点和其父亲的颜色不同，然后神秘操作一下子就行
*建图跑拓扑也行
例题：CF1427F,P5658
$x \xor x$出现在算式中可以直接视作啥都没有
所以可以把一个式子$\xor$上它本身消掉他
实际上，这里的trie树帮我们维护的其实就是位次的关系！
具体的，当我们把一个数插入Trie树时，它走过的路径就是它的二进制表示本身。所以Trie树天然地把所有数按照"从高位到低位"的顺序组织起来了，这也启示了我们对trie树的利用的新方面：维护数的位次顺序
我们就可以开始从高位往低位进行二进制贪心了。可以从0/1的数量来考虑，如果要从数字整体的大小的方面来考虑，那就可以从左右子树的方面来想。具体的，对于trie树的每个分叉，左分叉中的所有数字的数字一定小于右分叉中的所有数字。假如我们要寻找次于某个数的数，我们就可以构造trie数，然后在trie树上找这两个数的分叉处，走过这个分叉接下来所有分叉无脑走最大就行
当然如果让我们找第k大也好说。这是一个动态的过程。因为trie是从左到右逐渐增长，所以一定有一个分支的数的数量小于k，存的是第k-x大的数字。这一部分我们不需要。所以我们只需要记录每个分叉存的数的数量，如果小于k就减掉去搜下一个分支(往右走)，如果大于k就往左走，最后就可以搜到了。
总之，我们主要利用的性质有两个
1.位次的关系。Trie天然的把所有数按照从高位到低位的顺序组织了起来，方便进行比较，前缀查询等。
2.大小的关系，左分叉一定小于右分叉。
观察数据范围并写出转移式，若发现转移次数极多，且从“当前状态”到“下一个状态”的转移公式是完全一模一样的，不跳步（或者可以通过拆分拆成一样的），就可以考虑构造一个初始矩阵（因为要用一个统一的转移矩阵来转移，不能因为跳步而变化），再根据dp转移式构造一个转移矩阵上去转移（乘对应次数次）就行了。初始矩阵相当于dp的初始状态，转移矩阵相当于转移式。部分满足结合律的运算，如加法，乘法，异或出现在转移式中若满足上述条件也可以用矩阵辅助转移。
这里有一种普遍的优化：预处理第$2^n$个矩阵，原因是任何的整数（我们要用到所有的转移次数）都可以用之拼出来，这样我们只需要做一个二进制分解然后直接取值即可。并且$2$的次方的矩阵可以很方便的用快速幂递推地计算出来。
具体怎么计算呢？$T^{2^k} = T^{2^{k-1}} \times T^{2^{k-1}}$。这意味着我们只需要 $O(\log k)$ 次矩阵乘法，就能算出所有需要的 $2$ 的幂次矩阵。高效又方便。
这里每一步运算完后得到的是进行（当前升幂次数）递推后的结果，要与下面的广义矩阵乘法做区分。
例题：P6569，P6772
事实上，在大多数情况下，只要一个式子满足结合律，就可使用我们刻画出一种可能的使用矩阵乘法的转移。注意这里是可以使用而不是可以刻画。刻画是一定可以刻画的，转移一次也是可以的，但是转移多次就不一定了，具体见下。
Q1.为什么一定要满足结合律才能使用矩阵乘法转移？
sol：如果不满足就意味着运算分步，括号有顺序，不能一步到位，那进行幂运算就会出现顺序错误的问题，故不行。其实这里和之前优化dp的部分的从“当前状态”到“下一个状态”的转移公式是完全一模一样的差不多。只是这里改成了“是完全一样的操作”。
这里有一种方法。矩阵快速幂优化前想一想，“如果我把两次转移合并成一次，会不会改变原本从左到右的执行顺序？”如果不会（满足结合律）那就上矩阵快速幂。
Q2.证明？
矩阵快速幂的本质，是把 $k$次“一模一样”的转移，通过结合律任意重排括号，从而用 快速幂$O(logk)$次矩阵乘法代替 $O(k)$ 次不俗运算。如果转移本身会变，或者括号不能重排，快速幂就会算错。