主要是 $\tt pbds$ 有很多封装好了的小常数代码，比自己手写会方便很多。 头文件 #include<bits/extc++.h>，需要使用命名空间 __gnu_pbds 平衡树【模板】普通平衡树 - 洛谷 $\tt STL$ 容器：tree 123tree<Key, Mapped, Cmp_Fn = std::less<Key>, Tag = rb_tree_tag, Node_Update = null_tree_node_update, Allocator = std::allocator<char> > Key: 储存的元素类型，如果想要存储多个相同的 Key 元素，则需要使用类似于 std::pair 和 struct 的方法，并配合使用 lower_bound 和 upper_bound 成员函数进行查找 Mapped: 映射规则（$\tt Mapped-Policy$）类型，如果要指示关联容器是 集合，类似于存储元素在 std::set 中，此处填 ...

Problem - 1508D - Codeforces 首先将 $a_i$ 放到排列上去，考虑对于 $a_i \to i$ 进行连边，本质上又是置换的情况。 考虑对于置换进行操作，对于同一个置换环进行一次交换就可以将环归位而且不会相交。 考虑对于 $(u, v)$ 在不同的环中，我们使用交换本质上就是将两个环合并到一起，但是如何保证不会出现相交的情况。 最终肯定是只有 $1$ 个环，然后来进行操作。 对于凸包的情况考虑随便选择一个点，之后其他点和当前点连线肯定是不相交的，所以我们合并环的操作只能使用相邻两个点。显然我们交换相邻两个点是肯定可以使其变成一个环的。 如果不是凸包的话，发现随便画个图就去世了。 如果发现不对的情况，可以先考虑什么情况是不对的，看看能不能进行处理。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828 ...

Problem - 1290D - Codeforces $\text{my solution}$不妨考虑初始答案为 $n$，发现一个数是出现过的直接让答案 $-1$。 我们考虑如何查看一个数是出现过的。 我们先尝试能否让一个数和其他所有数进行匹配，考虑一个数消耗的次数是 $\frac{n- 1}{k -1}$。为了钦定顺序我们考虑位置 $i$ 只和位置在其前面的数进行匹配。 发现直接暴力匹配的话如果 $K$ 比较大会浪费掉很多查询次数，所以考虑如何利用 $K$。 如果考虑钦定了顺序，对于 $i \le K$ 的部分我们可以一次全部查完。 其次我们发现重置队列对于查询次数的影响还是很大的，能不能尽量少重置队列。 只要一个数没有出问题，其查询队列中可以包含符合范围的任意数。 如果后面的数和当前的数是不同的，查询队列是允许出现后面的数的。 注意每次加入数的时候可能会弹出数。 看看能不能倒着查询，就是让每个数被查询，考虑需要查询同一个块内的所有数，我们加入块之后。逐步加入原来的数。我们考虑同一块内的数倒着加入，然后依次查询前面的一个块。 我们只要保证块内的数互不相同，而且加入的数互不 ...

Problem - 1060F - Codeforces 考虑每个数如果被选择为最终的答案，要么是操作没有选择与其相连的边，要么是操作了这个边用 $\frac{1}{2}$ 的概率活下来了。 首先总边数是每次减少 $1$ 的，一个点被选择的概率只和该点周围连接了几条边有关。 设 $f(u, j)$ 表示在 $u$ 的子树中，对于所有删边顺序只对最后 $j$ 条边选择存活节点，根节点的编号仍然是 $u$ 的概率，节点 $u$ 的答案是 $\frac{f(u, n-1)}{(n-1)!}$。 考虑合并 $(u, v)$，我们只需要考虑 $u$ 还有 $v$ 的子树，我们同样设边的状态为 $g(i)$ 和上文相同。 枚举 $(u, v)$ 在什么时候被删除。 如果 $j \le i$ 意味着边收缩完成之后，新的编号已经确定，所以必须选择 $u$ 概率为 $\frac{1}{2}$，同时因为 $(u, v)$ 已经合并，所以最后的 $j -1$ 条边都需要选择 $u$，也就是选择 $v$。转移为： $g_i \leftarrow f(v, j - 1) \times \frac{1}{2}$。 ...

