pr3pony's magical wonderland
pony is love, coding is life

• problem link
• 有\(N\)個點，每個點有權值，一開始點都不相連，有\(Q\)個操作，強制在線，分兩種：
  1. 把 \(X\) 跟 \(Y\) 連一條無向邊。如果 \(X\) 和 \(Y\) 本身已經直接相連或間接相連，則忽略此操作。
  2. 查詢 \(X\) 到 \(Y\) 的路徑上權值 \( \le K\) 的點的數量。
• 資料範圍：多測資，沒講幾筆，\(N \le 5 \times 10^4, Q \le 10^5\)，權值範圍不重要（？），反正太大的話可以離散化

• Apr 17, 2017

• 繼續閱讀

• problem link
• 題目要求維護一個長度 \(N\) 的序列 \(a\)，會做 \(K\) 次操作，操作有兩種：
  1. 把第 \(i\) 個到第 \(j\) 個元素加上 \(x\)
  2. 查詢第 \(i\) 個到第 \(j\) 個元素中大於 \(0\) 的元素的和
• 資料範圍：\(N \le 10^5, K \le 2 \times 10^ 5, 過程中 -10^{13} \le a[i] \le 10^{13}\)
• 看到第一種操作直覺會想到可以用線段樹之類的做，但第二個操作就爛掉了。
  要找大於 0 的元素和，可以想到把元素由小到大排序後，預處理後綴和， 查詢時可以二分搜，區間加值就用一個變數存即可。
  之後發現線段樹要從左右子樹維護排序後的序列會爛掉。
  於是乎只能分塊搞一搞惹。
• Time Complexity: \(O(K \sqrt N \log N)\)
• 覺得這次分塊寫的特別乾淨就想貼上來 >///<

• Apr 16, 2017

• 繼續閱讀

台中區資訊(11/16)在台中一中比，題目照慣例由彰師大準備
值得一提的是今年是台中區第一次用 Online Judge，之前都是人肉 Judge，測資也因此不能太大
彰師大用的是 IOI 用過的 CMS，架在 Ubuntu 上，我問他們是 \(32\) 還是 \(64\) 位元卻沒回答我 = =
然後編譯器是 gcc，編 C++ 的參數有 -std=c++11 ，真令人感動
有一種經歷時代變遷的感覺啊（茶

• Nov 17, 2016

• 繼續閱讀

• problem link
• 問題：從長度在 \( [l, r] \) 的沒有連續兩個 0 的 01 序列中，同樣長度的選 k 個，有幾種選法？（輸出選法數除以 \(10^9+7\) 的餘數） (\(1 \le k \le 200, \; 1 \le l \le r \le 10^{18} \))

• Sep 16, 2016

• 繼續閱讀

• problem link
• 題目：
  給你一個有 \(n\) 個整數的陣列 \(a[1..n]\)，有 \(m\) 筆詢問，
  每筆\((i, j, k)\)問你 \(a[i..j]\) 中第 \(k\) 小的數為何
• 解法：相信大家都會寫持久化線段樹的作法，我就不介紹了
  今天用的是一種叫劃分樹的資料結構，感覺是中國選手自己搞出來的東西
  因為找不到英文的資料
  倒是 google 的到很多簡體中文資料
  隨便貼其中一個划分树 - pony1993 - 博客园，說明應該比我清楚

• Aug 27, 2016

• 繼續閱讀