單調棧的本質與應用
- 2022 年 9 月 28 日
- 筆記
單調棧的定義與證明 前言 最近領悟到了單調棧的本質，特此來記錄一下我的理解。 單調棧主要用來解決這樣一類問題，當 …
Continue Reading線段樹學習筆記（基礎&進階）（一） | P3372 【模板】線段樹 1 題解
- 2022 年 9 月 26 日
- 筆記
什麼是線段樹 線段樹是一棵二叉樹，每個結點存儲需維護的信息，一般用於處理區間最值、區間和等問題。 線段樹的用處 對編號連 …
Continue ReadingP4315 月下「毛景樹」(樹鏈剖分)
- 2022 年 8 月 6 日
- 筆記
P4315 月下「毛景樹」(樹鏈剖分) 題面 簡述: 邊權轉點權(在dfs1處轉換) 把一條邊權賦值在深度更深的上 需要 …
Continue Reading線段樹雜談
- 2022 年 7 月 24 日
- 筆記
概念： 線段樹（Segment Tree）是一個基於分治的數據結構。 通常處理區間，序列中的查詢，更改問題。大體上有單修 …
Continue Reading「 學習筆記 」線段樹合併
- 2022 年 3 月 10 日
- 筆記
線段樹合併 普通線段樹 \((\) 無懶惰標記 \()\) 時間複雜度 & 空間複雜度 假設有 \(2\) 棵線 …
Continue Reading「 題解 」P2487 [SDOI2011]攔截導彈
- 2022 年 2 月 12 日
- 筆記
簡單題意 給定 \(n\) 個數對 \((h_i, v_i)\)。 求： 最長不上升子序列的長度。 對於每個 \(i\) …
Continue Reading線段樹
- 2021 年 9 月 24 日
- 筆記
要解決的問題 數組任意區間內的元素修改，增加，求和，時間複雜度都要達到O(logN)水平, 方法說明如下 L…R上都 …
Continue Reading[題解] CF786B Legacy
- 2021 年 5 月 15 日
- 筆記
前言 題目鏈接 題意 有 \(n\) 個點，\(q\) 次連邊，以及起點 \(s\) 。連邊具體分三種： \(1\) \ …
Continue Reading
[題解] T’ill It’s Over
- 2021 年 4 月 2 日
- 筆記
前言 線段樹+網絡最大流的建模題。 題目鏈接 題目大意 最初時有 \(n\) 個 \(1\) 。給定 \(op\) 、 …
Continue Reading
樹鏈剖分解析
- 2021 年 3 月 6 日
- 筆記
前置知識 線段樹 \(and\) 樹上基本操作 定義 幾個在樹鏈剖分很重要的概念。 重兒子 對於一個父節點，含有節點數最 …
Continue Reading