You may check this article on cp-algorithms.com (or OI-wiki if you prefer reading in Chinese) for more precise information and proof of complexity about SAM. Here I just want to write about another perspective to understand SAM, which I’ve learned from Huadun Hong, PKU, through Zhengruioi’s online courses on 4th, Feb, 2020.

0

We can get the suffix tree of string $S$ simply by inserting all of its suffixes into a trie (though this will involve $O(|S|^2)$ vertices). Note that:

桥梁

将所有的操作按照时间顺序分成$T$个大小为$\frac{q}{T}$的块。对于每个块，将块内的询问按照$w_j$排序，将未被块内的操作修改过的边按照执行这个块内的操作之前的边权排序。

按照$w_j$降序枚举块内的询问，然后将所有重$w_j$的车能够通过的、“未被块内的操作修改过的”边加入；再加入块内修改过的、这次询问的时候的边权$\ge w_j$的边，查询$s_j$所在连通块的大小，然后再撤销掉加入的块内修改过的边。

C - Make Good

记$sum$为所有数的异或和，$tot$为所有数的和。$tot$显然必须是偶数。所以如果$tot$是奇数的话，就先往数组里面加入一个$1$。

如果$2\times sum > tot$，就往数组里面加入两个${2\times sum - tot \over 2}$，这对数组中的数的异或和没有影响。

CF1246F Cursor Distance

考虑对于每一个$i$，求出至多走$k$步就能够到达它的位置所构成的区间$[L_{i,k},R_{i,k}]$。我们只要对每个$i$分别求出$\sum_k L_{i,k},\sum_k R_{i,k}$就能得到答案。

最短路不一定是单向的（比如对于baaaaac，从b走到最后一个a），所以$L,R$可能不独立，不能直接倍增计算$L,R$的和。

TopCoder14929 MaxSquare

official editorial

设$s_i$表示$B$的前缀和。

LOJ2146 「SHOI2017」寿司餐厅

把$mx^2 + cx$拆一下就是：只要吃的寿司里面有代号为$x$的就要付出$mx^2$的代价；每吃一种代号为$x$的寿司就要付出$x$的代价。直接令$d_{i,i}$减掉$a_i$，就可以不再考虑$cx$这部分。

对每个区间$[l,r]$建一个点，权值为$d_{l,r}$；对每个代号建一个点，权值为$-mx^2$。如果选了$d_{l,r}$就必须选$d_{l,r-1}$和$d_{l+1,r}$，如果选了$d_{i,i}$就必须选$ma_i^2$。求出这张图的最大权闭合子图即可。

UOJ422 小z的礼物

考虑min-max容斥：

对希望得到的物品的每一个子集，求出期望最早什么时候子集里至少有一个物品被拿到了，就能算出答案。

loj6485 LJJ学二项式定理

首先枚举$i\pmod 4$的余数$t$，然后转化成对于每一个$t$，求

单位根反演：

CF963E Circles of Waiting

圆内的整点形成了一个类似方阵的结构。设$f_{x,y}$为$(x,y)$期望被经过的次数。我们可以对每一个点列出一个方程：

将每一行最左侧的点设为主元，其它的点都用主元表示。从左往右考虑每一列的点：$f_{x,y}$可以用$f_{x-1,y}$的方程表示出来（因为方程中涉及到的$f_{x-1,y},f_{x-1,y-1},f_{x-1,y+1},f_{x-2,y}$在之前都已经考虑过了，只有$f_{x,y}$是未知的）。