Problem - 1310E - Codeforces 考虑倒推，每个数具体是啥是不知道的，但是我们可以知道数的种类。 本质上对于集合中的每一个元素，就代表一种不同的元素。 如果进行一次逆变换，元素种类就会变成原来集合 $\sum a_i$。 一开始是有限定的，集合大小小于等于 $n$。 先处理 $k = 1$ 的情况：划分数 $\tt Dp$。 $k = 2$ 的情况，就是考虑需要倒推两次，不妨考虑当前集合是 $c$，考虑 $b$ 中出现次数为 $c_i$ 的数是 $v_i$，可以得到 $\sum c_i v_i \le n$。 我们只需要考虑其存在性即可，我们不妨让 $c_i$ 递减，之后 $v_i = i$。这样可以取到最小值。 所以我们只需要满足 $\sum c_ii \le n$ 即可，考虑进行 $\tt Dp$ 因为钦定了 $c_i$ 的关系，我们需要二维的状态复杂度 $O(n ^ 3)$，但是事实上我们钦定 $c_i$ 所以只需要枚举差分值就行了。考虑再推式子。 我们让 $t_i = c_i - c_{i + 1}$。 $$\be ...

Problem - 1620F - Codeforces 二分图本质上就是没有奇环，注意给定的是一个排列。 考虑什么时候会出现奇环，考虑如果 $(i, j), (j, k)$ 那么必然存在 $(i, k)$ 这样就去世了。 也就是如果存在 $(i, j)$ 那么 $\forall k \in [j + 1, n], a_k \ge a_j$。 我菜了。 既然结论已经想到这个份上了，直接考虑 $\tt Dp$。 我们注意结论：序列中不存在 $i < j < k, p_i > p_j > p_k$。 考虑进行填数设 $f(i, x, y)$ 表示填了 $i$ 个数，最大值为 $x$，已经填好的逆序对末尾的最大值为 $y$，能否没有奇环。 考虑优化状态，对于两个序列 $p_1, p_2$ 在相同的 $x$ 下选取较小的 $y$ 更加有潜力。 显然对于 $(i, y)$ 是固定的，$x$ 越小序列越容易合法。 考虑将状态变成 $f(i, x)$ 表示能取到的最小的 $y$。 如果不合法就是 $+\infty$。 转移方程，设 $z = \pm p_{ ...

Problem - 1603E - Codeforces 虽然是再论但是是一点题解的印象都无了。 首先从小到大开始考虑，对于这样的一个序列事实上我们可以任意排列，答案就是： $$\frac{n!}{\prod_{i} c_i!}$$ 其中 $c_i$ 表示一个数重复出现的次数。 发现做不下去了，考虑找找性质。 不妨考虑区间 $[l, r]$ 那么需要满足 $a_l \times a_r \ge sum_r - sum_{l - 1}$。 考虑对于同一个 $r$，$l$ 越小限制越强。 对于该序列只要前缀是合法的答案一定是合法的。 直接考虑 $\tt Dp$ 需要枚举第一个数，然后记录前缀和。 复杂度是 $O(n\times n^3\times n)$ 是过不去的。 考虑是否还有性质，不是很好找，那么考虑压缩状态，如果考虑前缀和第一个数不论转移的复杂度就已经是 $O(n^4)$ 了。 所以考虑能不能少枚举一些东西，前缀和是不能省掉的，考虑能否倒叙枚举，发现如果 $a_n \le n - 1$ 就去世了。所以 $a_n = n, n + 1$。 可以省略掉一维了，但是算上 ...

Problem - 1299D - Codeforces 切了，但是没有完全切。 有的时候还要打表一下证明一下结论。 md 不用打表，直接算就行了，之前直接感觉就是 $2^x$，比较大。 好吧，之前写过，严谨地说是抄过。现在能想到了还是挺好的。 打表得到线性基本质不同的个数为 $374$ 个。 考虑合并连通块就是线性基之间的转移，直接设 $f(i)$ 表示当前是第 $i$ 个线性基的方案数。 转移的时候保证线性无关就行了。 之后考虑三元环的情况： 因为没有重边所以没有二元环。 都是有 $2$ 条边连接节点 $1$，考虑分类讨论一下： 不选择，方案数为 $1$。 选择 $1$ 条边，随便选择即可方案数为 $2$。 选择两条边，加上当前线性基，方案数为 $1$。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283 ...