前置知識

分塊思想
熟練掌握 STL 演算法

莫隊思想

先來看一道例子，給出下面的一個序列，給出一個區間，求區間和：

下標	1	2	3	4	5	6
\(A\)	2	1	1	3	4	3

如果這道題不涉及修改操作，大家都會想到預處理前綴和，現在我強制要求使用莫隊，要怎么做呢？假設我們要求 \(S_{[2,4]}\) 的和，并且知道了 \(S_{[2,3]}\)，可以想到用 \(S_{[2,3]}\)加上 \(A_4\)，這樣就能夠得到答案了，同理，如果我們知道了 \(S_{[3,4]}\)，\(S_{[2,4]} = S_{[3,4]} + A_2\)，這些操作實際上就是移動區間的一個端點，同時把新的端點的答案合并，莫隊就是這樣，如果已經知道了一個區間的答案，就試圖通過移動區間邊界，把原來的答案與新的邊界的值合并，最終讓當前區間與詢問的區間重合，然后記錄答案，

但是，現在又有一個問題了，如果有一個序列，長度為 \(n\)，詢問 \(m\) 次，按照 \([1,2],[n-1,n],[3,4],[n-3,n-2],\cdots\) 詢問，那時間復雜度就變成了 \(O(nm)\) 級別了，顯然不利于解題，于是莫濤大佬又想出了一個解決方案，把序列分塊，再把詢問排序，按照排序后的詢問區間處理答案，對于兩個詢問區間，如果兩個區間的左端點在同一個塊，就比較它們的右端點，否則比較左端點，對于上面的那些詢問，排序后，時間復雜度減小至 \(\Theta(n+m)\)，對于一般情況下，這樣的時間復雜度是 \(O(n\sqrt{n})\)，~~但我不會證明 QwQ，~~

代碼模板

通過上面的介紹，我們來系統地總結一下移動區間端點的 \(4\) 種情況（上面只舉例了兩種），記當前區間為 \([l,r]\)，詢問區間為 \([L,R]\)，用代碼說明，

情況	代碼實作
\(L < l\)	`while (L < l) add(--l);`
\(R > r\)	`while (R > r) add(++r);`
\(L > l\)	`while (L > l) sub(l++);`
\(R < r\)	`while (R < r) sub(r--);`

前兩種情況是擴大區間，就把新端點的答案加到總答案里，后兩種相反，把舊端點的答案從總答案里洗掉，

接下來，看看莫隊演算法的框架，

// ...
struct query {
    int l, r, id; // 詢問區間以及它是第幾個詢問
};

constexpr int maxn = /* ... */; // 序列長度
constexpr int maxq = /* ... */; // 詢問個數
query qs[maxq];
int arr[maxn], ans[maxq], n, q, res, blocksize; // res 表示臨時計算的答案，會隨著區間的移動不斷更新

inline int blockid(int x) { return (x - 1) / blocksize + 1; }

inline void add(int x) {
    // ...
}

inline void sub(int x) {
    // ...
}

void solve() {
    // ...
    blocksize = sqrt(n); // 計算塊的大小
    sort(qs + 1, qs + 1 + q, [](const query &a, const query &b) { // 排序區間
        return blockid(a.l) == blockid(b.l) ？ a.r < b.r : a.l < b.l;
    }); // 這里使用了 Lambda 運算式
    int l = 1, r = 0; // 一開始區間是空的，這樣寫是為了符合語意
    for (int i = 1; i <= q; ++i) { // 處理詢問
        while (qs[i].l < l)
            add(--l);
        while (qs[i].r > r)
            add(++r);
        while (qs[i].l > l)
            sub(l++);
        while (qs[i].r < r)
            sub(r--);
        ans[qs[i].id] = res; // 記錄答案
    }
    // ...
}

演算法優化

排序后的區間順序其實對處理的速度有較大的影響，實際上，我們一般采用一個叫做奇偶化排序的東西，如果塊的編號是奇數，就按右端點升序排序，否則按降序排序，它的原理大致是——如果處理完奇數塊，\(r\) 這個指標就可以不用再跑更遠，從前開始往后掃描，可以看看下面這個詢問的例子：

// blocksize = 3
1 1
2 25
3 50
4 1
5 25
6 50

用了奇偶化排序后，速度可以提升大約 \(30\%\)，

代碼實作：

sort(qs + 1, qs + 1 + q, [](const query &a, const query &b) {
    return blockid(a.l) == blockid(b.l)
               ? (a.r == b.r ? 0 : !((blockid(a.l) & 1) && (a.r < b.r)))
               : a.l < b.l;
});

例題講解

SPOJ 3267 D-query

給出一個長度為 \(n\) 的序列，進行 \(q\) 次詢問，每次詢問給出區間 \([l,r]\)，問區間去重后有多少個數？

唯一需要注意的就是多維護一個陣列，記為 cnt[i]，表示第值為 \(i\) 的數目前出現了多少次，很顯然，直接在 add(x) 和 sub(x) 里更新，看代碼，

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

