young_tea 的博客站

摘要： 江湖人是過河卒 路是不歸路 -- csp-s 2025 游記 總結(jié): 打鐵了, 但是龍膽紫說 "江湖人是過河卒 路是不歸路", 所以我不會(huì) exit 的. day \(-1\) 睡不著, 打開 b 站看人直播 vp cf/atc, 我 vp div4 被炸死了. 感覺要寄. day \(0\) 火車 閱讀全文

摘要： dp 總結(jié) 1 閑來無事, 把剛學(xué)明白的 dp 筆記整理一下. shout out to professor Adzlpxsn. upd at oct 16th 2025, 修復(fù)了時(shí)間復(fù)雜度分析的重大失誤. 基本的, 狀態(tài), 轉(zhuǎn)移, 方程 狀態(tài) 一句話概況即為當(dāng)前的屬性. 比如說, 貝貝現(xiàn)在是 \( 閱讀全文

摘要： 爆炸的平衡樹, 替罪羊樹 由于Defad不太喜歡旋轉(zhuǎn), 所以一般用替罪羊樹. 這里寫個(gè)博客介紹一下. 什么是二叉搜索樹 可以維護(hù)一個(gè)集合, 相比于權(quán)值線段樹 (動(dòng)態(tài)開點(diǎn)) 的時(shí)間復(fù)雜度 \(\log{N}\) 空間復(fù)雜度 \(N \log{N}\), 二叉搜索樹理論上來說只需要 \(\log{N}\ 閱讀全文

摘要： 莫隊(duì)2 這次需要帶修改了 莫隊(duì)1 走上騙分之路 實(shí)現(xiàn)修改 莫隊(duì)是不支持修改的, 但是有后人加以改進(jìn), 就有了代修版本. 我們現(xiàn)在有一個(gè)東西叫時(shí)間軸 (類似函數(shù)式線段樹的每個(gè)根都是關(guān)于某次之前的根修改或查詢的), 每次詢問都記錄一下當(dāng)前的時(shí)間軸, 每次修改都在時(shí)間軸上新建一個(gè)版本. typedef s 閱讀全文

摘要： 莫隊(duì)1 走上騙分之路 新坑介紹莫隊(duì), 第一篇是不帶修的線性莫隊(duì). 什么是莫隊(duì) 一種硬往兩邊擴(kuò)展 (可能是收縮) 的玄學(xué)算法, 是老前輩莫濤老師發(fā)明的算法, 又因?yàn)槟蠋熯M(jìn)了國家隊(duì), 所以叫莫隊(duì). Google搜索需要搜索"Mo's Algo". 莫隊(duì)能解決什么問題 很多, 只要 \([l, r]\) 閱讀全文

摘要： 重鏈剖分, 樹上路徑問題大殺器 首先, 什么是樹鏈剖分 數(shù)組, 要進(jìn)行修改查詢是非常方便的, 一眼線段樹. 但是樹并不是. 看一下我們目前已有的樹上修改查詢技術(shù). 樹上差分 只能修改, 最后才能查詢, 不然就只能很慢的單點(diǎn)查詢, DFS 序 + 線段樹 只能進(jìn)行子樹操作, 不能進(jìn)行路徑操作. BFS 閱讀全文

摘要： 指針, C語言的精髓 莫隊(duì)先咕幾天, 容我先講完樹剖 (因?yàn)楹竺鏄渖系臇|西好多都要用樹剖求 LCA, 樹剖求 LCA 比倍增求 LCA 常數(shù)小). 什么是指針 保存變量地址的變量叫做指針. 這是大概的定義, 但是Defad認(rèn)為這個(gè)定義不太好理解, 所以我們先不看. 我們的電腦里都有隨機(jī)存儲(chǔ)器 RAM 閱讀全文

