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