\(\bf Coding\ Notes\ (From\ 2022.11.11)\)
\(\bf Some\ Notes\ To\ Help\ Me\ Do\ Better!\)
\(\bf My\ Achievements:(Only\ Questions\ Which\ Has\ A\ Difficulty\ Judgement\ By\ Luogu\ will\ be\ Included)\)
| \(\bf\color{#FE4C61}{Red}\) | \(\bf\color{#F39C11}{Orange}\) | \(\bf\color{#FFC116}{Yellow}\) | \(\bf\color{#52C41A}{Green}\) | \(\bf\color{#3498DB}{Blue}\) | \(\bf\color{#9D3DCF}{Purple}\) | \(\bf\color{#0E1D69}{Black}\) | \(\bf\color{#BFBFBF}{Grey}\) | |
|---|---|---|---|---|---|---|---|---|
| \(\bf Number\) | \(\bf\color{#FE4C61}{2}\) | \(\bf\color{#F39C11}{8}\) | \(\bf\color{#FFC116}{10}\) | \(\bf\color{#52C41A}{10}\) | \(\bf\color{#3498DB}{14}\) | \(\bf\color{#9D3DCF}{8}\) | \(\bf\color{#0E1D69}{0}\) | \(\bf\color{#BFBFBF}{5}\) |
\(\bf\color{#FE4C61}{Red}:\ CF1761A,\ CF1764A\)
\(\bf\color{#F39C11}{Orange}:\ P3378,\ CF1761B,\ P1540,\ CF1764B,\ CF1557B,\ P8918,\ P8924,\ P8925\)
\(\bf\color{#FFC116}{Yellow}:\ CF1761C,\ P5788,\ CF20C,\ CF1764C,\ P2880,\ P2251,\ P1816,\ CF1606C,\ P8306,\ P2580\)
\(\bf\color{#52C41A}{Green}:\ P2629,\ CF1764D,\ P8818,\ CF1617D1,\ P5656,\ UVA11526,\ P4343,\ CF1675F,\ CF1671E,\ P8926\)
\(\bf\color{#52C41A}{Green}:\ P8927\)
\(\bf\color{#3498DB}{Blue}:\ CF1761D,\ CF1761E,\ CF1764D,\ P3092,\ P2897,\ CF1747D,\ P3384,\ P3178,\ P8817,\ P3919\)
\(\bf\color{#3498DB}{Blue}:\ P2261,\ SP14168,\ P3396,\ P4551\)
\(\bf\color{#9D3DCF}{Purple}:\ P3850,\ P3278,\ P2042,\ P3165,\ P2710,\ P8819,\ P3203,\ CF13E\)
$\bf\color{#0E1D69}{Black}:\ $
\(\bf\color{#BFBFBF}{Grey}:\ CF1760A,\ CF1760B,\ CF1760C,\ CF1760G,\ CF1759G\)
\(\bf Part 1-Questions\ In\ Luogu\)
\(\bf 1.\ \color{#9D3DCF}P3850\)
\(\bf Knowledge:\) 平衡树
\(\bf Tricks:\) 利用平衡树结构确定唯一大小序列的特性和 merge() 默认左小右大的性质，可以不记录下标，只通过自动的寻找正确位置插入实现。
\(\bf 2.\ \color{#9D3DCF}P3278\)
\(\bf Knowledge:\) 带参数平衡树
\(\bf Tricks:\) 平衡树与线段树的 lazy 结合，维护移位和区间加乘。
\(\bf 3.\ \color{#9D3DCF}P2042\)
\(\bf Knowledge:\) 究极带参数平衡树
\(\bf Tricks:\) ①平衡树与线段树的 tag 结合，维护奆多操作。②一次插入许多数时 \(O(n)\) 建树再插入的方法。③ update 的时候需考虑是否需要判有无左/右子节点
\(\bf 4.\ \color{#9D3DCF}P3165\)
\(\bf Knowledge:\) 平衡树
\(\bf Tricks:\) 按排名分裂的平衡树可以利用维护 minn 以达到查询最小值在数列中的排名。（通过根左右的 minn 判断最小值在左子还是右子）
\(\bf 5.\ \color{#3498DB}P2897\)
\(\bf Knowledge:\) 神仙的单调思想模拟
\(\bf Tricks:\) 由于水从高到低流，又需要找到现在和接下来哪个水面在增加，可以利用单调思想（低的没填完不会填高的），每个平台只会被经过两次，达到 \(O(n)\)
\(\bf 6.\ \color{#9D3DCF}P8819\)
\(\bf Knowledge:\) 随机权值哈希
\(\bf Tricks:\) 随机赋值 \(w\) 数组，通过 \(a_1w_1+a_2w_2+\cdots+a_nw_n=\sum w_i\) 做到 \(O(1)\) 判断 \(a\) 数组全为 \(1\)。
判断动态数组相等 \(\texttt{Hash}\)，若 \(w\) 随机，
\[\sum_{i=1}^n w_i\times a_i=\sum_{i=1}^n w_i\times b_i\to a_i=b_i \]\(\bf 7.\ \color{#9D3DCF}P3203\)
\(\bf Knowledge:\) 分块
\(\bf Tricks:\) 对于某些问题，需要从一个点更新到结尾，要么查询 \(O(n)\) 更改 \(O(1)\)，要么更改 \(O(n)\) 查询 \(O(1)\)，我们可以利用分块思想，每一个点只更新到段尾，尝试用段间进行关联求解，做到查询更改 \(O(\sqrt{n})\)（对两种暴力的折中）
\(\bf 8.\ \color{#3498DB}P4185\)
\(\bf Knowledge:\) 并查集
\(\bf Tricks:\) 对于非标准数据结构形式的题目，又有类似数据结构的特征，可以考虑离线并以特殊的顺序回答询问。
\(\bf Part 2-Questions\ In\ Codeforces\)
\(\bf \color{#5EB95E}{[1700,2100]:(Total:\ 6)}\ CF1760G,CF1761D,\ CF1764D,\ CF1747D,\ CF1617D1,\ CF1675F\)
\(\bf 1.\ \color{#3498DB}CF1761D\)
\(\bf Knowledge:\) 组合数，数学
\(\bf Tricks:\) 组合数题目需一层层去掉限制条件，变为朴素计数（主要是多做...）
\(\bf 2.\ \color{#3498DB}CF1761E\)
\(\bf Knowledge:\) 思维题
\(\bf Tricks:\) 从简单情况开始考虑（什么图 \(1\) 步搞定，什么图 \(2\) 步？）
\(\bf 3.\ \color{#3498DB}CF1765D\)
\(\bf Knowledge:\) 组合数，数学
\(\bf Tricks:\) 先通过设变量剥离限制条件，再处理影响最大的先算（比如本题的最后一个选的点，因为导致了超过一半连续，所以是特殊的点，应先考虑）
\(\bf 4.\ \color{#3498DB}CF1747D\)
\(\bf Knowledge:\) 思维题
\(\bf Tricks:\) 从简单情况开始考虑（什么序列 \(ans=-1\)？什么序列 \(ans=1\)？什么序列 \(ans=2\)？）
\(\bf Part 3-Questions\ In\ AtCoder\)
\(\bf Part 4-Questions\ In\ RMJ\)
\(\bf 1.\ \color{#3498DB}SP14168\)
\(\bf Knowledge:\) 整除分块
\(\bf Tricks:\) 遇到约数和不好考虑时可以考虑为转而枚举约数，可能能降到 \(O(\sqrt{n})\)。
\(\bf Part 5-Self-owned\ Questions\)
\(\bf 1.\ \color{#9D3DCF}T294199\)
\(\bf Knowledge:\) 图论，缩点，dfs，二分答案
\(\bf Tricks:\) ①对于答案求 \(ans\) 极值，且 \(ans\) 取值只有一个转换点，可以考虑二分答案。（例如本题 \(k\)，只会随着 \(k\) 变小而从 Yes 转为 No，这样一个转换点）②对于树上 dp 需要用子节点值更新父亲节点的题目，可以 dfs 回溯过程中更新
\(\bf 1.\ \color{#9D3DCF}T297651\)
\(\bf Knowledge:\) 平衡树
\(\bf Tricks:\) 区间加等差数列，不一定要差分，也可以用首项 & 公差标记解决（具有可加性）
\(\bf 3.\ \color{#3498DB}T297652\)
\(\bf Knowledge:\) 线段树
\(\bf Tricks:\) 对于非标准线段树/平衡树形式的题目，又有类似数据结构的区间等特征，可以考虑离线并以特殊的顺序回答询问。
标签：bf,Knowledge,color,Notes,9D3DCF,Coding,3498DB,My,Tricks From： https://www.cnblogs.com/yinhy09-OI-blog/p/notes1.html