P4688 [Ynoi2016] 掉進兔子洞

序列，靜態，求三個區間的可重集的交的大小，離線，\(n,Q\le 10^5\)，3s，500MB

缺乏性質 \(\rightarrow\) bitset

靜態區間 \(\rightarrow\) 莫隊化為單點改

bitset 支持取交，\(x\) 重復 \(cnt_x\) 次即可，空間 \(O(n^2/w)\)，時間 \(O(n\sqrt n+{n^2\over w})\)，分三次處理減小空間常數

P4690 [Ynoi2016] 鏡中的昆蟲

序列，區間賦值，區間數顏色，離線，\(n,Q\le 10^5\)，1s，64MB

數顏色 \(\rightarrow\) 維護 pre

珂朵莉樹 \(\rightarrow\) pre 只改變 \(O(Q)\) 次

轉化：單點改 pre，查詢 \([l,r]\) 內 pre 小于 \(l\) 的數量

1. 樹套樹，在線，空間 \(O(n\log n)\)，時間 \(O(n\log^2 n)\)，過不去
2. CDQ，離線，空間 \(O(n)\)，時間 \(O(n\log^2 n)\)，正解

P5064 [Ynoi2014] 等這場戰爭結束之后

圖，動態加邊，回退到某歷史版本，查詢某個連通塊中權值第 \(k\) 小，離線。\(n,Q\le 10^5\)，500ms，20MB

回退歷史版本 & 可離線 \(\rightarrow\) dfs 操作樹轉為撤銷

第 \(k\) 小 & 可合并 \(\rightarrow\) 值域分塊 或 bitset

1. 值域分塊

   值域每 \(B\) 個分成一塊，按塊離線，記錄每個連通塊點數。

   • 合并、撤銷連通塊：暴力 \(O({n^2\over B}\log n)\)，注意到并查集操作對每個值域塊相同，預處理可 \(O(n^2/B)\)。
   • 查詢連通塊第 \(k\) 小：
     • 枚舉值域內每個數判斷，\(O(nB\log n)\)。
     • 每個并查集開桶，\(O(nB)\)，空間 \(O(nB)\)，\(B\) 需要開很小。
     • 使用鏈表維護，可以是有序鏈表歸并（難寫）或每次把鏈表所有數拿出來 nth_element，\(O(nB)\)。

   總時間復雜度 \(O(n\sqrt{n\log n})\) 或 \(O(n\sqrt{n})\)，空間線性。

2. bitset 壓位

   查詢 bitset 可直接 \(O(n/w)\)。

   不能開 \(n\) 個 bitset \(\rightarrow\) 對于點數小于 \(n/w\) 的連通塊用鏈表維護，同時至多存在 \(w\) 個 bitset，空間線性。

   鏈表查詢，合并同上。鏈表并入 bitset 可啟發式暴力。

   總時間復雜度 \(O(n^2/w)\)，空間線性。

P5354 [Ynoi2017] 由乃的 OJ

樹，每個點的效果為 \(\operatorname{and}/\operatorname{or}/\operatorname{xor}\) 一個數，單點改，詢問 \([0,z]\) 中所有數經過路徑操作得到的最大值，無需離線。\(n,Q\le 10^5\)，值域 \(2^{64}\)，250ms，128MB。

二進制操作 \(\rightarrow\) 拆位

二進制復合 \(\rightarrow\) 壓位處理復合矩陣，同時處理 \(k\) 位的復合，\(O(k)\rightarrow O(1)\)

總時間復雜度 \(O(n\log^2n+nk)\)

P6109 [Ynoi2009] rprmq1

二維平面，先修改后查詢，矩形加，矩形求 \(\max\)。\(n\le 5\times 10^4,Q\le 5\times 10^5\)，4s，512MB。

矩陣 \(\rightarrow\) 將一維時間化，離線問題轉為在線問題

修改，詢問在一段時間區間生效 \(\rightarrow\) 貓樹轉為對一段后綴有效（即修改后無需撤銷，詢問等價于查歷史信息和）

區間加歷史最值即可，時間復雜度 \(O(n\log^2n+Q\log n)\)

P6780 [Ynoi2009] pmrllcsrms

序列，單點改，求區間長度不超過 \(c\) 的最大字段和，其中 \(c\) 為全局定值，無需離線。\(n,Q\le 10^6\)，6s，512MB。

長度不超過 \(c\) \(\rightarrow\) 每 \(c\) 個位置分一塊，詢問分為每塊內全部或兩相鄰塊之間

相鄰塊后前綴長度和不超過 \(c\) \(\rightarrow\) 直角三角形模式，分成一個矩形和兩個小直角三角形

時間復雜度 \(O(n\log n)\)

P6783 [Ynoi2008] rrusq

