線段樹 + 一些持久化精神 參考 Morris 大神的文章，所以 code 可能有 87% 像 :P （感謝 Morris 大神寫了很好的文章，他的 code 排版清楚，命名也好理解 XD） 每次操作都是建立一個新節點，因此可以回溯。 詢問時參考新舊節點的值，修改時也會參考舊節點產生新節點。 傳送門 & 參考資料 ZJ_b278 Morris 大神的文章 程式碼 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 5... Read more 15 Jul 2017 - 5 minute read
解法 Rolling Hash 給 A, B 兩字串， 詢問每個長度為 A, B 字串長度公因數的子字串 是否可以藉由複製自己多次，重組為 A, B 且是否為 A, B 的共同子字串。 用 時間枚舉每個公因數長度子字串， 檢查是否合法。 總體複雜度 快速求取複製字串的方法： 利用 Rolling Hash 性質： 假設原字串 Hash 為 ，字串長為 ，那麼 其中， 為 hash 使用的基底， 為 hash 使用的模數 為字串 A 重複 2 遍的 hash 結果。 可以利用上面的性質和快速冪的概念， 在 時間內取得 A 重複 N 遍的 hash 值。 實作方式可以參考程式第 72 行。 傳送門 CF182D 1 2 3 4 5 6 7... Read more 12 Jul 2017 - 3 minute read
解法 線段樹 + 掃描線 用線段樹維護每個 y 方向的線段，取得 y 方向的線段和， 一邊掃過 x 方向，算出每個 y 方向線段間圍起來的面積和。 傳送門 POJ1151 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 8... Read more 12 Jul 2017 - 2 minute read
解法 線段樹 + 掃描線 用線段樹維護每個 y 方向的線段，取得 y 方向的線段和， 一邊掃過 x 方向，算出每個 y 方向線段間圍起來的面積和。 這題比 POJ1151 更困難一些。 差別在於這題輸入是閉區間，還有測資範圍比較大。 傳送門 CF610D 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74... Read more 12 Jul 2017 - 3 minute read
多邊形面積、格子邊上點、多邊形格子邊內點 傳送門 POJ1265 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105... Read more 12 Jul 2017 - 2 minute read