[資料結構] 掃描線

2021-06-08

tutorial

[Feb 2 2025] 更新部分敘述。

先備知識

線段樹

掃描線只是一種概念，當初在寫下這篇時基本上都是整理有關線段樹的技巧。以下的題目都是主要以線段樹為主軸，但事實上沒有掃描線題都離不開線段樹這回事。

經典題 - 矩形覆蓋面積計算

Link - TIOJ 1224

給你 $N$ 個矩形，四邊範圍 $0 \leq L, R, D, U \leq 10^6$，問你總覆蓋面積（重疊的只算一次）是多少。

做法

直接扣掉重疊面積好像有點難，又不太容易套二維資料結構 ¹，不如把每次覆蓋區域不一樣的地方都切成一條長條型，這樣要計算的東西就是 $覆蓋量 \times 高度$，不過要怎麼維護覆蓋量？

參考上面這張圖，當我加入一個矩形的時候，必須要對區間都加一次值（代表多被覆蓋一次），同樣，當一個矩形被掃完的時候，必須要對區間都扣一次值（代表少被覆蓋一次），但是每次我想知道的是有多少非 $0$ 的值（代表覆蓋到的實際面積），這樣就把原本的問題換成了區間操作的問題。

實作上可以使用線段樹，由於在線段樹上一個區間可以被拆成 $\log N$ 個區間，所以在每個區間的值就是

如果被蓋到，就是整個區間的長度
否則，回傳兩個子區間相加

這樣，總複雜度 $\mathcal O(N \log N)$。

基本概念差不多只有這樣，不過要做到更好，可以對區間做離散化，做起來會跟一般線段樹不太一樣，但基本上都是對區間做出修改。

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define F first
#define S second
#define pb(x) emplace_back(x)
#define fast ios::sync_with_stdio(0), cin.tie(0)
using namespace std;

int n, m, seg[400000], lazy[400000];
ll ans;
vector<int> t;
vector<int> pos;
vector<pair<int, pii>> add;
vector<pair<int, pii>> rem;

void push(int l, int r, int i)
{
    if (lazy[i] > 0)
    {
        lazy[i * 2] += lazy[i];
        lazy[i * 2 + 1] += lazy[i];
        lazy[i] = 0;
        seg[i] = (pos[r] - pos[l]);
    }
}

void pull(int l, int r, int i)
{
    int mid = (l + r) / 2;
    if (lazy[i] > 0)
        seg[i] = (pos[r] - pos[l]);
    else
        seg[i] = (lazy[i * 2] > 0     ? (pos[mid] - pos[l]) : seg[i * 2]) + 
                 (lazy[i * 2 + 1] > 0 ? (pos[r] - pos[mid]) : seg[i * 2 + 1]);
}

void modify(int l, int r, int i, int a, int b, int val)
{

    if (l == r)
        return;
    if (b <= l || r <= a)
        return;
    if (a <= l && r <= b)
        lazy[i] += val;
    else
    {
        int mid = (l + r) / 2;
        modify(l, mid, i * 2, a, b, val);
        modify(mid, r, i * 2 + 1, a, b, val);
    }
    pull(l, r, i);
}

signed main()
{
    fast;
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int l, r, d, u;
        cin >> l >> r >> d >> u;
        t.pb(d);
        t.pb(u);
        pos.pb(l);
        pos.pb(r);
        add.pb(make_pair(d, pii{l, r}));
        rem.pb(make_pair(u, pii{l, r}));
    }
    t.pb(-1);
    sort(t.begin(), t.end());
    t.resize(unique(t.begin(), t.end()) - t.begin());
    sort(pos.begin(), pos.end());
    pos.resize(unique(pos.begin(), pos.end()) - pos.begin());
    sort(add.begin(), add.end(), greater<pair<int, pii>>());
    sort(rem.begin(), rem.end(), greater<pair<int, pii>>());
    for (int i = 1; i < t.size(); i++)
    {
        pull(0, pos.size() - 1, 1);
        ans += (ll)(t[i] - t[i - 1]) * seg[1];
        while (!add.empty() && add.back().F == t[i])
        {
            int L = lower_bound(pos.begin(), pos.end(), add.back().S.F) - pos.begin(),
                R = lower_bound(pos.begin(), pos.end(), add.back().S.S) - pos.begin();
            modify(0, pos.size() - 1, 1, L, R, 1);
            add.pop_back();
        }
        while (!rem.empty() && rem.back().F == t[i])
        {
            int L = lower_bound(pos.begin(), pos.end(), rem.back().S.F) - pos.begin(),
                R = lower_bound(pos.begin(), pos.end(), rem.back().S.S) - pos.begin();
            modify(0, pos.size() - 1, 1, L, R, -1);
            rem.pop_back();
        }
    }
    cout << ans << '\n';
}

整理