template <typename T> T read() {
    T x = 0, s = 1;
    char c = getchar();
    while (c < '0' || '9' < c) {
        if (c == '-')
            s = -1;
        c = getchar();
    }
    while ('0' <= c && c <= '9') {
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * s;
}

struct query {
    int l, r, id;
};

constexpr int maxn = 30000 + 5;
constexpr int maxv = 1e6 + 5;
constexpr int maxq = 200000 + 5;
query qs[maxq];
int arr[maxn], cnt[maxv], ans[maxq], n, q, res, blocksize;

inline int blockid(int x) { return (x - 1) / blocksize + 1; }

inline void add(int x) {
    ++cnt[arr[x]];
    if (cnt[arr[x]] == 1)
        ++res;
}

inline void sub(int x) {
    --cnt[arr[x]];
    if (!cnt[arr[x]])
        --res;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("Environment/project.in", "r", stdin);
    freopen("Environment/project.out", "w", stdout);
#endif
    n = read<int>();
    blocksize = sqrt(n);
    for (int i = 1; i <= n; ++i)
        arr[i] = read<int>();
    q = read<int>();
    for (int i = 1; i <= q; ++i) {
        qs[i].l = read<int>();
        qs[i].r = read<int>();
        qs[i].id = i;
    }
    sort(qs + 1, qs + 1 + q, [](const query &a, const query &b) {
        return blockid(a.l) == blockid(b.l)
                   ? (a.r == b.r ? 0 : (blockid(a.l) & 1) ^ (a.r < b.r))
                   : a.l < b.l;
    });
    int l = 1, r = 0;
    for (int i = 1; i <= q; ++i) {
        while (qs[i].l < l)
            add(--l);
        while (qs[i].r > r)
            add(++r);
        while (qs[i].l > l)
            sub(l++);
        while (qs[i].r < r)
            sub(r--);
        ans[qs[i].id] = res;
    }
    for (int i = 1; i <= q; ++i)
        printf("%d\n", ans[i]);
    return 0;
}

Luogu P1494 小Z的襪子

有一個長度為 \(n\) 的序列，進行 \(q\) 次詢問，每次詢問給出區間 \([l,r]\)，問隨機從區間選兩個數相等的概率是多少？使用最簡分數輸出，

同樣是要維護 cnt[i]，對于區間 \([l,r]\)，選取兩個數的方案數是 \(\binom{r-l+1}{2}\)，而選取到相同兩個數的方案數是 \(\sum_{i=1}^{N}\binom{cnt[i]}{2}\)，概率就是它們相除，我們可以維護一下后面的這個方案數，前一個直接計算，每次移動區間端點都是差不多的，以擴大區間為例，要先減去之前的答案，再加上 cnt[i] + 1 的答案，那么加在一起就是 \(\binom{cnt[i]+1}{2}-\binom{cnt[i]}{2}\)，這個式子是可以化簡的：

\[\begin{aligned}\binom{cnt[i]+1}{2}-\binom{cnt[i]}{2}&=\frac{(cnt[i]+1)!}{2!(cnt[i]-1)!}-\frac{cnt[i]}{2!(cnt[i]-2)}\\&=\frac{cnt[i](cnt[i]+1)}{2}-\frac{cnt[i](cnt[i]-1)}{2}\\&=\frac{2cnt[i]}{2}\\&=cnt[i]\end{aligned} \]

縮小區間也是一樣的，你可以再推導一遍，也可以先把 cnt[i] 減去 \(1\)，然后讓臨時答案減去 cnt[i]，可以想想為什么，

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

template <typename T> T read() {
    T x = 0, s = 1;
    char c = getchar();
    while (c < '0' || '9' < c) {
        if (c == '-')
            s = -1;
        c = getchar();
    }
    while ('0' <= c && c <= '9') {
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * s;
}

struct query {
    int l, r, id;
};

constexpr int maxn = 50000 + 5;
query qs[maxn];
int arr[maxn], cnt[maxn], n, q, blocksize;
long long ans[maxn][2], res;

inline int blockid(int x) { return (x - 1) / blocksize + 1; }

inline void add(int x) { res += cnt[arr[x]]++; }

inline void sub(int x) { res -= --cnt[arr[x]]; }

long long GCD(long long x, long long y) { return y == 0 ? x : GCD(y, x % y); }

int main() {
#ifndef ONLINE_JUDGE
    freopen("Environment/project.in", "r", stdin);
    freopen("Environment/project.out", "w", stdout);
#endif
    n = read<int>();
    q = read<int>();
    blocksize = sqrt(n);
    for (int i = 1; i <= n; ++i)
        arr[i] = read<int>();
    for (int i = 1; i <= q; ++i) {
        qs[i].l = read<int>();
        qs[i].r = read<int>();
        qs[i].id = i;
    }
    sort(qs + 1, qs + 1 + q, [](const query &a, const query &b) {
        return blockid(a.l) == blockid(b.l)
                   ? (a.r == b.r ? 0 : (blockid(a.l) & 1) ^ (a.r < b.r))
                   : a.l < b.l;
    });
    int l = 1, r = 0;
    for (int i = 1; i <= q; ++i) {
        if (qs[i].l == qs[i].r) {
            ans[qs[i].id][0] = 0;
            ans[qs[i].id][1] = 1;
            continue;
        }
        while (qs[i].l < l)
            add(--l);
        while (qs[i].r > r)
            add(++r);
        while (qs[i].l > l)
            sub(l++);
        while (qs[i].r < r)
            sub(r--);
        ans[qs[i].id][0] = res;
        ans[qs[i].id][1] = (1LL * (r - l) * (r - l + 1)) >> 1;
    }
    for (int i = 1; i <= q; ++i) {
        long long g = GCD(ans[i][0], ans[i][1]);
        printf("%lld/%lld\n", ans[i][0] / g, ans[i][1] / g);
    }
    return 0;
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/73569.html

標籤：其他

上一篇：redis創建集群

下一篇：word尾注后面怎么插入新的一頁

【演算法】莫隊演算法粗略講解

前置知識

莫隊思想

代碼模板

演算法優化

例題講解