二維平面，\(n\) 個帶權點，\(m\) 個矩形，\(Q\) 次詢問區間 \([l,r]\) 內的矩形并中點權之和，離線。\(n,m\le 10^5,Q\le 10^6\)，4s，128MB。

靜態區間，難以增量 \(\rightarrow\) 掃右維護左

點出現在區間并中 \(\rightarrow\) 掃右端點，維護每個點最后出現時間

KD-Tree，每次暴力收回子樹內的出現時間 tag 即可

詢問使用 \(O(1)-O(\sqrt n)\) 的數組維護

時間復雜度 \(O(n\sqrt Q+Q\sqrt n)\)

P7446 [Ynoi2007] rfplca

序列，區間減，詢問 \(fa\) 數組形成的樹上某兩個點的 LCA，無需離線。\(n,Q\le 4\times 10^5\)，保證 \(fa_i<i\)，2.5s，64MB。

形式奇怪 \(\rightarrow\) 考慮分塊

詢問 LCA \(\rightarrow\) 不斷跳 \(fa\)

不斷進行重復操作 \(\rightarrow\) 記錄每個點跳出塊后的第一個位置

散塊直接重構，整塊 \(\sqrt n\) 次后全部出塊，直接打 tag，詢問 trivial，時間復雜度 \(O(n\sqrt n)\)

P7447 [Ynoi2007] rgxsxrs

序列，區間大于 \(x\) 的數減 \(x\)，區間和與最小最大值，無需離線。\(n,Q\le 5\times 10^5,a_i\le 10^9\)，6s，64MB。

和值域有關 \(\rightarrow\) 值域倍增分塊（？）

1. 塊大于 \(x\)，打標記或降塊，降塊至多 \(\log V\) 次，產生 \(\log n\) 的復雜度后必然降塊
2. 塊等于 \(x\)，暴力找到所有需要減小的 \(a_i\)，單個 \(a_i\) 同塊內至多減小 \(b\) 次（\(b\) 為倍增底數）

時間復雜度 \(O(nb\log_bV\log n)\)。空間底層分塊后線性。

P7722 [Ynoi2007] tmpq

三個序列 \(a,b,c\)，單點改 \(a\)，詢問有幾個 \(i<j<k\le r\) 滿足 \(b_{a_i}=a_j=c_{a_k}\)，離線。\(n\le 2\times 10^5,Q\le 5\times 10^4\)，4s，64MB。

陰間條件 \(\rightarrow\) 單點改 \(a,b,c\)，詢問 \(b_i=a_j=c_k\)

顏色相關 \(\rightarrow\) 次數大小分治，小者暴力，大者維護

小顏色暴力重新 dp，\(O(Q\sqrt n)\) 次區間加，\(O(Q)\) 次單點查

大顏色維護動態 dp，分塊維護塊內前綴 dp 結果及前綴塊 dp 結果，單點改 \(O(\sqrt n)\)，查詢 前綴塊+塊內前綴=\(O(1)\)

總時間復雜度 \(O(Q\sqrt n)\)，空間離線做到線性

P7880 [Ynoi2006] rldcot

樹，邊帶權（可以為負），靜態，\(Q\) 次詢問 \([l,r]\) 內的點對有幾種不同的 \(\operatorname{lca}\) 帶權深度，離線。注意不保證 \(fa_i\le i\)。\(n\le 10^5,Q\le 5\times 10^5\)，500ms，512MB。

合法子區間計數 \(\rightarrow\) 考慮有用點對

樹上有用點對 \(\rightarrow\) 重剖，由輕子樹合并上來，有用點對 \(O(n\log n)\) 對

問題轉化為給定 \(O(n\log n)\) 對帶權點對，求區間內存在哪些權值。

靜態區間問題 \(\rightarrow\) 掃右維護左，轉為在線問題

給前綴放上一個顏色，求單點顏色數，樹狀數組即可。時間復雜度 \(O(n\log^2 n+Q\log n)\)。

P7881 [Ynoi2006] rmpq

二維平面，抽象信息類，半平面乘，單點查，強制在線。\(Q\le 10^5,x_i,y_i\le 10^9\)，操作次數 \(2\times 10^7\)，2s，512MB。

無法 KD-Tree（值域過大且無法離線）。

很想離線（？）\(\rightarrow\) 根號重構。

問題變成預處理 \(B\) 次修改后每個位置的答案。

發現易于用 \(O(k^2)\) 的時間合并兩個大小為 \(k\) 的子問題，所以遞歸兩個子問題就可以做到 \(O(B^2)\) 處理。

總時間復雜度 \(O(nB+{n^2\over B})=O(n\sqrt n)\)。

總結

以上是生活随笔為你收集整理的Ynoi的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。