分塊 & 離線 & 一點點分治

# 分塊 --- ## 區間分塊 ---- ### RMQ ---- 大家都喜歡 RMQ，所以我們來看一個 RMQ 的解法。 ---- 餘切 : 那你就不用線段樹了，你用分塊 ---- 先考慮維護每 $K$ 個人一塊，維護這一塊的最大值，那完整包含的一塊就可以在 $O(1)$ 算 ![image](https://hackmd.io/_uploads/Byliu1RJ1l.png) ---- 因此你需要回答的時間是塊數 + 不滿一塊的人，因為你知道不滿一塊的人數，總時間 $O(\frac N K + K)$，因為你會算幾不等式，所以知道 $K = \sqrt N$ 最佳，一次詢問 $O(\sqrt N)$ [Code](https://cses.fi/paste/a58efd6878891ee0a606a1/) ---- #### 單點修改? 整塊重蓋? 時間複雜度 $O(K)$ 可以接受。 ---- #### 區間修改? 打懶標，複雜度 $O(\frac N K + K)$，很爽 ---- 這樣的東西在沒辦法好好合併的時候會很爽，所以我們來看一下這些題吧。喔還有分塊星爆快，所以你看到兩個log的東西都可以去砸砸看。 ---- ### [帶修改區間大於 $K$ 的數](https://www.spoj.com/problems/GIVEAWAY/) 分塊，每塊維護 sorted array。總時間 $O(N + Q \sqrt{N} \log N)$ 喔你也可以寫樹套樹，我沒意見。 ---- ### [Holes](https://codeforces.com/contest/13/problem/E) 給你一棵樹，保證父節點編號一定比你大 (根是 $N$)，每次有兩個操作，問一個點的深度與改父節點。 ---- 維護每個點需要花幾步才能跳出這一塊，與會走到誰。這樣問深度的時間是 $O(\frac N K)$ 修改 $O(K)$ 總複雜度 $O(Q \sqrt N)$ ---- 區間分塊另一個很爽的是是散塊中只有 $O(K)$ 個人，所以如果你要問的東西需要的時間跟散塊內的人數有關就很爽。例如 ---- ### 森林系二階考古題 ---- ### [區間~~種樹~~眾數](https://judge.yosupo.jp/problem/static_range_mode_query) 區間眾數無法合併，但可以仰賴一些性質。 ---- 我們先切每一塊，知道所有整塊之間的眾數 ($O(\frac {N^2} {K^2})$ 個這種區間)，那就只有整塊區間的眾數與散塊內的數有可能是眾數，所以複雜度是預處理 $O(\frac {N^2} K + K \text{count}(N))$ , $\text{count}$ 是算一個區間內某個數出現幾次需要的時間，可以做 $O(\log N)$ 或 $O(1)$ 複雜度 : $O((Q + N) \sqrt{N})$ ---- ### 題目很多題都有時間複雜度更好的方法，但分塊好好寫。 [ABC 339 G](https://atcoder.jp/contests/abc339/tasks/abc339_g) [CF 13 E](https://codeforces.com/contest/13/problem/E) [CF 551 E](https://codeforces.com/problemset/problem/551/E) [CF 617 E](https://codeforces.com/problemset/problem/617/E) [CF 785 E](https://codeforces.com/problemset/problem/785/E) ---- [CF 840 D](https://codeforces.com/contest/840/problem/D) [Library Checker - Static Range Inversions Query](https://judge.yosupo.jp/problem/static_range_inversions_query) [Library Checker - Range Linear Add Range Min](https://judge.yosupo.jp/problem/range_linear_add_range_min) [TIOJ 1840](https://tioj.ck.tp.edu.tw/problems/1840) [TIOJ 2378](https://tioj.ck.tp.edu.tw/problems/2378) [SPOJ - Give Away](https://www.spoj.com/problems/GIVEAWAY/) --- ## Ki子線段樹 ---- Ki 子線段樹就是有的時候你用一層合併會覺得很不爽，那你就可以開一棵線段樹，然後遞迴到一個大小小於 $K$ 的區間再當一層分塊暴力做。 ---- 好處可能是 code 會比較短，某些東西寫起來比較好看。 ---- ### 題目 [Luogu p3992](https://www.luogu.com.cn/problem/P3992) [Luogu p5063](https://www.luogu.com.cn/problem/P5063) --- ## 塊狀鍊表 ---- 類似兩層的 skip list，可以支援插入任意位置，整塊的移動等。 [這題](https://loj.ac/p/6282) 可以寫寫看。 --- ## 座標分塊 ---- 通常是給你一堆點，要求你找到一條夠短的 Hamilton Path 例如 : [CF 576 C](https://codeforces.com/problemset/problem/576/C) ---- 對 $x$ 座標分塊! 同一塊的按照 $y$ 座標排，不同塊的直接連。長度是$O(N \sqrt C)$ ---- ### 題目 [TIOJ 2298](https://tioj.ck.tp.edu.tw/problems/2298) --- ## 數論分塊 ---- 通常是問某種 $$\sum_{i=1}^N f(i)$$(或輸出 $f(i)$)，而且 $f(i)$ 是正(非負)整數，前期($i \le \Delta$)遞減極快。 ---- 例如 $$\sum_{i=1}^N \lfloor \frac N i \rfloor$$ 注意到，$i \ge \sqrt N$ 後只有 $\sqrt N$ 種值，所以我們可以在 $i \le \sqrt N$ 把 $f(i)$ 相同的人包一塊算，時間複雜度為 $O(\sqrt N)$。 ---- ### 題目 [ABC 230 E](https://atcoder.jp/contests/abc230/tasks/abc230_e) [CSES - Sum of Divisors](https://cses.fi/problemset/task/1082/) [CF 786 C](https://codeforces.com/contest/786/problem/C) [CF 616 E](https://codeforces.com/problemset/problem/616/E) [Luogu P2261](https://www.luogu.com.cn/problem/P2261) --- ## Hybrid / 分重 & 輕 case ---- ### 找三角形偷圖論簡報的 ---- 一個很值觀的想法是枚舉所有有邊的 $u$,$v$，用 bitset 兩個 and 起來，複雜度為 $O(\frac {\lvert E \lvert \lvert V \lvert} w)$。 ---- 再來你知道對於鄰接矩陣 $A$，拿 $A$ 去 or $A^2$ 就可以知道有沒有了，所以你有 $O(\lvert V \rvert ^ {\omega})$ ---- 然後你 hybrid 一下，對於 $\deg \le \Delta$ 的你就用 $O(\Delta \lvert E \rvert)$ 的時間枚舉一條邊跟他的一端要連誰，所以只剩三個點 $\deg > \Delta$ 的三角形，那你知道這樣點數有 $O(\frac {\lvert E \rvert} \Delta)$，複雜度是 $O(({\frac {\lvert E \rvert} \Delta})^\omega)$，總複雜度是 $O(({\frac {\lvert E \rvert} \Delta})^\omega + \Delta \lvert E \rvert)$，取 $\Delta = {\lvert E \rvert} ^ {\frac {\omega - 1} {\omega + 1}}$ 可得 $O(\lvert E \rvert ^ {\frac {2 \omega} {\omega + 1}})$ ---- ### 大步小步在找一個長度確定不超過 $N$ 且一次可以跳很多格的環的長度時，我們可以遇處理從開頭 $1 \sim K$ 的點，這樣保證$\frac N K$ 次從開頭跳 $K$ 以後一定可以找到我們走過的點，時間複雜度 $O(K + \frac N K) = O(\sqrt N)$ ---- :::spoiler AC code ```cpp= #include <bits/stdc++.h> #define uwu return 0; using namespace std; #define LOCAL #ifdef LOCAL const int SIZE = 1e5 + 5; int func[SIZE]; int Init(){ int n; cin >> n; for (int i = 1; i <= n;i++){ cin >> func[i]; } return n; } int Query(int a, int b){ while(b--){ a = func[a]; } return a; } void Report(int a){ cout << a << '\n'; return; } #else #include "lib2211.h" #endif int main(){ int n = Init(); int magic = sqrt(n) + 1; unordered_map<int, int> umap; umap[1] = 1; for (int i = 1; i < magic;i++){ int q = Query(1, i); umap[q] = i + 1; if(q == 1){ if(i == 1) Report(1); else Report(Query(1, i - 1)); uwu } } int tmp = 1; for (int i = 1; i <= n;i++){ tmp = Query(tmp, magic); if(umap[tmp]){ int len = i * magic - umap[tmp]; if(len == 0) Report(1); else{ int ans = Query(1, len); Report(ans); } uwu } } } ``` ::: ---- ### 題目 [Atcoder Typical 90 - 083](https://atcoder.jp/contests/typical90/tasks/typical90_ce) [ABC 219 G](https://atcoder.jp/contests/abc219/tasks/abc219_g) [ABC 350 G](https://atcoder.jp/contests/abc350/tasks/abc350_g) [ARC 060 D](https://atcoder.jp/contests/arc060/tasks/arc060_b) [ARC 139 B](https://atcoder.jp/contests/arc139/tasks/arc139_b) ---- [CF 797 E](https://codeforces.com/problemset/problem/797/E) [CF 1580 C](https://codeforces.com/contest/1580/problem/C) [CS Academy - Modulo Queries](https://csacademy.com/contest/archive/task/modulo-queries/statement/) [NEOJ 252](https://neoj.sprout.tw/problem/252/) [TIOJ 2211](https://tioj.ck.tp.edu.tw/problems/2211) ---- [暴雷](https://oj.uz/problem/view/IOI09_regions) [暴雷](https://oj.uz/problem/view/IOI15_teams) --- ## 合為定數的相異數 ---- 就一個老梗，都是正整數 $x$ 且 $\sum x_i = S$ 的話 $x$ 只有 $\sqrt S$ 種不同的值。 ---- ### 題目 [ABC 269 G](https://atcoder.jp/contests/abc269/tasks/abc269_g) [TIOJ 2363](https://tioj.ck.tp.edu.tw/problems/2363) [暴雷](https://oj.uz/problem/view/IOI15_teams) [暴雷](https://atcoder.jp/contests/joi2024ho/tasks/joi2024ho_c) --- ## Meet in the middle ---- 好像慣例都會放在分塊講，因為它是一種根號算法。 ---- ### [CSES - Meet in the Middle](https://cses.fi/problemset/task/1628/) 給你 40 個數，問你有幾種方法可以湊出給定的的數字。直接枚舉會爆炸，但你可以先枚舉前面的 20 個跟後 20 個，然後再合併兩個的答案，複雜度 $O(N 2 ^ {\frac N 2})$ ---- ### 題目 [ABC 271 F](https://atcoder.jp/contests/abc271/tasks/abc271_f) [ABC 326 F](https://atcoder.jp/contests/abc326/tasks/abc326_f) --- ## 樹分塊 ---- ### [有沒有人要學QAQ](https://the-coding-pooh.github.io/2024/08/26/On-a-New-Algorithm-for-Tree-Decomposition/) --- # 離線 ---- 離線就是你不會在線的處理某些事，那你就把輸入都先吃進來，然後再做事。 --- ## 時光倒流 ---- 時光倒流就是你發現你不會做正序的操作但會做逆序的。那你就把它全部吃進來，然後再到著做，然後輸出。 ---- ### 題目 [AGC 016 E](https://atcoder.jp/contests/agc016/tasks/agc016_e) [CSES - Network Breakdown](https://cses.fi/problemset/task/1677) --- ## 掃描線 ---- 掃描線是另一種把詢問吃進來以後再好好做的方法。通常順序會是對著某一種值去排序後再丟進去。 ---- ### 矩形覆蓋面積把所有的矩形吃進來，然後對 $y$ 掃描，矩形就變成兩個區間加值跟減值的操作。 ---- ### 區間最小值對右界排序，用單調對列做 ---- ### 題目 [CF 2009 G3](https://codeforces.com/contest/2009/problem/G3) [CSES - Static Range Minimum Queries](https://cses.fi/problemset/task/1647) [CSES - Distinct Values Queries](https://cses.fi/problemset/task/1734/) [TIOJ 1224](https://tioj.ck.tp.edu.tw/problems/1224) [TIOJ 2273](https://tioj.ck.tp.edu.tw/problems/2273) [SPOJ GSS2](https://www.spoj.com/problems/GSS2/) --- ## 莫隊 ---- ### 一般莫隊 ---- 還記得座標分塊嗎，如果我們把詢問離線進來，然後當作二維平面上的點，那我們能在 $O(f(n))$ 的時間支援改變 $l, r$，就能在 $O(\text{Hamilton Path Length} \times f(n))$ 的時間內弄完全部詢問。也就是說可以在 $O((N + Q) \sqrt N f(n))$ 或 $O(N \sqrt Q f(n))$ 的時間支援完。 ---- 具體實作上是怎樣呢? ```cpp= bool comp (queries q1, queries q2){ if(q1.l / K == q2.l / K) return q1.r < q2.r; return q1.l / K < q2.l / K; } ``` 把詢問按照這個排序。 ---- 什麼意思? 先把操作左界切成$K$塊，不同塊的話根據塊的編號排，同一塊根據操作右界sort ---- 所以每一塊內右界最多動到$N$次，左界每兩個操作之間都最多移$N/K$次，所以總複雜度是$O(NK+Q\frac N K)$ 為$O(N\sqrt Q)$。 ---- #### 奇偶優化可以發現如果奇數塊的右界按照一個順序，偶數塊反過來，這樣右界需要動的次數的期望值會下降，這就叫奇偶優化，實作如下: ```cpp! bool qcomp(queries x,queries y){ if(x.l / K != y.l / K) return x.l / K < y.l / K; return ((x.l / K) & 1)?x.r < y.r : x.r > y.r; } ``` 大概常數變0.7倍左右 ---- #### 呼叫改l,r的函數移左界和右界的順序一定要滿足先擴大再所小 ```cpp! for(auto qi:qvec){ while(qi.l < nl) add(--nl); while(qi.r > nr) add(++nr); while(qi.l > nl) del(nl++); while(qi.r < nr) del(nr--); ans[qi.id] = nans; } ``` 其實好像有6種(如果sort沒爛掉有12種排法)，請見[OI WIKI](https://oi-wiki.org/misc/mo-algo/) ---- ### 回滾莫隊 ---- 如果你不會刪，那你可以考慮不要刪，把所有的詢問分成兩類: 1. l和r是在同一塊的詢問 2. l和r是在不同塊的詢問 ---- 注意到對於$l$在同一塊的狀況下，$r$只會++不會--，因此對於狀況2可以維護$l$在的那一塊的右界到$r$的答案，這個答案不必重算 ---- 只需要重算$l$到$l$在的那一塊的右界的貢獻就好，因此總複雜度還是不變，只要確保把$l$的貢獻移除(回滾)的複雜度是好的就好。 ---- ```cpp= int prev_blk = -1, tmpl = 0, tmpr = -1, now_best = 0; for(auto i:qvec){ if(i.l / K != prev_blk){ init(); tmpr = (((i.l / K) + 1) * K) - 1; } prev_blk = i.l / K; if(i.l / K == i.r / K){ for (int j = i.l - 1; j <= i.r;j++){ insert(arr[j]); ans[i.id] = max(ans[i.id], query(arr[j])); } for (int j = i.l - 1; j <= i.r;j++){ remove(arr[j]); } save(); continue; } while(tmpr < i.r){ insert(arr[++tmpr]); now_best = max(now_best, query(arr[tmpr])); } ans[i.id] = now_best; tmpl = ((i.l / K) + 1) * K; while (tmpl >= i.l){ insert(arr[--tmpl]); ans[i.id] = max(ans[i.id], query(arr[tmpl])); } while(tmpl < ((i.l / K) + 1) * K){ remove(arr[tmpl++]); } } return; } ``` ---- #### $O(T(n))$ 可插入資節區間問題 $O(T(n))$ 可插入資節有一個很好的回滾法是用一個 stack 存一個歷史改值，再滾回去，空間複雜度是 $O(nT(n))$，因為這樣均攤是 $T(n)$ ，(因為一定要有 $k$ 次操作才能讓他一次噴 $kT(n)$ 個東西)，最經典的例子就是 DSU ---- ### 帶修改莫隊 / 多維莫隊 ---- 多維莫隊基本上就是跟一般莫隊差不多，$x$ 維就可以$O(QN^{\frac {x - 1} {x}})$ ---- 帶修改莫隊就是把時間當作一個軸，$O(QN^{\frac 2 3})$。 ---- ### 樹上莫隊 ---- 先把樹上的節點分組，然後直接沿著樹形做莫隊，有些實作真的很帥。 [例如這個](https://github.com/kth-competitive-programming/kactl/blob/main/content/data-structures/MoQueries.h) 性質應該是他的魔改 dfs 序相鄰兩人距離小於3 ---- ### 題目 [ABC 293 G](https://atcoder.jp/contests/abc293/tasks/abc293_g) [CSES - Distinct Values Queries](https://cses.fi/problemset/task/1734/) [CF 86 D](https://codeforces.com/problemset/problem/86/D) [CF 940 F](https://codeforces.com/problemset/problem/940/F) [CF Edu. DSU Step.3 pB](https://codeforces.com/edu/course/2/lesson/7/3/practice/contest/289392/problem/B) ---- [LOJ 6762](https://loj.ac/p/6762) [Luogu p1093](https://www.luogu.com.cn/problem/P1903) [TIOJ 1902](https://tioj.ck.tp.edu.tw/problems/1902) [TIOJ 2122](https://tioj.ck.tp.edu.tw/problems/2122) [SPOJ COT2](https://www.spoj.com/problems/COT2/) [暴雷](https://atcoder.jp/contests/joisc2014/tasks/joisc2014_c) ---- 掃描線題也都可以拿去練練手 --- ## 操作分塊 & 時間分塊 ---- ### 操作分塊考慮如果只有詢問的話可以花 $O(f(N))$ 建造一個東西來支援，然後你會花 $O(g(K))$ 來處理 $K$ 個操作對你的影響。那就每個 $K$ 個操作重花一次 $Of(N)$ 來支援，總時間複雜度 $O(Q(\frac {f(N)} {K} + g(K))$ ---- ### 時間分塊時間分塊是直接拿時間當一個維度來分塊，在支援一些插入刪除的操作時很好用。 ---- ### 題目 [CF 342 E](https://codeforces.com/problemset/problem/342/E) [NTUCPC OJ 102](https://oj.ntucpc.org/problems/102) [暴雷](https://oj.uz/problem/view/APIO19_bridges) --- ## 詢問分治 ---- 考慮一個這樣的問題，給你一個序列，問你區間積 $\mod M$。 ---- 如果先把詢問離線進來，然後把詢問拿去分治呢? 每層的分治就處理包含了中點的詢問，不然就丟下去接著就處理從中點出發的後綴積與前綴積。 $O(N \log N + Q \log N)$ ---- ### 題目 [Hackerank - Find the Path](https://www.hackerrank.com/challenges/shortest-path/problem) [暴雷](https://oj.uz/problem/view/BOI17_toll) --- ## 時間分治 ---- 又稱時間線段樹，基本上就是對時間的維度開一顆線段樹，某個東西某個時間段存在就可以在線段樹上加在 log 個節點，因此你只需要全部加完以後再遍歷整顆線段樹的子節點就好。 ---- ### 時間如果你可以用可回滾資節的話最好，不然就每層開一個資節。 $O(Q \log Q f(N))$ ---- ### 題目 [CSES - Dynamic Connectivity](https://cses.fi/problemset/task/2133) [Luogu p5787](https://www.luogu.com.cn/problem/P5787) --- ## 整體二分搜 ---- 當你有很多個二分搜要做的時候 (每個詢問要做一次)，而且每個二分搜有很多東西是重疊的，你就可以像詢問分治那樣，把這些二分搜一起做。 ---- ### 題目 [AGC 002 D](https://atcoder.jp/contests/agc002/tasks/agc002_d) [AGC 044 D](https://atcoder.jp/contests/agc044/tasks/agc044_d) [SPOJ - METEORS](https://www.spoj.com/problems/METEORS/) [TIOJ 1840](https://tioj.ck.tp.edu.tw/problems/1840) --- ## CDQ 分治 ---- 某種類型的分治的統稱，這個類型的分治的重點就是順序如下 ```cpp= vold solve(int l, int r){ int m = (l + r) / 2; solve(l, m); process(l, m, m + 1, r); solve(m + 1, r); } ``` ---- ### 有啥用? 首先是在線轉離線，因為你這樣的順序永遠保證在轉後面的人的時候，前面的值已經知道了。再來再很多操作問題上就可以變成看這個區間的人對後面的貢獻就好。最後是在解決多維偏序問題時可以把一維變成時間，然後離線，少掉一維。 ---- ### 題目 [OJDL 7172](https://ojdl.ck.tp.edu.tw/problem/7172) [TIOJ 1175](https://tioj.ck.tp.edu.tw/problems/1175) [SPOJ ADACABBA](https://www.spoj.com/problems/ADACABAA/) 去 dp 優化那邊找啦 --- ## Tarjan LCA ---- 離線，時間$O((N+Q) \alpha(N))$ Tarjan有另一個$O(N+Q)$的做法，自己看論文 ---- ### 過程 dfs的時候處理詢問如果詢問LCA的另一個點已經被走過了那答案就是另一個點在dsu的top return之前在dsu把自己連到parent上如果要啟發式合併要好好記最上面那個人 ---- 扣 ```cpp template <class Graph> struct Tarjan_LCA { const Graph& G; vector<int> top, P; vector<vector<int>> qid; vector<pair<int, int>> qry; Tarjan_LCA(const Graph& G) : G(G), top(size(G)), P(size(G), -1), qid(size(G)), qry() { iota(begin(top), end(top), 0); } void add_query(int u, int v) { int id = size(qry); qid[u].emplace_back(id); qid[v].emplace_back(id); qry.emplace_back(u, v); } vector<int> run(int rt) { vector<bool> vis(size(G)); vector<int> ans(size(qry), -1); auto f = [&](auto&& f, int x, int pre) -> void { vis[x] = true; for (auto to : G[x]) if (to != pre) { f(f, to, x); link(x, to); } for (auto id : qid[x]) if (ans[id] == -1) { auto [u, v] = qry[id]; int y = x ^ u ^ v; if (vis[y]) ans[id] = find_top(y); } }; f(f, rt, -1); return ans; } private: int find(int x) { return (P[x] < 0 ? x : P[x] = find(P[x])); } int find_top(int x) { return top[find(x)]; } void link(int pa, int x) { int ru = find(pa), rv = find(x); if (P[ru] > P[rv]) swap(ru, rv); P[ru] += P[rv]; P[rv] = ru; top[ru] = pa; } }; ``` --- # 回到在線 --- ## 持久化 ---- 持久化就是幫每次修改到的節點開一個新的版本，例如再線段樹上就複製一個點。空間就會是原本操作的時間複雜度 (因為就改到這麼多人)，然後可以保存歷史值。所以可以拿來在線處理很多掃描線需要的東西。 ---- ### 題目掃描線那邊的去寫一寫 --- ## 詩乃莫隊 (假裝自己是莫隊的分塊 = =) ---- 基本上就是分塊，只不過他告訴你如果合併有好性質就可以 $O(Q \sqrt N)$，不然就塊切大一點然後 $O(Q N ^ {\frac 2 3})$ --- ## 操作分塊 again ---- 稍微提醒你一下操作分塊如果你重蓋跟算貢獻都不需要後面的詢問，哪他其實是在線的喔。 ---- ### 題目 [Luogu p2137](https://www.luogu.com.cn/problem/P2137) [暴雷](https://oj.uz/problem/view/IOI11_elephants) --- ## Disjoint Sparse Table ---- 把詢問分治的結果存下來，找詢問的層的時候補到 2 的冪次用位元運算。時間 $O(N \log N + Q)$ ---- ### 題目 [Codechef - SEGPROD](https://www.codechef.com/problems/SEGPROD) --- # 我今年不用講校培啦。