前言

應該很多人都知道 CSES problemset 吧，裡面基本上就是經典題大雜燴。而 additional problem 是裡面的最後一章，也是很多人容易遺忘的章節。

個人認為前面章節的題目都算是對應章節的裸題，主要只是讓你知道這類題目最基本的樣子而已。所謂經典技巧當然不是只有這些裸題，有更多經典技巧是只能靠刷題來累積的，additional problem 裡就直接幫你整理出了一大堆，讓你不用從茫茫題庫中尋找，還不會被大主題直接爆雷。除了經典技巧外，這裡一些有趣的梗題與不有趣的構造題，個人還蠻喜歡的。

那這麼好的題單卻查不到一份完整的題解（註：在 2021 年，我不確定現在有沒有了），真是太讓我難過了，所以我就開始寫這篇題解。

順便先提一點，additional problem 的題目不一定會比前面的章節難，裡面也有許多簡單題，可以不用害怕，從解題人數多的題目開始下手，也不用把前面都刷完再來寫這部份。

題目連結

題目

有一個長度為$n$個環形序列，上面有$m$個線段，線段$i$的左右界分別為$l_i, r_i$，因為是環形區間，所以$l_i > r_i$是允許的，現在請在每個線段塗上紅色或藍色，使的每個位置都至少被一個紅色線段與一個藍色線段覆蓋。

subtask

1. $2 \leq n, m \leq 15$，Score 13
2. $2 \leq n, m \leq 100$，Score 20
3. $2 \leq n, m \leq 1000$，Score 22
4. $2 \leq n, m \leq 100000, \forall 1 \leq i \leq m, l_i \leq r_i$，Score 19
5. $2 \leq n, m \leq 100000$，Score 26

CF打了64場終於上紅了

第一次打owo
因為也算是大比賽(? 所以就留一點紀錄ㄅ

第一次的國際賽，雖然不算到非常正式還是留個紀錄好了

賽前

因為可撥疫情，台北遊、捷絲旅和拉麵全部泡湯
原本以為可以睡晚一點是最值得高興的事，但還是6.半就不小心醒了= =
早上也沒做什麼，去買了巧克力和調那超難調的鏡頭位置就開始了

總覺得2!的日記變得混好多OAO

連結

題意

給$n$個二維平面上的點，定義兩點之間的距離為兩點的曼哈頓距離，請輸出前$k$小的點對距離

$1 \leq n, k \leq 250000$

Day 1

早上搭8點半的火車，因為下午4點半才報到，就先在北車附近亂晃
中午ㄘ了拉麵，好好ㄘ

連結

題意

給定一個長度$n$的陣列，有$q$筆詢問，每筆詢問給定$l, r, v$
請找出$l \leq k < r$，區間$[k, r)$和$v$的xor最大值

$1 \leq n \leq 10^4, 1 \leq q \leq 10^6, 0 \leq C < 2^{30}$

連結

題意

裸三維空間最近點對