Summarize some recent tricks

Summarize some recently seen TRICK：

1. Union checking set $O(n+m)$ Solve the problem of interval merging 3115. Crazy steamed bread .

2. Slide the window enumeration to $i$ Time to time $[i-k,i-j]$ The highest value in .

3. Monotone stack needs to reverse the order to find the rightmost value closest to itself .

4. Enumeration matrix has 4 A degree of freedom , By enumerating the upper and lower boundaries, the matrix can be changed into 1 Dimensional , It is being realized with binary or double pointers $O(n^3)$ Traverse .

5. Given a $n\ast m$ Matrix Ask for one $c\ast c$ The maximum value in the submatrix of size . It can be realized by two-dimensional sliding window . The core idea is to regard two dimensions as one dimension . First, find a length of $c$ Sliding window of , Find a length of $c$ Sliding window of , Finally, enumerate the answers .

6. DP The essence of is combinatorics , Can pass 0/1 knapsack , The idea of complete knapsack deduces the combinatorial number formula and the resettable combinatorial formula in combinatorics .

7. Remember some smart data for interval merging , Interval merging can $O(n)$ Realization , The left endpoint is sorted from small to large .

8. unorder_map, capitation $O(1),The\; worstO(n)$ , Fast platoon is shared equally $O(nlogn),The\; worstO(n^2)$ You can prevent being stuck by initializing the size ,（CF With the exception of , need mt19937）

9. Interval merging has 3 Methods , Union checking set , greedy , discretization + Difference .

10. Brush table method can solve knapsack problem $K$ Excellent solution .

11. Given a matrix , Find the area of the largest submatrix with constraints , Or consider each line separately , run $n$ Time Monotonic stack .

12. Dye a pile of things for the final color , You can think backwards .

13. Many ideas for solving problems on trees come from The center of gravity of the tree also The diameter of the tree .

14. Many problems need to be gradually decomposed , If there is no thought , You can try , Draw pictures to find rules and properties , Two point answer turns to judgment , etc.

15. Double pointer key （ In fact, if you write too much, there is nothing critical ）, Definition $j=f[i]$ , If $i$ After determining ,$j$ Only monotonously left （ Not seen ）/ Move right , You can directly double pointer .while Inside the loop is the negative condition .

16. Find the maximum value on the matrix except for $n$ The monotone queue can also be two-dimensional $ST$ surface .

17. Line segment tree pointer writing ,new Super slow , You can define static nodes and move them by one bit .

18. $LCA$ Yes $tarjan$ , Union checking set , Multiply Three ways of writing , At least recite one .

19. If two intervals $[l_1,R_1],[R_1+1,R_2]$ Want more space , You can subscript by 2. somewhat sb

20. Two dimensional and one-dimensional can be transferred into one dimension of two-dimensional array , But what if you follow the column ？ Or rewrite a , Or take out the data first according to the column , Then pass it in .

21. Sometimes I put DP The state is too dead , Then it is found that the state transition equation cannot be written at all , You can take a step back , Give Way DP Multi band one-dimensional information , Try again. . such as , Definitely , Definitely not .

22. The feasibility of DP, It can be used bitset Pretend to realize .

23. Some known middle order traversals and xx Traverse , Output bfs Preface question , stay dfs Wear a layer inside , Can directly record bfs order .
    Cartesian tree .