文章目录
前言
神迹: 模拟赛切掉 A,C,E，但不会 B,D,F。
真就涉及到一丢丢构造和贪心就不会做呗，我是真的菜。
Solutions
A
不难发现，每次操作可以将 a 1 + a 3 − 2 a 2 a_1+a_3-2a_2 a1+a3−2a2 减小或增大 3 3 3。
若令 p p p 为初始时的 a 1 + a 3 − 2 a 2 a_1+a_3-2a_2 a1+a3−2a2，那么：
- 若 p ≡ 0 ( m o d 3 ) p \equiv 0 \pmod 3 p≡0(mod3)，则答案为 0 0 0。
- 若 p ≡ 1 ( m o d 3 ) p \equiv 1 \pmod 3 p≡1(mod3)，则答案为 1 1 1。
- 若 p ≡ 2 ( m o d 3 ) p \equiv 2 \pmod 3 p≡2(mod3)，则可以使 a 1 + a 3 − 2 a 2 = − 1 a_1+a_3-2a_2=-1 a1+a3−2a2=−1，从而答案为 1 1 1。
B
个人主观感觉这是一道神仙题，比 E 难很多倍。
注意到，若存在一个 i i i 使 [ 1 , i ] [1,i] [1,i] 中 1 1 1 的个数与 [ i + 1 , n ] [i+1,n] [i+1,n] 中 0 0 0 的个数相等，那么一步就可以解决问题了。
那若不存在这样的 i i i 呢？对不起，这样的 i i i 永远都是存在的。下面是简要证明：
- 令 x i = ∑ j = 1 i [ a j = 1 ] − ∑ j = i + 1 n [ a j = 0 ] x_i=\sum_{j=1}^i [a_j=1]-\sum_{j=i+1}^n [a_j=0] xi=∑j=1i[aj=1]−∑j=i+1n[aj=0]。
- 不难发现， x n ≥ 0 x_n \ge 0 xn≥0， x 1 ≤ 0 x_1 \le 0 x1≤0 且 x i = x i + 1 − 1 x_i=x_{i+1}-1 xi=xi+1−1 或 x i = x i + 1 + 1 x_i=x_{i+1}+1 xi=xi+1+1。
- 这等价于一个青蛙从某个属于 x x x 轴正半轴（及原点）的点出发，每次将自己的横坐标加 1 1 1 或减 1 1 1，最终到达某个属于 x x x 轴负半轴（及原点）的点。
- 不难发现，这只青蛙必定会在某个时刻经过原点，因此这样的 i i i 必定存在。
特别的，若初始序列已经有序，则只要输出 0 0 0 就足够了。方案构造十分容易，这里不再质数。
总复杂度 O ( ∑ n ) O(\sum n) O(∑n)。
C
为方便叙述，令
[
l
,
r
]
[l,r]
[l,r] 优秀，当且仅当
r
>
l
r>l
r>l 且其中 a 的个数大于 b 和 c 的个数；令区间
[
l
,
r
]
[l,r]
[l,r] 为极小优秀区间，当且仅当
∀
l
≤
l
′
≤
r
′
≤
r
\forall l \le l' \le r' \le r
∀l≤l′≤r′≤r 满足
[
l
′
,
r
′
]
[l',r']
[l′,r′] 不优秀且
[
l
,
r
]
[l,r]
[l,r] 优秀。
通过手玩不难猜出，极短优秀区间的长度不会很大，随便设 k = 50 k=50 k=50 就过了。官方题解说极短优秀区间的长度最大是 7 7 7。
时间复杂度 O ( ∑ k n ) O(\sum kn) O(∑kn)，其中 k k k 为常数，可以通过本题。
D
Observation 1
若 x ⊕ y ≤ min ( x , y ) x \oplus y \le \min(x,y) x⊕y≤min(x,y)，当且仅当 x , y x,y x,y 在二进制表示下的数位相等，即 ⌊ log x ⌋ = ⌊ log y ⌋ \lfloor \log x \rfloor=\lfloor \log y \rfloor ⌊logx⌋=⌊logy⌋。
Observation 2
令 x , y x,y x,y 属于同一个等价类，当且仅当 x ⊕ y ≤ min ( x , y ) x \oplus y \le \min(x,y) x⊕y≤min(x,y)。
则等价类共有 ⌈ log n ⌉ \lceil \log n \rceil ⌈logn⌉ 个，每个等价类的大小分别为 1 , 2 , 4 , 8 , ⋯ 1,2,4,8,\cdots 1,2,4,8,⋯（最后一个等价类的大小较为特殊）。
Solution
不难发现，只要我们将两端属于不同等价类的边删去，那么每个分裂出的连通块中的合法起点总和就是答案。
思考一个极端情况: 对于树上每条边 ( u , v ) (u,v) (u,v)， u , v u,v u,v 均属于不同的等价类。这样合法起点数就是 n n n，达到上界。
那能否构造出来呢？永远都可以！下面以构造方案证明这个性质。
考虑将树上的点按深度的奇偶性分为两类，则每条树边都连接了两个不同类别的点。令第一类的节点个数为 c n t cnt cnt，那么我们可以将 c n t cnt cnt 表示为若干个 2 2 2 的幂次之和，并对于每个拆分出来的 2 r 2^r 2r，在属于该类的节点中填入所有二进制表示下长度为 r + 1 r+1 r+1 的数。第二类的节点填上剩余未填的值即可。
总复杂度 O ( ∑ n ) O(\sum n) O(∑n)。
E
可以发现，当固定了 a , b a,b a,b 之后，答案就是
∑ i = 1 n ∣ ∑ j ∣ i μ ( i j ) ( b j − a j ) ∣ \sum_{i=1}^n \left| \sum_{j|i} \mu(\frac i j)(b_j-a_j) \right| i=1∑n∣∣∣∣∣∣j∣i∑μ(ji)(bj−aj)∣∣∣∣∣∣
构造多项式 F ( x ) , G ( x ) F(x),G(x) F(x),G(x)，其中 F i ( x ) = μ ( i ) F_i(x)=\mu(i) Fi(x)=μ(i)， G i ( x ) = b i − a i G_i(x)=b_i-a_i Gi(x)=bi−ai，且 H = F ⋅ G H=F \cdot G H=F⋅G，则式子可以被写作：
∑ i = 1 n ∣ H i ( x ) ∣ \sum_{i=1}^n |H_i(x)| i=1∑n∣Hi(x)∣
不难发现，当 b b b 变大 1 1 1 后， G 1 ( x ) G_1(x) G1(x) 变大了 1 1 1，对于每个 [ 1 , n ] [1,n] [1,n] 中的 i i i 同时 H i ( x ) H_i(x) Hi(x) 也变大了 μ ( i ) \mu(i) μ(i)。
先设定 b 1 = 0 b_1=0 b1=0。定义一次函数 f i ( x ) = h i + μ ( i ) x f_i(x)=h_i+\mu(i)x fi(x)=hi+μ(i)x，那么一次查询的答案就是
∑ i = 1 n ∣ f i ( x ) ∣ \sum_{i=1}^n |f_i(x)| i=1∑n∣fi(x)∣
不难想到将询问离线下来并按 x x x 从小到大排序，然后考虑 1 , 2 , 3 , ⋯ , n 1,2,3,\cdots,n 1,2,3,⋯,n 对各个询问的贡献，每次先二分找到 f i ( x ) < 0 f_i(x)<0 fi(x)<0 和 f i ( x ) ≥ 0 f_i(x) \ge 0 fi(x)≥0 的分界点并差分进行贡献。
总复杂度 O ( ( n + q ) log q ) O((n+q) \log q) O((n+q)logq)，可以通过本题。
F
咕咕咕
Code
不想放了，自己写吧 /kel