Catalogue.txt

1) Segment trees. just find functions which can be merged. 
2) convert mergesort tree type structures to pers if possible
3) knapsack with duplicates is solvable by breaking k = 1+2+4+8+...
4) Try applying different types of sqrt decomp. By nodes, or by queries. 
5) What we can do is perform some queries, and then revert them, and see what changes we incurred.This could be optimal in several cases. like dynamic MST. 
6) Apply exchange argument for greedy algorithms. Mainly, find the sorting parameter. what can help is checking only with N = 2 to find a sort parameter.
7) try to apply binsrch to determine the answer wherever possible. 
8) if its a tree problem, think about centroid decomp first. If during that decomp, you need to access information abt paths that go into the domain of a parallel centroid, then it means ur basically moving up in the centroid tree. Then ofcourse think in relation with a centroid tree. 
9) think about LCA based merging. also used s2L while merging always when possible. 
10) Try to convert DP problems into DAG problems.
11) treaps can be helpful sometimes. 
12) think about euler tours of a tree, including path euler tour. We can skip subtrees in the path version by marking first entry using + values and second using - ( or wtvr the inverse is, if present). That way, if entire subtree is skipped, stuff cancels out.
13) treedp can be sometimes simplified using HLD. 
14) try using Mo's, either the normal variant or the euler tour variant. 
15) when cycles are in graph, try in terms of euler tour. Also think what happens when two cycles intersect.
16) think offline preprocessing with prefix sums. even 2D
17) while doing small to large, especially when using segment trees(like while counting inversions), to make complexity nlogn instead of nlognlogn, traverse the segment trees simultaneously, but primarily focus on the smaller segmenttree. when there is a NULL pointer in the smaller segtree but a node in the larger segtree, just attach a reference to that node in the new segment tree, while otherwise merging the results of both segtrees in the old segtree.
18) considering bitmask problems, try to think of subproblems also in the form of bitmasks, as we already have a 2^k term in out complexity, so it cant get worse anyway.
19) In graphs, if some parameter is small, convert graph to DAG by incorporating the small param into the node label for the new graph. Then try do DP.
20) We can try to reduce problems to geometry problems. For EG : if we have to maximize some function, we can write it as slope. for eg, let a/b and c/d be chosen to maximize a+b/c+d. we can write this as slope between 2 points and reduce it to hull problems.
21) When finding shortest odd/even length path from a source to target vertex, modifying shortest path algorithms only give the shortest walk, and not shortest path. 
22) Note that .size() does not return an int, so convert it to an int
23) while computing maxflow, if do several maxflows, and in each iteration we increase capacities by 1, the comlexity does not change by much, so its worth implementing.
24) number of triangles in a graph is O(Msqrt(M)). This can be used especially in the fact that if we include child of child (only if they are not connected directly) for some problem in our queue lets say, we only do msqrt(m) insertions. This is because, for every triangle, we visit a->b->c even though a->c is a valid edge, making the earlier visit redundant.
25) 2*(a&b) + a^b = a+b
26) Counting problems, like number of different arrangements of stuff can be sometimes treated as counting number of topological sorts in a graph.
27) HLD can be used for proving amortizations in trees as well, considering that each path has atmost logn nodes, and that for updates, each chain gets modified only O(queries) number of times.
28) When in each query some information is given so that the sum of all those informations if O(N), try using sqrt decomp on that.
29) TRY SQRT DECOMPOSITION EVERYWHERE.LITERALLY EVERYWHERE.
30) greedily choosing numbers in array with atleast 1 separation can be seen as manipulating augmenting paths in a bipartite graphs, and can be maintained in a heap.
31) In queries regarding ranges, we can maybe try to process the begining and ending as events while processing offline. 
32) Constraint equations can be solved via bellman ford. u - v <= a implies an edge from V to U with wieght a.
33) while doing treaps and lazy, note that its not exactly like segtree. so like the lazy tags might need to be pushed two steps sometimes to calculating the sum at a certain level, because here, we can recalculate stuff even though lower things have not been pushed due the the split and merge functions. 
34) Exact K-edge shortest path can be solved using bellman ford. We just need to do it in a dp style.
35) we can use the fact that in a tree number of vertices - number of edges = 1. Thus it can be extended to a forest as well. This can be useful in case we are keeping count of the number of trees somewhere. Also can be used to find the number of connected components.
36) Try to see if a graph can be formed for which euler tour gives then answer
37) while expanding in segtree node, the normal pointer which is passed into the update/query function needs to be reference variable as well, and not just in the expand function.
38) Grid can be viewed as a bipartite graph with rows and coulumns as nodes and the (i,j) pair with the a[i][j] as the edge. This can also be done in a graph, where the x and y axis itself can be nodes, and edges are basically the points (i,j)
39) x^k can also be represented as (1+1+1....+1) * (1+1+1+1 ... +1) * ... (..) which means basically number of order tuples from each of the sets in the brackets, which can be calculated with a dp
40) cache friendliness can make even 1e10 basic operations run really fast
41) check connected component dp and the fact of setting default values initially and then updating them as u put stuff one by one.
42) check complexity of stuff carefully. things might get amortized, there might be some other constraint that reduces the complexity.
43) while pairing stuff, pairing via their ith bit is set or not strategy is cool. Similarly while separatinh stuff,  separate via their ith bit.
44) proving stuff on trees via HLD can be cool.
45) if two stuff is happening simultaneously, maybe they can be separated?
46) sometimes when coloring stuff, maybe we can color inside stuff in any way we want, and then fixing some other stuff so that this coloring becomes valid. So suppose in a rectangle, we want to color so that xor of values of rows and columns are given. so we randomly color rectangle R-1 x C-1 and fix rim. something like this strategy. Like, coloring inside of tree, and fixing color of leaves accordingly.
47) in DnC dp, if we move the L,R of the cost function as and when needed, like mo's style, apparently its bounded by nlogn, which means amortized O(1). CF: 868F.
48) dont set block sizes that exactly divide the variable on which sqrt decomp is being performed. wierd errors can take place that require more handling.
49) apparently long double is 12 bytes, so use it when comparing in CHT as even long*long can overflow
50) sometimes, it can be useful to delete a certain vertex in a graph and count stuff in the rest of the graph, for example counting connected components maybe.
51) in a tree, doing +1, -1 on nodes and then taking subtree sum to check "partial sums" can be a useful technique in several cases. 
52) when considering DP of permutations or such, we can maybe process numbers in order , like 1 then 2 then... i then i+1. Also, we can do stuff about blocks in permutation by using partition functions.
53) dividing into sets based on powers of 2 can be oof, in many cases. Like, even in range queries, we can try to divide it into 2 powers of 2, (for min max query maybe) both of range 2^k <= L, st 2^(k+1) > L (like we do in O(1) sparse table max).
54) for grid problems and toggling, we can think about enemy DSU.. or maybe in other places as well. a cool idea.
55) euler tours are fun in a graph. think about them. 
56) we can set up root(n) checkpoints in some query update type problem, and then during queries, extend from each checkpoint. Like in the retroactive problem theorem.
57) in tree problems, rerooting can be used, which is, shift the root to some other node by travelling thru some edge.
58) DSU with rollbacks can be avoided by adding the extra edges and then doing a DFS.
59) we can transform coordinates if necessary. Basically to shift from a pair of bases to another, we do 2 sweeplines from the direction perpendicular to either of the bases
60) instead of doing everything online, we can do stuff offline with segtree + sweep. so 2D / pers can be avoided.
61) doing stuff backwards is a NICE idea
62) parallelelllll binaarryy searrcch is nice
63) there were 2 probs were we could precompute in blocks and then compute in whole
64) whenever edge wieghts are there, see if only MST is concerned.
65) in euclidean MST, no node has degree more than 5
66) deque takes much more memory than vector :3 even more than vector[] + int[]
67) Intersection of two cycle intervals whose sum of lengths is less than n, results in a single cycle interval. If the length if more than n, then this is not necessarily true. 
68) "Rule of thumb": When the question is "count numbers satisfying some inequalities", sqrt-decomposition is usually the right way.
69) Think about DP stuff in Matrix forms, maybe that will help, especially when DP is combined with query, we can think about range matrix multiplication using segtree