• 給 \(N\) \(\small(1 \le N \le 2000)\) 個數字 \(a_i\) \(\small(0 \le a_i \le 10^6)\)
• 可以把原序列切成 任意段
• 求每一段的中位數之和的 最大值
• 有 \(T\) \(\small(T = 100)\) 筆測資

Subtask

• \([20]\) \(N = 1\)
• \([50]\) \(N \le 100\)
• \([30]\) \(N \le 2000\)

Subtask 1 (\(N = 1\))

• 數列長度只有 \(1\)，所以也只有一種切法
• 直接輸出 \(a_1\) 就可以了

\(\color{red}{WA}\) \((20/100)\)

小性質

• 經由 Subtask 1 可以發現，一個數字的中位數就是他自己
  • 所有數字都 \(\ge 0\)？
  • 直接輸出所有數字的和！

\(\color{red}{WA}\) \((70/100)\)

• 好像忘了什麼？
  • 還要對 \(10^9 + 7\) 取餘數

\(\color{lime}{AC}\) \((100/100)\)

• \(2N\) \(\small(2 \le N \le 3 \times 10^5)\) 個人分成黑白兩隊
  • 黑隊每個人有一個數字 \(a_i\) \(\small(1 \le a_i \le N)\)
  • 白隊每個人有一個數字 \(b_i\) \(\small(1 \le b_i \le N)\)
• \(\forall 1 \le i \le N\) 比較 \([\min(a_i, b_i), \max(a_i, b_i)]\) 區間裡面哪一隊數字大的比較多

Subtask

• \([23]\) \(N \le 2000\)
• \([20]\) \(1 \le a_i, b_i \le \min(N, 2000)\)
• \([16]\) \(a_i = 1\)
• \([41]\) \(N \le 3 \times 10^5\)

Subtask 1 (\(N \le 2000\))

• 咦？好像可以暴力？
  • 寫寫看吧，反正又不虧

\(\color{cyan}{TLE}\) \((23/100)\) 或 \((43/100)\)

Subtask 2 (\(a_i, b_i \le 2000\))

• 每次詢問的範圍跟上面那筆一樣ㄟ
  • 總共的詢問大約有 \(\frac{2000^2}{2} = 2 \times 10^6\) 種，不如先把他存起來吧

• 枚舉左界 \(1 \le L \le \min(N, 2000)\)
  • \(\forall L \le R \le \min(N, 2000)\) 求出區間 \([L, R]\) 的答案

\(\color{red}{WA}\) \((43/100)\)

Subtask 3 (\(a_i = 1\))

• 好像跟上面那筆差不多呢
  • 總共的區間只有 \(3 \times 10^5\) 種，也可以先算出來

• \(\forall 1 \le i \le N\) 處理出編號 \(1 \sim i\) 的答案

\(\color{red}{WA}\) \((16/100)\)

• 加上前面的就有 \((59/100)\)

性質一

• 每次對戰的結果都是固定的
  • 很好證明ㄅ
  • \(a_i\) 跟 \(b_i\) 都不會改變

• 既然是固定的那是不是可以預處理呢？
  • 但是狀態數高達 \(4.5 \times 10^{10}\) 種？

性質二

• 區間 \([L, R]\) 對戰的結果等於 \([1, R]\) 的結果扣掉 \([1, L-1]\) 的結果
  • 假設前 \(10\) 分鐘我得了 \(7\) 分，且前 \(4\) 分鐘我得了 \(3\) 分，請問第 \(5 \sim 10\) 分鐘我總共拿到幾分？

• 只要處理出所有 \([1, i]\) 的情況就可以了！
  • 黑隊勝場數
  • 白隊勝場數
• 詢問 \([L, R]\) 的時候就用 \([1, R] - [1, L-1]\) 的結果來判斷

• 時間複雜度 \(O(N)\)！

\(\color{lime}{AC}\) \((100/100)\)

• 這種技巧叫做前綴和，是競賽中常出現的咚咚ㄛ

• 你需要模擬一個 queue
• 有 \(Q\) \(\small(1 \le Q \le 5 \times 10^5)\) 次操作
  • 把所有值加上 \(k\) \(\small(1 \le k \le 10^6)\)
  • 把前面的 \(x\) \(\small(1 \le x \le 10^6)\) 個數字 pop 掉
  • 在最後面加入 \(y\) \(\small(1 \le y \le 10^6)\) 個 \(0\)
• 每次操作完都要求出 queue 裡面的最大值

Subtask

• \([9]\) \(Q \le 1000\)，\(x = y = 1\)
• \([8]\) 沒有 pop 的動作
• \([35]\) \(y = 1\)
• \([19]\) \(Q \le 1000\)，\(\sum{y} < 2^{31}\)
• \([29]\) \(Q \le 5 \times 10^5\)

Subtask 1 (\(Q \le 1000\)，\(x = y = 1\))

• 直接暴力 ><

\(\color{cyan}{TLE} / \color{orange}{RE}\) \((9/100)\)