剛剛我們做了什麼事讓原本 $\mathcal O(N^2)$ 的事降到 $\mathcal O(N \log N)$？一個很重要的關鍵是，對於原本的問題，本來要按照輸入順序做的東西，把他按照順序排好之後， 用時間掃過一個維度（或是一項要維護的問題），然後其他按照順序去做處理。

接下來有很多掃描線的問題可能題目並沒有一個圖，但實際觀點有點像在平面上維護一些性質。

例題 - Codeforces 524E Rooks and Rectangles

Link

給你一個 $N \times M$ 的矩形，上面有 $K$ 個城堡（可以走直或橫）， $Q$ 次詢問一個矩形是不是每格都被矩形內的城堡保護到。

$N,\ M \leq 10^5$
$K,\ Q \leq 2 \times 10^5$

觀察

一個矩形要被完全保護到，一定滿足：

直的每一列上都要有城堡
否則橫的每一行都要有城堡

所以問題就簡單一點了，問題是單獨查詢每一列複雜度是可怕的 $\mathcal O(QN\log N)$。

做法

首先，有了剛才的觀察，就只要先討論一個方向就好，另一個方向可以用一樣的方法解決。

看到二維的東西，然而又不能用二維的資料結構處理，所以轉向去思考：有沒有可能用時間慢慢掃過一維處理？

想像一條掃描線從左掃到右，記錄當下的狀況，但是遇到的問題是：查詢不僅是在線上的一個區間，還有時效的限制。

剛剛想到用時間處理一維，但是掃描線只解決了右界的問題，那左界呢？可以想成過期的條件，也就是說我可以查看看最好的解，再回來用左界看看他是不是過期了，如果這個最好的解過期了，表示其他所有解都一定過期了。

換句話說，當我掃到一個查詢的右界的時候，在當下就回答那個查詢，並且對所有左界都可以處理那個查詢。

實作

既然我們有把「左界當成過期」的想法，那要怎麼知道有沒有過期？剛剛有提到，「先查看看最好的解，再看看他有沒有過期」，所以對於每一橫排，當我掃到 $R$ 的時候，需要把左邊所有的城堡都放進去，也就是保留 $R-1$ 的狀況，新增在 $R$ 上的城堡，

當我遇到那一橫排有新的加入，就覆蓋掉前面的，因為當我回答的時候可以想像成從右界開始往左掃回去，所以越右邊的會越好。查詢的時候只要看區間裡最早出現的元素（最小值），再拿去跟左界比較有沒有過期。

時間複雜度 $\mathcal O(Q \log Q + Q \ log N + K \log N )$。

Code

類題 - Codeforces 833B The Bakery

Link

給你一個長度為 $N$ 的陣列，要你剛好切成 $K$ 塊，其中每塊的價值是那一塊中相異元素的數量，問最大價值。

觀察

稍微想一下，可以設出 DP 狀態： $dp[i][j]$ 表示已經安排好 $[1, i]$ 的部分，而且已經切了 $j$ 塊的最大價值。問題是轉移時需要 $\mathcal O(N)$，需要優化。

但是看一下 DP 計算的順序，剛好是 $1 \rightarrow N$，這樣來看，似乎可以套用掃描線的技巧？

做法

如果我需要用線段樹加速DP，就要想辦法維護轉移的價值，這樣只要單點修改加上之前的 DP 值就可以在 $\mathcal O(\log N)$ 的時間計算出來，觀察到每個數字排在一行上，其實跟上一題的情況有點像，只需要改一下維護的值，當同樣一個數字出現的時候，需要對 $[上次出現+1, 這次出現]$ 加值，

Code

類題 - TIOJ 1872 最小公倍數

Link - TIOJ 1872

給定一個長度為 $N$ 的陣列 $c$，$Q$ 次查詢區間最小公倍數$\mod 10^9 + 7$。 $N,\ Q,\ c_i \leq 10^6$。

觀察

區間中的 LCM 似乎沒有辦法好好的用兩個數字的 LCM 做，是一個最大的問題。

區間 $[i, j]$ 要求的其實是 $\prod_{p \in \mathbb{P}}p_k^{\max{a_k}}$。但是直接對每個質數維護是不夠好的，複雜度為
$\mathcal O(Q \frac{N}{\log N} \log N ) = \mathcal O(QN)$。（質數個數 $\mathcal O(\frac{N}{\log N})$）

做法

把質因數分解之後，一一對齊會長的像是：

還記得剛剛優化的核心概念嗎？

當我掃到一個查詢的右界的時候，在當下就回答那個查詢，並且對所有左界都可以處理那個查詢。

也就是說，從右界往左的所有後綴區間都是有效的。這裡我的做法用區間乘積維護答案，對於每個質數都要有一個單調隊列依序遞減，所以區間乘積就要透過差分去做拆解：

當新的次方較大，就把舊的刪除
否則，差分完丟進我們維護的線段樹內

如觀察所述，我需要做到：

