莫隊算法

介紹

將 query 排序

分成 sqrt(n) 個 block

每筆 Query 按照 :

1. 左界所屬 Block 從小排至大

2. 若左界 block 相同，則將右界從小排至大

code

struct Query {
    int l, r, block_id;

    bool operator<(const Query &rhs) const {
        if (block_id != rhs.block_id) {
            return block_id < rhs.block_id;
        } else {
            return r < rhs.r;
        }
    }
};

暴力移動 pointer

注意先擴大（add），再縮小（del）¹

code

int l = -1, r = 0;
for (auto &i : Query) {
    while (l > i.l) add(--l);
    while (r > i.r) add(++r);
    while (l < i.l) del(l++);
    while (r > i.r) del(r--);
}

維護 data structure

• O(1) 新增/刪除

• O(sqrt(n)) 查詢

  • 總和
  • x 出現的次數
  • mode
  • 第 k 小

複雜度

• left pointer

  • 同塊 : 同個 block 裡面 l 最多移動 sqrt(n) 格，O(Q * sqrt(n))
  • 不同 : 不同 block 之間的總移動距離為 O(N)

• right pointer

  • 同塊 : 每個 block 裡面 r 最多會移動 N 格，共 sqrt(N) 個 block，O(N * sqrt(N))
  • 不同 : 換 block 最多 sqrt(N) 次，每次最多移動 N 格，O(N * sqrt(N))

每 k 個當一個 block :

• left: 同個 block 每次移動 k，共 Q 次 ⇒ O(Q * k)

• right: N / k 個 block，每個 block O(N) ⇒ O(N * (N / k))

題目

把問題轉換換成 add, del, query，其中讓 add, del 快，query 慢

CF 86 D. Powerful Array

給一個長度為 \(n\) 的陣列 \(a_1,\ldots ,a_n\)，有 \(q\) 筆詢問 :

• 給一個區間 \([l,r]\)，將區間內每種數字與其出現的次數平方的乘積加總後輸出

\(n,q\le 2\times 10^5,1\le a_i \le 10^6\)

思路

Zerojudge b417. 區間眾數

給一個長度為 \(n\) 的陣列 \(a_1,\ldots ,a_n\)，\(q\) 次詢問一個區間的 :

• 眾數出現的次數

• 多少種數字可當眾數

\(n\le 10^5,q\le 10^6\)

思路

• freq[i] : i 出現次數

• cnt[i] : 幾種數字的出現次數為 i

• mode : 眾數的出現次數

code

#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define mk make_pair
#define pb push_back
using namespace std;

const int maxn = 1e5 + 5;
int cnt[maxn], freq[maxn], a[maxn], mode;
int n, q;

struct Query {
    int l, r, block_id, query_id;

    bool operator<(const Query &rhs) const {
        if (block_id != rhs.block_id) {
            return block_id < rhs.block_id;
        } else {
            return r < rhs.r;
        }
    }
};

void add(int x) {
    cnt[freq[x]]--;
    freq[x]++;
    cnt[freq[x]]++;
    if (freq[x] > mode) mode = freq[x];
}

void del(int x) {
    cnt[freq[x]]--;
    freq[x]--;
    cnt[freq[x]]++;
    if (cnt[mode] == 0) mode--;
}

signed main() {
    cin >> n >> q;
    vector<Query> query;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int lb, rb;
    int k = sqrt(n);
    for (int i = 0; i < q; i++) {
        cin >> lb >> rb;
        lb--, rb--;
        query.pb({lb, rb, lb / k, i});
    }
    sort(query.begin(), query.end());

    int l = 0, r = -1;
    vector<pii> ans(q);
    for (int i = 0; i < q; i++) {
        Query now = query[i];

        while (l > now.l) add(a[--l]);
        while (r < now.r) add(a[++r]);
        while (l < now.l) del(a[l++]);
        while (r > now.r) del(a[r--]);

        ans[now.query_id] = {mode, cnt[mode]};
    } 

    for (auto &p : ans) {
        cout << p.first << " " << p.second << "\n";
    }
}

LOJ #6285. 数列分块入门 9

給一個長度為 \(n\) 的陣列 \(a_1,\ldots ,a_n\)，\(n\) 次詢問一個區間的最小眾數

\(n\le 10^5\)

思路

