Contest Info

practice link

Solutions

A. The Fair Nut and the Best Path

题目大意：给你一棵树，每个点和每条边都有非负的权。现在要你从一个点走到另一个点，经过点时代价会加上点权，经过边时会减掉边权，要求任意时刻代价不能为负，求最大代价。

题解：注意到代价非负的条件不影响最大值。如果一条路径走到中间某点代价为负，那么从这个点开始走答案会更优。简单 DFS 一下即可。

B. The Fair Nut and Strings

签到题。

C. Max Mex

题目大意：有一棵树，每个点有一个点权，点权是 \(0\sim n-1\) 的一个排列。定义一条链的价值为链上所有点权的 \(mex\)。现在有两种操作，一种是交换两个点的权，一种是询问所有链的价值的最大值。

题解：显然二分。若 \(0\sim x\) 的所有点不能被一条链包含，而 \(0\sim x-1\) 可以，那么答案为 \(x\)。问题变为如何快速判断 \(0\sim x\) 是否可以被一条链包含。我们用一棵线段树来维护这个信息即可。

D. The Fair Nut’s getting crazy

题目大意：给你一个长度为 \(n\) 的数列，定义一个区间对 \([l_{1},r_{1}],[l_{2},r_{2}]\) 是好的，当且仅当这两个区间相交且互不包含，并且 \([l_{2},r_{1}]\) 中的任何元素在 \([l_{1},r_{1}],[l_{2},r_{2}]\) 中分别只出现一次。求好区间的数量。

题解：我们枚举 \([l_{2},r_{1}]\) 后，显然只要把其中每个元素左边第一个相同的出现取个 \(\max\)，就是 \(l_{1}\) 的下界，右边同理。我们从大到小枚举 \(l_{2}\)，对 \(r_{1}\) 用线段树维护一堆东西（写一下式子就知道要维护什么），非常难写。

E. The Fair Nut and Rectangles

简单斜率优化 \(dp\)。

F. The Fair Nut and Amusing Xor

题目大意：给你两个长度为 \(n\) 数列 \(a\) 和 \(b\)，每次你可以对 \(a\) 中一个长度为 \(k\)（给定）的区间中的每个数异或上 \(x\)（自己选）。问 \(a\) 能否变成 \(b\)，若能，至少操作多少次。另外有 \(q\) 个询问，每次改变 \(a\) 或 \(b\) 中的一个位置。

题解：显然我们把 \(a\) 和 \(b\) 异或起来（记为 \(c\)），就是问 \(c\) 能否全变成 \(0\)。我们对 \(c\) 求一个异或差分，每次操作就是同时修改差分中两个相距 \(k\) 的位置。我们把位置按照膜 \(k\) 分类，那么就把问题归约到了 \(k=2\) 的情况。

\(k=2\) 时，能够变为 \(0\) 等价于整个数列的异或和为 \(0\)，操作次数是 \(c\) 的所有前缀中非零的数量。

维护 \(c\) 的前缀时我们采用根号分块。每块我们记录一个 offset，对于修改区间两端的块暴力重构即可。