Codeforces Hello 2023
这次一样八题只解出四题 :(
看来我距离 master 还有很长一段路要走
最后排在 948 名
problem F 最后 WA 在 pretest 13
感觉方法应该是对的，不过不确定，之后再慢慢 debug 吧
A. Hall of Fame
如果是全 L 或全 R 会失败
如果是 LL..LLRRR..RRR 的形式交换边界的 LR 即可
其他情况不用做任何事就成功了
B. MKnez's ConstructiveForces Task
n 是偶数的的话输出 -1, 1, -1, 1, ... 就可以
n 是奇数的话，因为任两个相邻的都是总和
所以一定是 ABABABA 的形式
令总和是 S, 计算之后可以知道
A = (1 - k)S
B = kS
其中 k = n / 2
所以只有 n = 3 时会失败，其他都可以很容易建构出来
C. Least Prefix Sum
可以发现 m 要最小的条件是：
1. 对于所有 j > 1, 都有 sum(a_j, a_{j+1}, ..., a_{m-1}) <= abs(a_m)
2. 对于所有 m < j <= n, 都有 sum(a_{m+1}, a_{m+2}, ..., a_j) >= 0
基本上都用 priority_queue 在不符合的时候挑最有利的那个改方向就可以了
其他有一些 corner cases 注意一下就行（例如要求非空所以 a_1 毫无意义）
D. Boris and His Amazing Haircut
这题我一开始还以为要用 disjoint set 做
后来想一想才发现用 monotonic stack 就可以了
决定切在 i 之后，就一直切到不能切为止，也就是 b[j] > b[i] 时
所以可以用 monotonic stack 做
A 的作用是：
1. 如果 a[i] < b[i] 就直接失败
2. 如果 a[i] = b[i] 则不用切，只需要把不能继续切的 pop 掉
E, F 两题我都有看题目
E 我觉得很有趣，但感觉是蛮复杂的图论就放弃了，之后应该会补写
F 题我倒在 pretest 13, 我觉得大方向是对的就是了，不知哪里写烂了
首先可以发现要让 root 变 0 就一定要让全部人 xor 起来变 0 再做在 root 上
把全部人 xor 的值叫 xsum 好了
有几个有用性质：
1. 做在奇数的 subtree 上不会影响 xsum
2. 做在偶数的 subtree 上会让该 subtree 的 xsum 变 0
3. 如果做在祖先节点，任何做在底下的都变没有用处
因为 0 <= a_i < 32，所以可以 divide and conquer，只要花 32*32 次检查
我是因为比赛时间不够所以直接存一个
array<vector<int>, 32> 来纪录要能 xor 某个值需要的操作
空间有点浪费就是了
最后看有没有办法让整棵树的 xsum 变 0 就可以了
不知道错在哪QQ