離散化，預處理 dp[i][j] = block(i) ~ block(j) 的眾數，可以枚舉 i 然後 O(n) 做下去，時間複雜度 O(n * sqrt(n))，當預到一個 query(l, r) 時，可以分成 l ~ r 之間的完整 block，與左右不完整的 block 來做，完整 block 直接查表，不完整 block 直接暴力跑即可，過程中要檢查 l r 之間 x 出現的次數可用 vector[x] 存 x 出現的 index 然後去 lower bound，複雜度 O(q * sqrt(n) * log n)

參考 : https://blog.csdn.net/hypHuangYanPing/article/details/81260095

LOJ #6762. 「THUPC 2021」本质不同逆序对

給一個長度為 \(n\) 的陣列 \(a_1,\ldots ,a_n\)，\(q\) 次詢問一個區間的逆序數對數量

\(n\le 10^5,m\le 5\times 10^5\)

其他練習

• CSES - Distinct Value Query (多種作法)

• TIOJ 1699 Problem I 害蟲決戰時刻

• atcoder ABC 174 F

• codeforces 86 D

帶修改莫隊

介紹

把詢問的區間 [l, r] 擴充時間這個維度 ⇒ (l, r, t)。(l, r, t) 可以翻譯為「在詢問 [l, r] 之前要先處理 0~t 的修改」，排序跟普通莫隊不太一樣，是 L_block → R_block → t

struct code

struct Query {
    int l, r, t, l_block, r_block, qid;

    bool operator<(const Query &rhs) const {
        if (l_block == rhs.l_block) {
            if (r_block == rhs.r_block) {
                return t < rhs.t;
            } else {
                return r_block < rhs.r_block;
            }
        } 
        return l_block < rhs.l_block;
    }
};

時間複雜度為 \(O(n^{\frac{5}{3}})\)

相當於 \(n \times n\times n\) 的三維空間，放 \(n\) 個點，找一個路徑經過所有點移動距離最小值最差是多少呢？

一個維度放 \(n^{1/3}\) 個，每個維度的長度是 \(n\)，所以間距取 \(n / n^{1/3} = n^{2/3}\)。共要走 \(n - 1\) 邊，每邊長 \(n^{2/3}\)，所以是 \(O(n \times n^{2/3}) = O(n^{5/3})\)。

Block 的大小可以取 \(n^{2/3}\)，讓每個維度的數量最平均

此證明不嚴謹，若要嚴謹證明可見莫队时间复杂度和块长分析

指針移動

當 updates 有影響到當前 [ql, qr] 的話，才需要 add, del，不然就直接修改陣列上的元素即可

code

int l = 0, r = -1, t = -1;
for (auto [ql, qr, qt, l_block, r_block, qid] : query) {
    while (ql < l) ds.add(--l);
    while (r < qr) ds.add(++r);
    while (l < ql) ds.del(l++);
    while (qr < r) ds.del(r--);
    while (t < qt) ds.modify_add(ql, qr, ++t);
    while (t > qt) ds.modify_del(ql, qr, t--);
    ans[qid] = ds.ans;
}

CF 940 F. Machine Learning

給一個長度為 \(n\) 個陣列 \(a_1,\ldots ,a_n\)，有以下 \(q\) 個操作 :

• \(\text{mex}(l,r):\) 輸出區間數字出現次數的 mex

• \(\text{update}(i,x):\) 將 \(a_i\) 改成 \(x\)

\(n,q\le 10^5,1\le a_i \le 10^9\)

洛谷 P1903 [国家集训队] 数颜色 / 维护队列

給一個長度為 \(n\) 的陣列 \(a_1,\ldots ,a_n\)，q 筆以下操作：

• 單點改值

• 問區間 \([l, r]\) 中 distinct number 數量

\(n,q\le 1.4 \times 10^5\)

code

#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define pb push_back
#define mk make_pair
#define F first
#define S second
#define ALL(x) x.begin(), x.end()

using namespace std;

const int INF = 2e18;
const int maxn = 1e6 + 5;
const int M = 1e9 + 7;

struct Query {
    int l, r, t, l_block, r_block, qid;

    bool operator<(const Query &rhs) const {
        if (l_block == rhs.l_block) {
            if (r_block == rhs.r_block) {
                return t < rhs.t;
            } else {
                return r_block < rhs.r_block;
            }
        } 
        return l_block < rhs.l_block;
    }
};

int n, q;
int ans[maxn];
vector<Query> query;

struct DS {
    static const int N = 1e6 + 5;
    int ans = 0;
    vector<int> cnt;
    vector<int> a;
    vector<pii> updates;
    stack<pii> stk;

    DS(vector<int> b) {
        cnt.resize(N);
        a = b;
    }

