tomxi

摘要： 不得不說這道 dp 既考察對時間復雜度方面的優化，也要考慮對空間方面的優化。 題意 首先從暴力說起： 首先既然讓我們刪除 \(k\) 個數，也就是說保留 \(N-k\) 個數。 顯然可以 dfs 枚舉子集加剪枝優化(不過剪不剪的好像沒啥區別)，這樣做是 \(O(2^N)\) 估計只能過樣例。 代碼： 閱讀全文

摘要： 線段樹： 這是一個線段樹的例圖。 我們可以發現其實線段樹就是將幾個連續的小區間拼湊成一個個大區間的過程，從而實現查找時的優秀的復雜度。 引入-分塊基礎的思想： 其實如果你知道分塊的思想，那么你會更好理解線段樹的思想，分塊就是將一個序列分成 \(\sqrt N\) 個塊每個塊的塊長就是 \(N / \ 閱讀全文

摘要： 題意 思路： 對于1操作可以采用類似鏈表的方法在元素 \(x\) 的后面直接插入 \(y\) 的值，即 \(nxt_x = y\)。 對于2操作可以采用鏈表的刪除的方法先令 \(p = nxt_x\) 即 \(x\) 的后繼，讓 \(pre_p = pre_x\) 然后讓 \(nxt_{pre_x} 閱讀全文

摘要： 分塊二分： 眾所周知，分塊可以實現一些奇奇怪怪的區間的問題，比如以下這個題： 給定一個 \(N\) 和 \(N\) 個整數，分別為 \(A_1,A_2,A_3,A_4....A_N\) 每次詢問給出三個整數 \(l,r,k\) 求所有滿足 \(l \leq i \leq r,a_i \leq k\) 閱讀全文