前言

寒假康复训练Day1,差点爆零了qwq。

题解

C - Konrad and Company Evaluation

题目要求维护,修改是把指向某个点的入边全部改成出边。
考虑对点按照度数不升序排序,那么我们尝试分成两部分来做。
1.对于位于左边的点,与相连的点必不可能超过。若超过,则说明有超过个点在左边且他们的度数都大于,总度数也大于,显然矛盾。因此,我们每次最多将条从左往右的边改成从右往左。
2.对于位于右边的点,我们这样考虑:刚开始从右指向左的总边数不超过,且每次修改最多新增条,那么显然总共出现过的从右往左的边数不可能超过,这一步修改的总边数也不超过这个数。
维护每个点的入边,每次暴力修改完清空即可,总的复杂度为

D - Wojtek and Card Tricks

因为最多种排列嘛,所以预处理一个表示第种排列(点)经过第种排列(边)之后得到的新排列(点)。
如果把排列看做边的话,那就是点经过范围内的边,能到达的点的个数。
枚举左端点,按顺序枚举每个没有访问到点,添加新的边,由于每次添加新的类型的边都会使被访问到的点的个数至少翻倍,因此最多添加条,每次枚举个顶点暴力添加,暴力搜索新的被访问到的点。
总的复杂度