    void add_event(int idx, int val) {
        updates.pb({idx, val});
    }
    void add(int x) {
        x = a[x];
        if (cnt[x] == 0) {
            ans++;
        }
        cnt[x]++;
    }
    void del(int x) {
        x = a[x];
        cnt[x]--;
        assert(cnt[x] >= 0);
        if (cnt[x] == 0) {
            ans--;
        }
    }
    void modify_add(int l, int r, int t) {
        auto [idx, val] = updates[t];
        if (l <= idx && idx <= r) {
            stk.push({idx, a[idx]});
            del(idx);
            a[idx] = val;
            add(idx);
        } else {
            stk.push({idx, a[idx]});
            a[idx] = val;
        }
    }
    void modify_del(int l, int r, int t) {
        assert(stk.size());
        auto [idx, val] = stk.top();
        stk.pop();
        if (l <= idx && idx <= r) {
            del(idx);
            a[idx] = val;
            add(idx);
        } else {
            a[idx] = val;
        }
    } 
};

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> q;
    int k = pow(n, (double)2/(double)3);
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    DS ds(a);
    int uid = -1, qid = -1;
    for (int i = 0; i < q; i++) {
        char c;
        cin >> c;
        if (c == 'R') {
            int idx, val;
            cin >> idx >> val;
            idx--;
            uid++;
            ds.add_event(idx, val);
        } else if (c == 'Q') {
            int l, r;
            cin >> l >> r;
            l--, r--;
            qid++;
            query.pb({l, r, uid, l / k, r / k, qid});
        }
    }
    sort(ALL(query));
    int l = 0, r = -1, t = -1;
    for (auto [ql, qr, qt, l_block, r_block, qid] : query) {
        while (ql < l) ds.add(--l);
        while (r < qr) ds.add(++r);
        while (l < ql) ds.del(l++);
        while (qr < r) ds.del(r--);
        while (t < qt) ds.modify_add(ql, qr, ++t);
        while (t > qt) ds.modify_del(ql, qr, t--);
        ans[qid] = ds.ans;
    }
    for (int i = 0; i <= qid; i++) {
        cout << ans[i] << '\n';
    }
} 

回滾莫隊

可處理加值易，刪除難的問題。一個典型的例子就是區間最值。添加時，我仍然可以只看新加進來的數，將其與目前的最值比較，但由於 ans 是單個值，一旦刪除時把最值給刪了，那麼我們就又得重新枚舉區間。

回滾莫隊的思想，就是把所有刪除操作給去掉（當然，如果是添加操作不好處理，回滾莫隊則是把所有添加操作去掉）

算法

初始化 :

• L 在 block 的右端點加 1
• R 在 block 的右端點
• 將同一個 block 內的按照 r 小到大排序（相反則為大到小）

如果詢問的 ql, qr 所屬的塊相同，那麼暴力掃描區間回答詢問

如果詢問的左右端點所屬的塊不同：

• 不斷將 R 擴展到 qr
• 不斷將 L 擴展到 ql
• 回答詢問
• 將 L rollback 回 block 的右端點加 1

最後要到下一個 block 的時候，再將 R 給 rollback 回來，然後一樣初始化 L, R，...

複雜度

假設回滾莫隊的分塊大小是 \(k\)：

• 對於左、右端點在同一個塊內的詢問，可以在 \(O(k)\) 時間內計算

• 對於其他詢問，考慮左端點在相同塊內的詢問，它們的右端點單調遞增，移動右端點的時間複雜度是 \(O(n)\)，而左端點單次詢問的移動不超過 \(k\)，因為有 \(\displaystyle \frac{n}{k}\) 個塊，所以總複雜度是 \(\displaystyle O(qk+\frac{n^2}{k})\)，取 \(\displaystyle k=\frac{n}{\sqrt {q}}\) 最優，時間複雜度為 \(O(n\sqrt{q})\)。

JOISC 2014 Day1 历史研究

給一個長度為 \(n\) 的陣列 \(a_1,\ldots ,a_n\) 和 \(q\) 筆詢問，每次詢問一個區間 \([l, r]\) 內重要度最大的數字，要求輸出其重要度。一個數字 \(x\) 重要度的定義為 \(x\) 乘上 \(x\) 在區間內出現的次數。

\(1\le n,m\le 10^5,1\le a_i\le 10^9\)

思路

回滾莫隊，過程中在 add 維護答案並更新答案，del 只維護答案（見代碼）

code

