[可持久化平衡树]洛谷5055【可持久化文艺平衡树】题解
题目概述Luogu5055解题报告带tag的可持久化平衡树，Pushdown需要在新建的节点上进行，并且Pushdown需要新建两个儿子，以避免影响之前的信息。好像看到了很多Pushdown在原...
[可持久化平衡树]洛谷3835【可持久化平衡树】题解
题目概述Luogu3835解题报告由于非旋Treap的Split和Merge都是自上而下的操作，因此可以很方便的可持久化。未解之谜：Split肯定需要新建节点，但是Merge好像并不需要？洛谷这...
[主席树二分+复杂度分析]牛客IOI周赛28-提高组 C【下克上の天邪鬼】题解
题目概述下克上の天邪鬼解题报告顺着 ${\lfloor{a_i\over 2}\rfloor}\le a_j<a_i$ 想，不难想到利用这个 $\lfloor{a_i\over 2}\rf...
[离线+可持久化树+线段树分治+并查集按秩合并+哈希]2022牛客暑期多校训练营8 I【Equivalence in Connectivity】题解
题目概述Equivalence in Connectivity解题报告好像确实有维护动态图的方法……但是可能是考场上写不出的那种……考虑离线，建出可持久化树，如果用并查集维护图的连通性，会发现不...
[KMP+后缀数组+主席树]2022牛客暑期多校训练营6 L【Striking String Problem】题解
题目概述Striking String Problem解题报告神仙题，根本想不到。记 $n$ 为 $S$ 长度，$m$ 为 $T$ 长度，$U_i$ 表示 $S[l_1,r_1]+\cdots+...
[差分+二分+主席树]2021牛客暑期多校训练营7 K【xay loves sequence】题解
题目概述xay loves sequence解题报告先对数组差分，令 $c_i=a_i-a_{i-1}$ 。每次区间加或者区间减就是对 $c$ 的两个位置 $+1$ 和 $-1$ ，所以不难发现...
[主席树求区间mex]Codeforces1436E【Complicated Computations】题解
题目概述CF1436E解题报告呜呜呜，忘了区间mex可以用主席树做了QAQ。开 $n$ 个权值主席树，第 $i$ 棵树记录 $1\sim i$ 中 $x$ 最后一次出现的位置 $pos_x$ 。...
CodeChef April Challenge 2019 Division 2
上次打完之后分数还是不够Div1……只能再打Div2。UPD：这次打完分数还是不够QAQ。Maximum Remaining去重后第二大。#include<cstdio>
#incl...
[主席树+哈希]HackerRank(101 Hack 49)【Sorting Lists】题解
题目概述有 $n$ 条线段 $(a_i,b_i)$ ，定义 $C(i)$ 表示包含 $i+{1\over 2}$ 的有序线段列表，求字典序第 $K$ 小的 $C(i)$（相同列表不重复计算）。解...
[霍尔定理+主席树+复杂度分析+DP]HHHOJ197【古明地】题解
解题报告题解里有个很厉害的 $O((n+s)log_2n)$ 做法，但是我不会……我只会这种比较好想的做法。首先这明显是一个二分图完全匹配问题，我们可以把每项工作 $K_i$ 看成 $K_i$...