摘要： 樹上主席樹 主席樹, 但是維護(hù)樹上路徑信息. 由于Defad今天忌離散化, 就不離散化了, 把值域開大點(diǎn)一般沒啥問題. 上次的主席樹有個(gè)朋友說沒完全講清楚, 這次先講透了 主席樹, 整體圍繞的是前綴和, 用"批判的繼承"維護(hù)前綴和, 然后在前綴和上二分. 為什么主席樹不可修改, 就是因?yàn)檫@個(gè)前綴和思 閱讀全文

摘要： C語言離散化 最近看到STL就不想用, 于是寫個(gè)C語言離散化, 居然能過主席樹板子, 就寫個(gè)博客介紹一下. qsort和bsearch都在<stdlib.h>或<cstdlib>里. 什么是離散化 一種映射, 可以把值域從 \([1, Val_{\max}]\) 變成 \([1, N]\) 且保留大 閱讀全文

摘要： 題解 ICPC 2019 SH 區(qū)域賽 F 樹上簡單問題 young_tea: 給我哥 defad 的遺產(chǎn)里加上一點(diǎn)點(diǎn), 掛上這題的 qoj 鏈接和 qoj 的 vj 鏈接. CF的Gym里沒找著 牛客的題目鏈接 首先這個(gè)題多測非常SB, 每次都要清空, 需要特別注意. 樹剖應(yīng)該都會(huì)吧, Defad 閱讀全文

摘要： 線段樹的各種擴(kuò)展 前情提要線段樹, 算法競賽掌管區(qū)間的神, 權(quán)值數(shù)據(jù)結(jié)構(gòu)水各種題. 小技巧 動(dòng)態(tài)開點(diǎn) 這篇博客所有的線段樹擴(kuò)展都基于動(dòng)態(tài)開點(diǎn), 所以先講一下. 先申請(qǐng)一個(gè)很長的數(shù)組, 需要新結(jié)點(diǎn)就從數(shù)組里申請(qǐng). 這是一種內(nèi)存池思想, 可以避免內(nèi)存的多次申請(qǐng)與釋放 (更多的是可以避免指針), 在有文字 閱讀全文

摘要： 權(quán)值數(shù)據(jù)結(jié)構(gòu)水各種題 前置知識(shí) 樹狀數(shù)組, 線段樹, 分塊... 反正任何你能想到的能求和的數(shù)據(jù)結(jié)構(gòu)就行, 只要數(shù)據(jù)結(jié)構(gòu)能單點(diǎn)加求區(qū)間和, 就能當(dāng)權(quán)值數(shù)據(jù)結(jié)構(gòu). 給樹狀數(shù)組和線段樹的鏈接吧, 分塊現(xiàn)在沒有, 以后大概率也沒有 (莫隊(duì)?wèi)?yīng)該會(huì)有). 樹狀數(shù)組及其各種擴(kuò)展 線段樹, 算法競賽掌管區(qū)間的神 閱讀全文

摘要： 線段樹, 算法競賽掌管區(qū)間的神 什么是線段樹 上回講樹狀數(shù)組的時(shí)候說過, 是一種分治數(shù)據(jù)結(jié)構(gòu), 把區(qū)間從中間劈開, 通過左子區(qū)間和右子區(qū)間的合并得到大區(qū)間. 上回的樹狀數(shù)組及其各種擴(kuò)展. 線段樹長什么樣 觀察線段樹. 再次思考, 把區(qū)間從中間劈開, 通過左子區(qū)間和右子區(qū)間的合并得到大區(qū)間. 兩個(gè)子區(qū) 閱讀全文

摘要： 樹狀數(shù)組及其各種擴(kuò)展 什么是樹狀數(shù)組 一種簡單的區(qū)間數(shù)據(jù)結(jié)構(gòu), 可以維護(hù)簡單修改的數(shù)組. 樹狀數(shù)組長什么樣 \(\displaystyle val_{x} = \sum a_{i}, i \in (x - \operatorname{lowbit}(x), x]\) 注意是左開右閉區(qū)間, \(\di 閱讀全文