#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define pb push_back
#define mk make_pair
#define F first
#define S second
#define ALL(x) x.begin(), x.end()

using namespace std;

const int INF = 2e18;
const int maxn = 3e5 + 5;
const int M = 1e9 + 7;

struct Query {
    int l, r, l_block, r_block, qid;

    bool operator<(const Query &rhs) const {
        if (l_block == rhs.l_block) {
            return r < rhs.r;
        }
        return l_block < rhs.l_block;
    }
};

int n, q, k;
vector<int> a, b;
vector<Query> query;
int cnt[maxn], L[maxn], R[maxn], ans[maxn];

void add(int x, int &ans) {
    cnt[x]++;
    ans = max(ans, cnt[x] * b[x]);
}

void del(int x) {
    cnt[x]--;
}

void init() {
    cin >> n >> q;

    a = vector<int>(n);
    b = vector<int>(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        b[i] = a[i];
    }
    sort(ALL(b));
    b.resize(unique(ALL(b)) - b.begin());

    for (int i = 0; i < n; i++) {
        a[i] = lower_bound(ALL(b), a[i]) - b.begin();
    }
    k = sqrt(n);
    int l, r;
    for (int i = 0; i < q; i++) {
        cin >> l >> r;
        l--, r--;
        query.pb({l, r, l / k, r / k, i});
    }
    sort(ALL(query));

    // 為了方便, 先預處理好每個 block 的左右界
    int tot = n / k;
    for (int i = 0; i < tot; i++) {
        L[i] = i * k;
        R[i] = (i + 1) * k - 1;
    }
    if (R[tot - 1] < n - 1) {
        tot++;
        L[tot - 1] = R[tot - 2] + 1;
        R[tot - 1] = n - 1;
    }
}

void solve() {
    int l = 0, r = -1, last_block = -1, res = 0;
    for (auto [ql, qr, l_block, r_block, qid] : query) {
        if (last_block < l_block) {
            while (last_block != -1 && r > R[last_block]) del(a[r--]);
            l = R[l_block] + 1;
            r = R[l_block];
            last_block = l_block;
            res = 0;
        }

        if (l_block == r_block) {
            vector<int> cnt(b.size());
            for (int i = ql; i <= qr; i++) {
                cnt[a[i]]++;
                ans[qid] = max(ans[qid], cnt[a[i]] * b[a[i]]);
            }
        } else {
            while (r < qr) add(a[++r], res);
            int tmp = res;
            while (l > ql) add(a[--l], tmp);
            ans[qid] = tmp;
            while (l < R[l_block] + 1) del(a[l++]);
        }
    }
    for (int i = 0; i < q; i++) {
        cout << ans[i] << '\n';
    }
}

signed main() {
    init();
    solve();
} 

CF edu dsu B. Number of Connected Components on Segments

給一張 n 個點，給 m 條邊，有 q 筆查詢 :

• query(l, r): 只保留 edge[l ... r] 的邊，圖上共有幾個連通塊

\(1\le n,m,q \le 5\times 10^4\)

思路

回滾莫隊思路，配合 rollback dsu，詳見代碼

code

#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define pb push_back
#define mk make_pair
#define F first
#define S second
#define ALL(x) x.begin(), x.end()

using namespace std;

const int INF = 2e18;
const int maxn = 3e5 + 5;
const int M = 1e9 + 7;

struct Edge {
    int u, v;
};

struct DSU {
    DSU (int n) : n(n) {
        sz = vector<int>(n, 1);
        par = vector<int>(n);
        cnt = n;
        for (int i = 0; i < n; i++) {
            par[i] = i;
        }
    }
    void merge(Edge e) {
        int x = find (e.u), y = find (e.v);
        if (x == y) {
            stk.push ({x, x});
            return;
        }

        if (sz[x] < sz[y]) swap(x, y);
        sz[x] += sz[y]; par[y] = x;
        cnt--;
        stk.push({x, y});
    }
    void undo() {
        assert(stk.size());
        auto [x, y] = stk.top ();
        stk.pop ();
        if (x == y) return;
        sz[x] -= sz[y]; par[y] = y;
        cnt++;
    }
    int cc() {
        return cnt;
    }

private :
    int n, cnt;
    vector<int> sz;
    vector<int> par;
    stack<pii> stk;

    int find(int x) {
        if (par[x] == x) return x;
        else return find(par[x]);
    }
};

struct Query {
    int l, r, l_block, r_block, qid;

