Summary of common skills

2021/12/9

The two strings are trie On the tree LCA It's two substrings lcp
The two prefixes are SAM Of parent On the tree lca, Is the longest common suffix of these two prefixes （AHOI differences ）
KMP The number of occurrences of each prefix on the mismatch tree of is equal to the number of points in its subtree plus one
ACAM Of fai The number of points in each subtree on the tree is the number of occurrences of this point in all strings

2021/12/10

If a function value $f(x)$ be equal to x The function values of all factors add up , also $f(1)$ yes 1, So this is Mobius function
The properties of the minimum spanning tree ：
1： When the edge less than a certain weight is added , The connection of the whole picture is certain
2： In the minimum spanning tree , The number of edges of a weight in the tree is fixed

2021/12/13

CDQ The outermost layer of partition is best shaped like $a\le b$ instead of $a<b$
Otherwise, special judgment is required , And if the two elements are exactly the same, it may be less remembered. The contribution should be combined first
When calculating the slope, it is necessary to judge whether there will be x The same results in less than once
Slope optimization must be judged clearly , Dot x Are the coordinates orderly
When the decision is monotonous, divide and conquer
If it is layered , Or the calculation is more troublesome , Write with divide and conquer , Similar to the whole dichotomy
If you can $O(1)$ perhaps $O(logn)$ Calculated , Select two points + Monotonic stack

2021/12 26

DP When , If not enough, open another array
Sometimes the state can be expressed by difference , Reduce complexity

2021/12/28

Edge weights in graphs , You can turn an edge into a point by creating a new point on it
The point weight in the graph , You can split a point into input points and output points and convert them to edges

2021/1/5

2-sat If you are afraid of less conditions, you can consider all points
The optimization of line segment tree should be started 5 Times the space