Subtask 2 (沒有 pop 的動作)

• 最大值會是誰？

• 第一個人一定有最多片口罩
  • 他最一開始就在那裡，而且每次發口罩都會給到他
• 把所有 \(k\) 加起來就好

\(\color{red}{WA}\) \((8/100)\)

• 加上前面的是 \((17/100)\)

小性質

• queue 裡面的數字一定非嚴格遞減
  • 後面的人比較晚來怎麼可能會拿到更多東西？

• 每次求最大值可以輸出 queue.front() 就好！

Subtask 3 (\(y = 1\))

• 人數不會超過 \(5 \times 10^5\)
  • 每個人最多只會進一次 queue 也只會離開一次 queue
  • 操作 \(2\)、\(3\) 可以暴力
• 詢問目前也可以做到 \(O(1)\)
• 不過第一種操作要怎麼辦？不能用迴圈直接跑吧

• 運用剛才提到的前綴和想法
  • 如果只把答案紀錄在第一個人跟最後一個人身上
  • 要把第一個人 pop 掉的時候再把答案傳下去？

• front 表示最前面的人的編號，back 表示最後面的人的編號
• ans[i] 表示第 \(i\) 個人的答案
• 每次對所有人發口罩就 ans[front] += k, ans[back+1] -= k
• 當操作二中，第 \(i\) 個人要被丟掉的時候就 ans[i+1] += ans[i]

\(\color{orange}{RE}\) \((44/100)\)

• 合起來是 \((52/100)\)

• 感覺已經很接近正解了？
  • 是的，沒錯
• 感覺如果總共的人數不會超過 \(10^6\) 就可以做掉了？
  • 是的，沒錯

• 教個小技巧：離散化
  • 如果數字很大，但是其實重要的只有數字間的相對關係那就可以使用
  • 例如說：\([77, 10, -9, 6, 10]\) 就可能被離散化成 \([4, 3, 1, 2, 3]\)
• 實作上可以先把所有數字存到陣列裡
• 對陣列進行排序，把一樣的數字去掉
• 再對每個數字二分搜他是第幾大的

• 要怎麼應用到這題ㄋ

• 先重新定義：
  • front 表示最前面的人的編號，back 表示最後面的人的編號 \(+1\)
    • 注意這個 \(+1\)，剛剛操作中真正用到的不是 back 而是 back+1
• 先把所有數字存下來
  • 紀錄每次操作完的 front 跟 back
• 離散化~~~

• 咦？這樣就做完了？
  • 是的，沒錯

\(\color{lime}{AC}\) \((100/100)\)

• 給你一棵 \(N\) \(\small(2 \le N \le 10^5)\) 個點的樹
• 小 Y 跟小 P 分別在點 \(1\) 跟點 \(N\)
• 輪流往相鄰的地方移動，但是不能移動到有人走過的點
• 不能走的就輸了
• 問你誰會贏

Subtask

• \([27]\) \(N \le 300\)
• \([9]\) \(u_i = i\)，\(v_i = i+1\)
• \([16]\) 點 \(1\) 跟點 \(N\) 相鄰
• \([48]\) \(N \le 10^5\)

Subtask 2 (\(u_i = i\)，\(v_i = i+1\))

• 圖大概長那樣

• 每個人的走法都是固定的
  • 判奇偶性就好 ><
    • \(N \equiv 1 \pmod{2}\) 就是 \(\texttt{Little Y}\)
    • \(N \equiv 0 \pmod{2}\) 就是 \(\texttt{Little P}\)

\(\color{red}{WA}\) \((9/100)\)

Subtask 3 (點 \(1\) 跟點 \(N\) 相鄰)

• 小 Y 跟小 P 的移動不會對對方造成策略上的改變
  • 只要計算出小 Y 跟小 P 最多能走多少步再比較即可
  • 從點 \(1\) 跟點 \(N\) 各 dfs 一次

\(\color{red}{WA}\) \((16/100)\)

• 這樣就有 \((25/100)\) 了

小性質

• 注意到只有 \(1 \sim N\) 的那條路徑上才是有意義的
• 如果其中一個人離開那條路徑那答案就確定了

官解 - dp

• 把樹壓成序列，\(d_i\) 表示「從 \(1 \sim N\) 路徑上的第 \(i\) 個點離開最多可以再走幾步」
  • 最多可以再走幾步 \(\Leftrightarrow\) 子樹深度
• 依序去看小 Y 在路徑上走 \(i\) 步之後離開會不會獲勝、小 P 在路徑上走 \(i\) 步之後離開會不會獲勝
  • 可以就直接輸出解答

\(\color{lime}{AC}\) \((100/100)\)

• 給定 \(N\) \(\small(1 \le N \le 10^5)\) 個點的權重 \(a_i\) \(\small(0 \le a_i \le 10^7)\)
• 在兩個城市 \(i\), \(j\) 之間建邊的花費是 \(a_i + a_j\)
• 將其中 \(M\) \(\small(0 \le M \le 10^5)\) 條邊 \((u_i, v_i)\) 的價格改成 \(w_i\)
• 求最小生成樹權重

