A.矩形异或

50pts

计算二维前缀异或和， 回答询问

70pts

考虑一个值在矩形内出现了多少次

矩形 ，不妨设

则值 出现次数

只关心次数的奇偶性，那就只需求奇数偶数自然数区间和

100pts

对于偶数区间和，每个数最低位都为0，扣掉这一位，转化为自然数

注意到若 ，

所以区间和只需计算不是整段的部分

B.弹钢琴

20pts

枚举排列，跳过坏掉的键

50pts

将所有键以音高为第一关键字，音色为第二关键字升序排序

动态规划 表示已考虑前 个键，敲了第 个键，已敲击的键中最大音色值 ， 亦为第 个键的音色

考虑前一个键

对每个 值维护关于 的前缀最大值

100pts

单点修改，询问前缀最大值，树状数组

C.跑路

0pts

记录深度为 的点数

过不了样例

20pts

每个询问单独处理，每次选收益最大的点走过去

为什么是对的？可以看作费用流模型……

鉴于与正解相关性不大，这里不作赘述

40pts

冷静分析一下，首先每个人都走到叶子注定不劣

故有 的叶子被标记

删去所有叶子，得到子问题

故记

则

80pts

深度递增考虑，每次添加一个深度的所有点

按到根距离自小向大加点，维护

可以发现一个点会更新自它向上的一定距离内的祖先

（根到它的路径的一个后缀）

二分更新到哪里，

100pts

若一个新点更新不了它的一个祖先

则 必已被与它同深度（到根距离）的点更新

故考察同深度点LCA即可，可以Tarjan

std的做法是从LCA处考虑

若 的子树内有 个深度为 的点，则在他们加入时贡献出 个 的点来

仅计数 （长链剖分），复杂度

Std

A

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40791809

B

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40791791

C

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40791796