    bool operator<(const Query &rhs) const {
        if (l_block == rhs.l_block) {
            return r < rhs.r;
        }
        return l_block < rhs.l_block;
    }
};

int n, m, q, k;
vector<Edge> edges;
vector<Query> query;
int L[maxn], R[maxn], ans[maxn];

void init() {
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        edges.pb({u, v});
    }
    k = sqrt(m);

    cin >> q;
    int l, r;
    for (int i = 0; i < q; i++) {
        cin >> l >> r;
        l--, r--;
        query.pb({l, r, l / k, r / k, i});
    }
    sort(ALL(query));

    int tot = m / k;
    for (int i = 0; i < tot; i++) {
        L[i] = i * k;
        R[i] = (i + 1) * k - 1;
    }
    if (R[tot - 1] < m - 1) {
        tot++;
        L[tot - 1] = R[tot - 2] + 1;
        R[tot - 1] = m - 1;
    }
}

void solve() {
    DSU dsu(n);
    int l = -1, r = m, last_block = -1, r_cnt = 0;
    for (auto [ql, qr, l_block, r_block, qid] : query) {
        if (last_block < l_block) {
            while (r_cnt > 0) {
                dsu.undo();
                r_cnt--;
            }        
            l = R[l_block] + 1;
            r = R[l_block];
            last_block = l_block;
        }
        if (l_block == r_block) {
            for (int i = ql; i <= qr; i++) {
                dsu.merge(edges[i]);
            }
            ans[qid] = dsu.cc();
            for (int i = ql; i <= qr; i++) {
                dsu.undo();
            }
        } else {
            while (r < qr) {
                dsu.merge(edges[++r]);
                r_cnt++;
            }

            int l_cnt = 0;
            while (l > ql) {
                dsu.merge(edges[--l]);
                l_cnt++;
            }
            ans[qid] = dsu.cc();
            while (l_cnt > 0) {
                dsu.undo();
                l_cnt--;
            }
            l = R[l_block] + 1;
        }
    }
    for (int i = 0; i < q; i++) {
        cout << ans[i] << '\n';
    }
}

signed main() {
    init();
    solve();
} 

TIOJ 1902 . 「殿仁．王，不認識，誰啊？」，然後他就死了……

給一個長度為 \(n\) 的序列 \(a_1,\ldots ,a_n\)，有 \(q\) 筆詢問 :

• 給區間 [l, r]，問在這個區間內的 maximum xor sum

\(n,q\le 10^5,a_i\le 10^9\)

樹上莫隊

SPOJ COT2

給一個 n 個點的樹，每個點有一個權值 \(w_i\)，有 q 筆詢問如下 :

• \(\text{query}(u,v):\) 輸出 u 到 v 的路徑上 distinct number 數量

\(n\le 4\times 10^4,q\le 10^5\)

思路

打成 dfs order，不妨設 in[x] < in[y] （也就是先訪問 x，再訪問 y），分 2 種 case 討論 :

若 lca(x,y) = x，這時 x, y 在一條鏈上，那麼 in[x] 到 in[y] 這段區間中，有的點出現了兩次，有的點沒有出現過，這些點都是對答案沒有貢獻的，我們只需要統計出現過 1 次的點就好比如當詢問為 2, 6 時，[ in[x], in[y] ] = 2, 3, 4, 4, 5, 5, 6，4, 5 這兩個點都出現了兩次，因此不統計進入答案

若 lca(x,y) != x，此時 x, y 位於不同的子樹內，我們只需要按照上面的方法統計out[x] 到 in[y] 這段區間內的點。比如當詢問為 4, 7 時，[ out[4], in[7] ] = 4, 5, 5, 6, 6, 3, 7。大家發現了什麼？沒錯！我們沒有統計 lca，因此我們需要特判 lca

參考 : https://www.cnblogs.com/zwfymqz/p/9223425.html

code

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 40005;
const int MAXM = 100005;
const int LN = 19;

int N, M, K, cur, A[MAXN], LVL[MAXN], DP[LN][MAXN];
int BL[MAXN << 1], ID[MAXN << 1], VAL[MAXN], ANS[MAXM];
int d[MAXN], l[MAXN], r[MAXN];
bool VIS[MAXN];
vector < int > adjList[MAXN];

struct query{
    int id, l, r, lc;
    bool operator < (const query& rhs){
        return (BL[l] == BL[rhs.l]) ? (r < rhs.r) : (BL[l] < BL[rhs.l]);
    }
}Q[MAXM];

