LUOGU_进阶数据结构

二叉堆

P10977 Cut the Sequence：因为DP的值是单调递增的，所以可能的决策点只有最远的合法位置与那些后缀最大值段的左端点，用单调队列+可删除堆（懒标记）做。

如果 \(\exist a<0\) ，怎么做？CDQ优化DP，可以做！！

并查集

P10350 Modernizacja Bajtocji：把二选一的居民放进一个并查集，记录这个并查集里的电脑数，电脑坏了就是删点，若电脑数=居民数，则为1，若电脑数=0，则为0，否则为'?'

P9565 Not Another Path QUery Problem：用并查集看是否存在一条路径使得起末联通

P8026 Bajtocja：在多个图中联通当且仅当在所有图中的代表元素都相同，因为是快速同时比较，可以Hash。

线段树/树状数组

P3801 红色的幻想乡：\(ans=len_ynum_x+len_xnum_y-num_xnum_y\)

P7764 Poklon：离线扫描线

P9561 Colorful Segments：线段树优化DP，对所有线段排序，枚举上一个相异的颜色的区间（因为相异的限制更多，这样更好满足）,对每个颜色建立线段树，动态维护。\(f_i=\sum_{j<i}g_j\times 2^{\sum_{k=j+1}^{i-1}[col_k=col_i][l_k>r_j]}\)

P5524 充满的希望：询问3的值一定源于某次区间复制，直接扫描线维护最后一次被那个覆盖，如果 \(<l\) 则答案为 \(0\)。

字典树

P2536 病毒检测

P9694 New but Nostalgic Problem：统计字典树每一层的节点个数，与 \(k\) 比大小，选择节点数 \(\ge k\) 的最小的层\(-1\)。