感觉垃圾场，出题人喜欢卡两 ，没意思。

[A Average Walk]

solution

题意：签到，输出 。

做法：

[B Business Stamps]

solution

题意： 的网格图，每个点有个颜色，从给定起点走到给定终点，问所有路径能经过的最少颜色数。

做法：直接暴力状压 bfs 即可，时间复杂度 。

[C Company Layoffs]

solution

题意： 个数，给一个递减序列 ，对每一个 输出 。

做法：单调，时间复杂度 。

[D Denji]

solution

题意：四种操作：一是插入一个数；二是删除一个数；三是使某个数加上一个值；四是查询小于某个数的个数。

做法：离线离散化树状数组。时间复杂度 。

[E Exam Period]

solution

题意：给出若干个不等式或等式，形式形如 ，，问是否存在 满足， 是给定的。

做法：认真分类讨论下，发现就是 2-SAT，时间复杂度 。

[F Fence Painting]

solution

题意：给序列 ， 是循环数组。两种操作，一是区间查询 ，二是区间覆盖，将 的 覆盖到 的 上。

做法：暴力就是两棵线段树，修改的 change 等价于在 的线段树上区间查询，注意到信息是可以标记合并的，即记录左右最大最小和答案可以轻松合并，时间复杂度 ，好像有点卡常。

实际上 的线段树上查询是可以 ，静态区间查询有许多做法，比如猫树。所以就 了。

坑：下传修改标记的时候记得改变初始位置。

[G Gustavos Modern Art]

solution

题意：给出 的网格图，每个格子 的权值为 ，有四种翻折交换方式。修改是翻折，查询是单点值。

做法：可以发现这个翻转可以被表示成一个四元置换，时间复杂度 。

[H Homework]

solution

题意：混合图，问是否能定向后存在环分解。

做法：别想着 dfs 树了，冷静一下，发现环分解的等价条件是欧拉回路，那么就是经典的混合图欧拉回路问题。要求入度等于出度，连成二分图，把未定向的边连向终点，端点连向边，流量均为一，表示谁入度会增加。一个增加另一个就会减少，所以整体差距除以二后就正常了，再起点连向每个点，流量为需要增加的度数即可。跑个最大流，时间复杂度 。

[I Ivan And Mega Queries]

solution

题意：低能出题人写不懂题面。给 个数，每次询问给出若干个下标 ，求 。

做法：一眼最值分治，然后两边算算个数，这样是两个 ，被卡常了。把最值分治改写成笛卡尔树，时间复杂度 ，可以通过。

[J Joyful City]

solution

题意：一棵树，给边定向，出度为 贡献为 ，求最大贡献。

做法：简单 dp 题，考虑 表示 是谁指向谁，转移等价于枚举 ，排序即可。时间复杂度 。

[K Keypad Repetitions]

solution

题意：签到题。

做法：

[L Ladybug And The Bullet Train]

solution

题意：一棵树，从 出发，每个点只能经过两次，若可以抵达 必须抵达 并停止，问最多步数。

做法：模拟，时间复杂度 。