// Set up Stuff
void dfs(int u, int par){
    l[u] = ++cur; 
    ID[cur] = u;
    for (int i = 1; i < LN; i++) DP[i][u] = DP[i - 1][DP[i - 1][u]];
    for (int i = 0; i < adjList[u].size(); i++){
        int v = adjList[u][i];
        if (v == par) continue;
        LVL[v] = LVL[u] + 1;
        DP[0][v] = u;
        dfs(v, u);
    }
    r[u] = ++cur; ID[cur] = u;
}

// Function returns lca of (u) and (v)
inline int lca(int u, int v){
    if (LVL[u] > LVL[v]) swap(u, v);
    for (int i = LN - 1; i >= 0; i--)
        if (LVL[v] - (1 << i) >= LVL[u]) v = DP[i][v];
    if (u == v) return u;
    for (int i = LN - 1; i >= 0; i--){
        if (DP[i][u] != DP[i][v]){
            u = DP[i][u];
            v = DP[i][v];
        }
    }
    return DP[0][u];
}

inline void check(int x, int& res){
    // If (x) occurs twice, then don't consider it's value 
    if ( (VIS[x]) and (--VAL[A[x]] == 0) ) res--; 
    else if ( (!VIS[x]) and (VAL[A[x]]++ == 0) ) res++;
    VIS[x] ^= 1;
}

void compute(){

    // Perform standard Mo's Algorithm
    int curL = Q[0].l, curR = Q[0].l - 1, res = 0;

    for (int i = 0; i < M; i++){

        while (curL < Q[i].l) check(ID[curL++], res);
        while (curL > Q[i].l) check(ID[--curL], res);
        while (curR < Q[i].r) check(ID[++curR], res);
        while (curR > Q[i].r) check(ID[curR--], res);

        int u = ID[curL], v = ID[curR];

        // Case 2
        if (Q[i].lc != u and Q[i].lc != v) check(Q[i].lc, res);

        ANS[Q[i].id] = res;

        if (Q[i].lc != u and Q[i].lc != v) check(Q[i].lc, res);
    }

    for (int i = 0; i < M; i++) printf("%d\n", ANS[i]);
}

int main(){

    int u, v, x;

    while (scanf("%d %d", &N, &M) != EOF){

        // Cleanup
        cur = 0;
        memset(VIS, 0, sizeof(VIS));
        memset(VAL, 0, sizeof(VAL));
        for (int i = 1; i <= N; i++) adjList[i].clear();

        // Inputting Values
        for (int i = 1; i <= N; i++) scanf("%d", &A[i]);
        memcpy(d + 1, A + 1, sizeof(int) * N);

        // Compressing Coordinates
        sort(d + 1, d + N + 1);
        K = unique(d + 1, d + N + 1) - d - 1;
        for (int i = 1; i <= N; i++) A[i] = lower_bound(d + 1, d + K + 1, A[i]) - d;

        // Inputting Tree
        for (int i = 1; i < N; i++){
            scanf("%d %d", &u, &v);
            adjList[u].push_back(v);
            adjList[v].push_back(u);
        }

        // Preprocess
        DP[0][1] = 1;
        dfs(1, -1);
        int size = sqrt(cur);

        for (int i = 1; i <= cur; i++) BL[i] = (i - 1) / size + 1;

        for (int i = 0; i < M; i++){
            scanf("%d %d", &u, &v);
            Q[i].lc = lca(u, v);
            if (l[u] > l[v]) swap(u, v);
            if (Q[i].lc == u) Q[i].l = l[u], Q[i].r = l[v];
            else Q[i].l = r[u], Q[i].r = l[v];
            Q[i].id = i;
        }

        sort(Q, Q + M);
        compute();
    }
}

---

參考資料

• https://sam571128.codes/2020/10/03/MO-Algorithm/

• https://cp.wiwiho.me/mo-algorithm/

• https://docs.google.com/document/d/11-Ho9_nnds76VdfBfDQC7U1sYjXVrlNgEurdZ4ykL4s/edit#heading=h.isbo4ewxeenw

• https://drive.google.com/file/d/1F73WYrDtwoH_VtjYK4qicKDuEFDu9OqY/view

• https://hackmd.io/@iceylemon157/HkdBTBJEK

• https://www.cnblogs.com/RioTian/p/15113195.html

• https://zhuanlan.zhihu.com/p/369836899

• https://codeforces.com/blog/entry/43230

---

1. [2, 5] → [6, 7] 如果先移動左邊，可能會變成 [6, 5]，無法保證左界小於等於右界 ↩