Subtask

• \([19]\) \(N, M \le 1000\)
• \([6]\) \(M = 0\)
• \([13]\) \(w_i \le a_{u_i} + a_{v_i}\)
• \([41]\) \(a_1 \le a_2 \le \dots \le a_N\)
• \([21]\) \(N, M \le 10^5\)

Subtask 1 (\(N, M \le 1000\))

• 暴力啦，暴力
• \(O(N^2)\) 建邊做 MST

\(\color{cyan}{TLE}\) \((19/100)\)

Subtask 2 (\(M = 0\))

• 沒有特殊權重的邊
• 所有點都要被連到一次
  • 都連到權重最小的就好啦 o(￣▽￣)ブ

• 把點權 sort 之後輸出 \((a_1 + a_2) + (a_1 + a_3) + \dots + (a_1 + a_N)\)
  • \(= a_1 \times (N-2) + (a_1 + a_2 + a_3 + \dots + a_N)\)

\(\color{red}{WA}\) \((6/100)\)

• \((25/100)\) GET！

Subtask 3 (\(w_i \le a_{u_i} + a_{v_i}\))

• 顯然答案只會比 \(M = 0\) 的情況更好
• 把點權最小的點到其他所有點，以及額外的 \(M\) 個限制都一起做 MST

\(\color{red}{WA}\) \((19/100)\)

• 你會拿到 Subtask 2 跟 3
• \((38/100)\) GET！！！

官解 - priority queue + dsu

• 假設輸入已經按照點權排序 \((a_1 \le a_2 \le \dots \le a_N)\)
• 把剛剛會用到的邊都丟進去 priority queue 裡面
• 用並查集判斷兩個點能不能連邊

• 不過如果 \(w_i > a_{u_i} + a_{v_i}\) 可能會被丟到很後面，讓邊權比較小的 \(a_{u_i+1} + a_{v_i}\) 跟 \(a_{u_i} + a_{v_i+1}\) 進不來
  • 對每個限制 \((u_i, v_i, w_i)\)，如果 \(w_i > a_{u_i} + a_{v_i}\) 就把 \((u_i + 1, v_i)\) 跟 \((u_i, v_i + 1)\) 也丟進來

\(\color{red}{WA}\) \((47/100)\)

• 你會拿到 Subtask 2 跟 4
• 加起來就是 \((79/100)\) ㄌ ><

• 如果把點權直接排序後面的 \(M\) 個限制會爆掉
  • 存一個 map 來表示本來的第 \(i\) 個數字在 sort 之後被丟到哪裡ㄌ

\(\color{lime}{AC}\) \((100/100)\)

• 給你一棵 \(N\) \(\small(1 \le N \le 3 \times 10^5)\) 個點的樹，每個點都有點權 \(a_i\) \(\small(1 \le a_i \le 2)\)
• 請找出最小的正整數 \(K\) 使圖中不存在一條 簡單路徑 的權值和為 \(K\)。

Subtask

• \([11]\) \(N \le 2000\)
• \([29]\) \(u_i = i\)，\(v_i = i+1\)
• \([7]\) \(a_1 = 1\)，\(a_2 = a_3 = \dots = a_N = 2\)
• \([53]\) \(N \le 3 \times 10^5\)

Subtask 1 (\(N \le 2000\))

• 可以暴力 \(O(N^2)\) dfs 拿到所有點對的距離
• 答案的值最高就是 \(2N\)
• \(\forall 1 \le i \le 2N\)，檢查有沒有點對的距離是 \(i\)。

\(\color{cyan}{TLE} / \color{orange}{RE}\) \((11/100)\)

Subtask 3 (\(a_1 = 1\)，\(a_2 = a_3 = \dots = a_N = 2\))

• 把路徑權值分為 奇數 跟 偶數 來看
• 最長 偶數權值的路徑就是以 \(1\) 為根，\((所有子樹的直徑最大值) \times 2\)
• 最長 奇數權值的路徑就是某條經過點 \(1\) 的鍊
  • 如果點 \(1\) 只有一個孩子，答案就是 \((樹的深度) \times 2 + 1\)
  • 不然，答案就是 \((第一深的子樹深度 + 第二深的子樹深度) \times 2 + 1\)

\(\color{red}{WA}\) \((7/100)\)

小性質

• 注意到一條權值和 \(w > 2\) 的路徑只會有四種形式：
  • \(1 - \dots - 1\)
  • \(1 - \dots - 2\)
  • \(2 - \dots - 1\)
  • \(2 - \dots - 2\)

• 每一種形式都可以經由拆掉一個或兩個端點來構造出權值和 \(w-2\) 的路徑
• 只要找出 權值最大 的奇數跟偶數路徑就可以了

官解 - 樹 dp

• 對每個點維護他往下可以到的最大奇數權值跟最大偶數權值
• 對每個點都更新一次答案
• 做完了 (?)

\(\color{lime}{AC}\) \((100/100)\)