CFTracker，都说刷这个比较好？加 ❄ 的是现在不会的，加 🅰 的是字符串题。
CF526F Pudding Monsters
转化为 $\max_{i=l}^{r}\{a_i\}-\min_{i=l}^{r}\{a_i\}=r-l$ 的个数，扫描线，维护最小值及其个数即可。
CF487E Tourists
圆方树板子。
CF739E Gosha is hunting
wqs 二分 + 贪心，我数据结构呢？？？
CF765F Souvenirs
扫描线，类似找支配对，发现每次减半。
❄ CF896E Welcome home, Chtholly
分块，块内用平衡树维护，每次减 $-x$ 将数分成 $[1,x),[x,2x],(2x,\max)$，第一段不用动，第二段暴力合并，第三段打标记。
时间复杂度 $O(n^2\log n+n\sqrt{n}\log n)$，不知道能不能过。
突刺贯穿的第二分块，过不了，怎么成废物了？分块，记最大值为 $v$，分讨
- $x < v$，不用管。
- $v \le 2x$，将 $[x+1,v]$ 的减 $x$。
- $2x < v$，将 $[1,x]$ 的加 $x$，再打一个全局标记。
加减可以并查集维护，时间复杂度 $O(n\sqrt{n})$，优化空间复杂度可以逐块枚举。
🅰 CF914F Substrings in a String
好像可以
bitset暴力，时间复杂度 $O(\frac{n^2}{\omega})$。确实可以。SAM + 分块 + 根号分治，小的部分就考虑块内和块间。
CF464E The Classic Problem
线段树维护二进制距离，线段树二分比较大小。
CF1446D2 Frequency Problem (Hard Version)
众数一定出现，然后根号分治。
🅰 CF666E Forensic Examination
字符串越来越多，我该怎么办？？？
对模板串建立广义 SAM，预处理匹配串的前缀能匹配到的点，倍增找 $[l,r]$ 对应节点，找到第一个满足 $len_u \ge r-l+1$ 的点。
需要查询模板串的区间信息，用权值线段树维护 endpos，合并时线段树合并。
什么时候学字符串？？？
CF997E Good Subsegments
见第一题。还有析合树做法？
CF603E Pastoral Oddities
$n$ 是偶数。唉唉唉。。。
存在合法方案当且仅当连通块大小为偶数。
整体二分，答案有单调性，求出 $mid$ 的答案然后分治。
CF576E Painting Edges
怎么降紫了，线段树分治。
CF176E Archaeology
支持单点修改，维护最大连通子树，用
set就行。❄ CF1458D Flip and Reverse
画出折线图，发现相当于找一段区间进行翻转，建出图来就是一个环逆方向走，求出字典序最小的欧拉路径即可。
关于字典序最小的欧拉路径，排序后直接做就行了，题解都在干什么？？？
srds，我的数据结构呢？？？
🅰 CF587F Duff is Mad
字符串越来越多，我该怎么办？？？
SAM + 根号分治，我不会字符串啊。
🅰 CF1037H Security
字符串越来越多，我该怎么办？？？
CF1616H Keep XOR Low
字典树上 DP
❄ CF1491H Yuezheng Ling and Dynamic Tree
弹飞绵羊，分块每个点维护第一次跳出块后达到的点 $to$。
考虑修改，散块直接 $O(\sqrt{n})$ 重构，整块发现减 $O(\sqrt{n})$ 次后第一次就会跳出块，此时打标记即可。
考虑查询，先跳到同一块，若 LCA 在这个块中那么 $to_i=to_j$，此时暴力跳即可，否则跳到下一个块。
❄ CF1844G Tree Weights
并非水题，这就是数据结构吗？
以 $1$ 为根，记 $a_i$ 为点 $i$ 的深度，有 $a_1=0$。根据限制有 $a_i+a_{i+1}-2a_{LCA(i,i+1)}=d_i$，恰好 $n-1$ 个方程。
shenmi，先计算 $a’_i=a_i\%2$ 的值，有 $a’_{i+1}=d_i-a’_{i}$，再考虑 $a_i \% 4$，有 $a’’_{i+1}=a’’_i-a’_{LCA(i,i+1)}$，以此类推。
❄CF1017G The Tree
初始点权为 $-1$，操作一单点加 $1$，查询询问点到根节点的最大后缀和即可，对于操作二，即令最大后缀和为 $-1$，单点减 $qry+1$ 即可。
❄ CF1628E Groceries in Meteor Town
kruskal 重构树，找所有白点和给定点的 LCA。
🅰 CF1063F String Journey
CF150E Freezing with Style
显然二分，权值 $> 0$。树上路径你不想点分治想啥？
单调队列可以去掉一个 $\log$。
CF1320E Treeland and Viruses
建虚树然后 dij。
CF1476F Lanterns
数据结构是吧？
CF407E k-d-sequence
不重，同余，$\frac{mx-mn}{d}-(r-l) \le k$。扫描线。
❄ CF1707E Replace
❄ CF1270H Number of Components
发现若 $i,j(i<j)$ 连通，那么它们中间的点也和它们连通，于是连通块是一段区间，连通块数量相当于计算 $[1,p],[p+1,n]$ 没有连边的 $p$ 的数量。
考虑切片，枚举 $v$，将 $a_i$ 变为 $[a_i \ge v]$，相当于计算形如 $0…01…1$ 的数量，令 $a_0=\infty,a_{n+1}=-\infty$ 那么至少有一个 $01$，线段树维护 $01$ 的最小值及其个数即可。
CF453E Little Pony and Lord Tirek
相当于对时间进行推平，分块能做到 $O(n\sqrt{n\log n})$，能过吗？
可以离线下来，相当于二维偏序，时间复杂度 $O(n\log n)$。
哦，分块可以做到 $O(n\sqrt{n})$。
哦，主席树可以做到在线 $O(n\log n)$。
CF1119F Niyaz and Small Degrees
建虚树，贪心选点 DP 即可，时间复杂度 $O(n\log n)$。
所以虚树为啥是数据结构？
CF679E Bear and Bad Powers of 42
直接做，均摊是对的。
❄ CF571D Campus
好可以分块，块大小 $\le \sqrt{n}$ 时暴力，大于后不合并直接打标记，时间复杂度 $O(n\sqrt{n})$，不知道能不能过。过不了吧，不过可以支持复杂操作。
把合并离线下来，形成两棵树，每次进行子树叶子加和赋值为 $0$。求最后一次赋值的时间可以 DFS +
set，求值可以 DFS + 树状数组，时间复杂度 $O(n\log n)$。CF319E Ping-Pong
将相交不包含的区间合并，最终 $u$ 能到 $v$ 当且仅当 $(L_{S_u},R_{S_u})$ 与 $(L_{S_v},R_{S_v})$ 包含。插入一个区间后查询包含 $l,r$ 的区间进行合并即可，实现类似线段数分治。
❄ CF1621G Weighted Increasing Subsequences
先求逆排列，然后正难则反，最后正着反着分别 DP 一次即可。
CF793F Julia the snail
扫描线，这是经典的吉司机线段树。还能回滚莫队？
CF786E ALT
唐氏树链剖分优化网络流建图。
CF1286D LCC
可能的答案只有 $O(n)$ 种，枚举答案可以 $O(n)$ DP，动态 DP 即可。
CF1076G Array Game
动态 DP。
CF1368G Shifting Dominoes
建图，然后矩形并。
CF1476G Minimum Difference
就莫队吧，时间复杂度 $O(n^{\frac{2}{3}}m)$。
CF650E Clockwork Bomb
好像直接做就是对的？
还真是，可以 LCT，不过我不会 LCT 啊。
❄ CF633H Fibonacci-ish II
$O(n^2)$ 桶排就行了。
可以莫队 + 线段树维护矩乘。
❄ CF1656H Equal LCM Subsets
$\gcd$ 就是全选。
先质因数分解，若存在 $a$ 中的某个数，使得其质因数分解的某个质数的次幂大于 $b$ 中该质数次幂的 $\max$，那么这个数不能选，将其删去。如果 $a,b$ 中都不存在这样的数且均非空，那么选择这两个集合合法。
如果下式成立，那么 $a_j$ 要删去
需要单点修改求全局 $\gcd$，线段树维护，时间复杂度 $O(n^2\log n\log V)$。
🅰 CF1286E Fedya the Potter Strikes Back
CF696E …Wait for it…
树剖板子。
❄ CF1920F2 Smooth Sailing (Hard Version)
考虑立一条从岛屿到边缘的线，那么路线合法当且仅当路线穿过线奇数次。
建出 kruskal 重构树即可。
CF1340F Nastya and CBS
维护右括号左括号的哈希值，单侧递归线段树。
❄ CF1175G Yet Another Partiton Problem
cdq 分治 + 斜率优化。
❄ CF757G Can Bash Save the Day?
主席树 + 树链剖分，每次交换只需重构一棵主席树。
CF626G Raffles
不带修直接贪就是对的，因为函数单调递减。
猜测加减 $1$ 变化不大，堆？两个堆就行。
可以证明最多变化 $1$。
CF1172F Nauuo and Bug
扫描线 + 平衡树。可以直接合并，不用势能分析，势能分析是 $\log^2$。势能分析好像不对，错误的。是低贱的离线做法。
有在线版本（P5609 [Ynoi2013] 对数据结构的爱）CF1936D Bitwise Paradox
经典只有 $O(\log V)$ 个有用的。
❄ CF1610H Squid Game
先不考虑非祖先后代链，对于祖先后代链，选择一个子树-子树的点可以将该点对覆盖。
贪心选择最深链的最浅点，用树状数组维护，然后判断是否非的都被覆盖然后加 $1$ 即可。
CF1763F Edge Queries
圆方树。
CF1178G The Awesomest Vertex
显然可以转化为序列上的问题。可以求 $\max(\sum a,-\sum a) \times |\sum b|$。然后随便做吧？KTT？分块维护凸包？
哦，还可以分块套李超。还会 KTT 吗？？？
其实有 $|a||b| = |ab|$，更自然点？
CF1458E Nim Shortcuts
不屑了。
❄ CF1495E Qingshan and Daniel
不是，我在干啥啊？
最后一定有一个队伍出完，对出完的每个人先前找与之匹配的另一个队的人即可，用并查集维护。
CF798E Mike and code of a permutation
这个翻译我不好评价。。。
直接线段树求拓扑排序就行了。
❄ CF1034D Intervals of Intervals
二分，然后双指针，线段树维护类似扫描线。
求出最小值 mn，然后求大于 mn 的和及个数，最后加上缺少个数个的 mn。
哥哥，要进来吗 QAQ还是扫描线啊，对每个位置维护 $lst_i$ 表示最后加入的位置，每次进行区间覆盖，$lst_i$ 会造成 $\min(lst_i,lim)$ 的贡献。直接 ODT + 树状数组 就行了吧。
CF1548E Gregor and the Two Painters
找那个啥，代表元。
🅰 CF1482H Exam
❄ CF1774G Segment Covering
让你求减是有原因的。
若线段 X 包含线段 Y，那么 X 选择的贡献为 $0$，可以将其删去。
对于询问 $[l,r]$，先找出 $[l,r]$ 内的线段，左端点最小的是一定要选的，然后若 $l_1 < l_2 < l_3 < r_1$，那么 $3$ 也是不能选的，以此类推，倍增维护。
CF855F Nagini
Segment Tree Beats
❄ CF1329D Dreamoon Likes Strings
新建一个字符串 $t$，如果 $s_i=s_{i+1}$ 就将 $s_i$ 放入 $t$ 中，然后有两种操作，删相邻不同的和删一个。
❄ CF700D Huffman Coding on Segment
首先得会 huffman 编码，对 $k$ 个字符构建 huffman 树就是有 $k$ 个叶子的二叉树，记 $c_i$ 为第 $i$ 种字符的出现次数，$d_i$ 为深度，那么编码总长度为 $\sum c_id_i$，使其最小可以贪心 + 堆，每次取最小的两个合并。
对于本题，首先要求出出现次数，可以莫队。然后考虑贪心，发现总出现次数为 $r-l+1$，于是根号分治，对于次数 $
❄ CF1137F Matches Are Not a Child’s Play
摆了。
CF1637H Minimize Inversions Number
奇妙结论。
❄ CF1523G Try Booking
注意到当限制为 $x$ 时，最多加入 $\frac{n}{x}$ 个区间。于是暴力找是对的！
从大到小枚举 $x$ 这样相当于加入区间，可以先找到 $[1,n]$ 中编号最小的区间加入，然后递归计算。找区间用树套树维护即可。
CF1344E Train Tracks
怎么是这题，摆了。
❄ CF1583G Omkar and Time Travel
记 $f_i$ 为 $i$ 区间的传送次数，记 $T(i)$ 为包含 $i$ 的区间集合，有
对于集合 $S$，找到右端点最靠右的区间 $x$，那么 $l_i < l_x \wedge r_i < r_x$ 的 $k$ 变为必须走的，形成子问题。扫描线树状数组维护即可。
CF1787G Colorful Tree Again
艹艹艹，读错题了。
一个点最多在一种路径的中间，其他都是 LCA。于是变成区间加减找最小值对应的最大值。
🅰 CF1535F String Distance
❄ CF827F Dirty Arkady’s Kitchen
奇偶拆点，考虑 dij，状态相当于 $(u,l,r)$ 表示 $[l,r]$ 可以到达这个点（奇偶意义下），然后枚举出边按 $l$ 从小到大枚举，每条边只用枚举一次，时间复杂度 $O(m\log m)$。
❄ CF1209G2 Into Blocks (hard version)
相当于找一些总长度最长的不交的颜色段。DP 可以单次 $O(n)$。
相当于将序列分为尽可能多的段，使得每种颜色只出现在一段中，然后答案就是 $\sum len_i - (众数数量)$。
因为一种颜色出现在一段中，那么可以将个数挂到左端点上，然后就是求 $\max$。对于分段，若染色左右端点为 $L,R$，那么 $[L,R)$ 不能分段，区间加，然后为 $0$ 的就是分段点，线段树随便做。
CF799F Beautiful fountains rows
第一个条件可以容斥掉。可以按 $l,r$ 的奇偶性分讨，然后就是二维求交？扫描线，合法的是一段区间。
还可以随机化？！扫描线右端点赋值为 $0$，那么若区间 $[l,r]$ 满足 $[l,r)$ 中 $1$ 的个数为偶数，那么合法。然后随机化 hash，map 记录一下就行。
❄ CF1693E Outermost Maximums
上界是 $O(n^2)$ 的。$O(n^2\log n)$ 很好做。
发现若一个数被操作，那么它之后是不可能作为被选择的点的，于是变化就是变为左侧比 $v$ 小的最大值和右侧比 $v$ 小的最大值。
按值统计
从大到小枚举，对每个枚举到的值记 L,R,O 表示要选左侧，要选右侧，还是不确定。
当前枚举到的值为 O，O 左边为 O 的都变为 L，右边同理。左边为 R 的都要指向当前的数，计入答案并将其变为 O，右边同理。
发现标记始终形如 L,O,R 维护分段点即可，统计用树状数组。
按位统计
对值域建一个数轴，对于 $i$，将左边的数视为黑色放到数轴上，右边的数为白色，那么操作就变为从 $a_i$ 开始，每次跳到最近的黑点或白点上。
从小到大枚举 $i$，黑白的变化是 $O(1)$ 的，用线段树维护跳入区间是黑/白，跳出区间是黑/白的最少步数即可。
🅰 CF1801G A task for substrings
CF1408H Rainbow Triples
答案上界为 $\frac{cnt_0}{2}$ 所以每个点左右两边只有一个是紧的，相当于二分图匹配，然后求最小割。
❄ CF1648E Air Reform
先用 B 找补图最小生成树，然后建 kruskal 重构树。
❄ CF983D Arkady and Rectangle
扫描线，建线段树，标记永久化，线段树每个节点开一个 set，将区间下放到 $O(\log n)$ 个节点的 set 上。
图上某个点的颜色就是对应叶子节点到根的路径上时间最大的颜色。
若没有删除，那么可以对每个节点维护其到其子树叶子节点路径最大值的最小值，那么可以在插入时简单判断是否被看到。
考虑删除，每个颜色只需被看到一次，在这均摊一下，对每个节点维护子树中没有被看到的颜色的时间最大值，找到后暴力更新即可。
时间复杂度 $O(n\log^2n)$。
CF264E Roadside Trees
可以倒着 DP，这样砍树就暴力做就行了。
暴力进行几轮，这样新加入的树就非常矮了。
比新加入的树矮的树很少，还是暴力。
对横纵坐标分别开一棵线段树即可。
CF1930G Prefix Max Set Counting
CF671E Organizing a Race
CF639F Bear and Chemistry
CF1609G A Stroll Around the Matrix
CF1859F Teleportation in Byteland
方案是先到路径的一个点，然后到离这个点最近的 $1$，倍增维护，时间复杂度 $O(n\log n\log V)$/
❤ CF773E Blog Post Rating
平衡树二分？也可以求 $\min(s+n,a_1+n-1,a_2+n-2,…,a_n)$。
❄ CF1558F Strange Sort
切片转化为 01 序列。每次的答案就是最右边的 $0$ 走到对应位置的时间，枚举最后一个没有和 $0$ 相撞的位置取 $\max$ 即可，线段树维护。
❄ CF533A Berland Miners
wc，我怎么又，注意到最多改变一个点。
CF536E Tavas on the Path
离线，从小到大枚举 $l$，树剖维护答案。
CF436F Banners
分块。
CF1956F Nene and the Passing Game
CF1651F Tower Defense
CF793G Oleg and chess
CF1712F Triameter
CF1523H Hopping Around the Array