質數篩 + DP $\mathcal O(C + \sqrt C \log \log C)$
質因數分解 $\mathcal O(\log C)$
按右界 sort 一次查詢 $\mathcal O(Q \log Q)$
每次對 $\mathcal O(\dfrac{\log C}{\log \log C})$ 個質因數的單調隊列更新，均攤 $\mathcal O(1)$
每次單調隊列更新就更新線段樹 $\mathcal O(\log N)$
回答查詢 $\mathcal O(Q\log N)$

總複雜度 $\mathcal O\left(C + Q\log Q + Q \log N + \frac{ N \log N \log C}{\log \log C} + N \log C\right)$。

Code

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
/*  | |       _    _  | |        _____       | |
//  | |   _  | |  | | | | _____ /  ___|__  __| |___  _____
//  | |  |_|[   ][   ]| |/  _  \| |    | | | |  _  \/  _  \  
//  | L__| | | |_ | |_| || ____|| |___ | |_| | |_| || ____|
//  L____|_| |___||___|_|\_____|\_____|\_____/\____/\_____|
//  Segment Tree is hard.
*/
#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
#pragma pack(0)
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
#define MOD 1000000007
#define fast ios::sync_with_stdio(0), cin.tie(0)
using namespace std;

struct Q
{
    ll i, l, r;
};

ll n, q, arr[1000005], sieve[1000005], seg[4000000], prime[1000005], idx = 1, ans[1000005];
vector<pii> mq[1000000];
vector<Q> query;

ll fastpow(ll base, ll p)
{
    ll a = 1, b = base;
    while (p > 0)
    {
        if (p & 1)
            a = a * b % MOD;
        b = b * b % MOD;
        p >>= 1;
    }
    return a;
}

void Modify(int l, int r, int i, int pos, ll val)
{
    seg[i] = seg[i] * val % MOD;
    if (l == r)
        return;
    int mid = (l + r) / 2;
    if (pos <= mid)
        Modify(l, mid, i * 2, pos, val);
    else
        Modify(mid + 1, r, i * 2 + 1, pos, val);
}

ll Query(int l, int r, int i, int a, int b)
{
    if (a <= l && r <= b)
        return seg[i];
    else if (b < l || r < a)
        return 1;
    else
    {
        int mid = (l + r) / 2;
        return Query(l, mid, i * 2, a, b) * Query(mid + 1, r, i * 2 + 1, a, b) % MOD;
    }
}

signed main()
{
    fast;
    for (int i = 2; i <= 1000000; i += 2)
        sieve[i] = 2;
    prime[2] = 1;
    for (int i = 3; i <= 1000000; i += 2)
        if (sieve[i] == 0)
        {
            sieve[i] = i;
            prime[i] = ++idx;
            for (int j = i * i; j <= 1000000; j += i)
                sieve[j] = i;
        }

    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> arr[i];
    for (int i = 1; i <= q; i++)
    {
        int l, r;
        cin >> l >> r;
        query.emplace_back(Q{i, l, r});
    }
    for (int i = 1; i < 4000000; i++)
        seg[i] = 1;

    sort(query.begin(), query.end(), [](Q q1, Q q2) { return q1.r < q2.r; });
    idx = 0;

    for (int i = 1; i <= n; i++)
    {
        while (arr[i] > 1)
        {
            ll base = sieve[arr[i]], p = 0;
            while (arr[i] % base == 0)
                arr[i] /= base, p++;
            while (!mq[prime[base]].empty() && p >= mq[prime[base]].back().S)
            {
                pii last = mq[prime[base]].back();
                Modify(1, 1000000, 1, last.F, fastpow(base, last.S * (MOD - 2) % (MOD - 1)));
                mq[prime[base]].pop_back();

                if (!mq[prime[base]].empty())
                    Modify(1, 1000000, 1, mq[prime[base]].back().F, fastpow(base, last.S));
            }
            ll res = fastpow(base, p);
            Modify(1, 1000000, 1, i, res);
            if (!mq[prime[base]].empty())
                Modify(1, 1000000, 1, mq[prime[base]].back().F, fastpow(res, MOD - 2));
            mq[prime[base]].emplace_back(make_pair(i, p));
        }
        while (idx < q && query[idx].r == i)
        {
            ans[query[idx].i] = Query(1, 1000000, 1, query[idx].l, query[idx].r);
            idx++;
        }
        if (idx > q - 1)
            break;
    }
    for (int i = 1; i <= q; i++)
        cout << ans[i] << '\n';
}

離線限制？

剛剛所有提到的做法都要剛剛好是離線 sort 的狀態，那有沒有可以在線回答的方法呢？

答案是有，只要有效率地把所有東西都存下來就可以，如果以線段樹作為儲存資料結構，那只要把它持久化就可以做到在線詢問了。

還是可行的，但是用二維 BIT 複雜度是 $O(N\log^2N + N^2)$，沒有任何改進。 ↩︎