Sweep Line

Sự kiện mở, đóng

Đoạn $[l, r]$ trên tọa độ nguyên cho hai sự kiện: $+1$ tại $l$, $-1$ tại $r + 1$ (đoạn nửa mở $[a, b)$ thì $-1$ tại $b$). Sắp mọi sự kiện theo tọa độ; quét qua và cộng dồn, giá trị hiện tại là mức phủ của đoạn từ sự kiện này tới sự kiện kế tiếp.

Đây là mảng hiệu (bài 02) khi tọa độ quá lớn để lập mảng: chỉ lưu những điểm có thay đổi. Hai sự kiện cùng tọa độ thì xử lý hết rồi mới đọc mức phủ, hoặc xếp thứ tự theo đúng nghĩa đề (đóng trước mở khi đoạn nửa mở chạm nhau).

Muốn biết có bao nhiêu tọa độ được phủ đúng $k$ lần: sau khi xử lý mọi sự kiện tại $x$, mức phủ $c$ giữ nguyên tới sự kiện kế tiếp $x'$, nên cộng $x' - x$ vào ô đáp án thứ $c$. Sự kiện cùng tọa độ cách nhau 0, nên không cần tách riêng.

Ví dụGiờ Cao Điểm

Đề. $n \le 2 \cdot 10^5$ khoảng nửa mở $[a_i, b_i)$, mọi đầu mút khác nhau. Tìm số khoảng cùng phủ một thời điểm nhiều nhất.

Lời giải. Mỗi khoảng sinh hai sự kiện: $+1$ tại $a_i$ (bắt đầu), $-1$ tại $b_i$ (kết thúc). Sắp theo thời điểm rồi cộng dồn: sau mỗi sự kiện, tổng đang có là số khoảng đang mở, và đáp án là giá trị lớn nhất của nó.

Bước 1: sinh sự kiện.

ev.push_back({a, 1});
ev.push_back({b, -1});

Bước 2: sắp và quét.

sort(ev.begin(), ev.end());
ll cur = 0, best = 0;
for (pair<ll, ll> e : ev) {
    cur += e.second;
    best = max(best, cur);
}

Khoảng nửa mở nên khi trùng thời điểm, sự kiện $-1$ phải đứng trước $+1$; pair sắp $-1$ trước $1$ một cách tự nhiên. Ở bài này các đầu mút khác nhau nên chi tiết đó không phát sinh.

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

ll n;
vector<pair<ll, ll>> ev;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (ll i = 1; i <= n; i++) {
        ll a, b;
        cin >> a >> b;
        ev.push_back({a, 1});
        ev.push_back({b, -1});
    }
    sort(ev.begin(), ev.end());
    ll cur = 0, best = 0;
    for (pair<ll, ll> e : ev) {
        cur += e.second;
        best = max(best, cur);
    }
    cout << best << '\n';
}

ChạyInput4
1 4
2 5
6 8
3 7

Output3

Độ phức tạp: $O(n \log n)$ cho phần sắp.

Gán phòng

Muốn gán mỗi khoảng vào một phòng (máy, nhân viên) sao cho hai khoảng chồng nhau không cùng phòng, và dùng ít phòng nhất: quét các khoảng theo thời điểm bắt đầu, giữ hàng đợi ưu tiên các phòng đang dùng theo thời điểm rảnh. Khoảng mới bắt đầu sau khi phòng rảnh sớm nhất đã rảnh thì dùng lại phòng đó, không thì mở phòng mới. Số phòng mở ra bằng mức phủ lớn nhất, cận dưới hiển nhiên, nên là tối ưu.

Ví dụPhân Phòng Tối Thiểu

Đề. $n \le 2 \cdot 10^5$ lượt, lượt $i$ chiếm các ngày $a_i..b_i$; hai lượt chung một ngày phải khác phòng. In số phòng ít nhất và phòng của từng lượt.

Lời giải. Xét lượt theo ngày bắt đầu tăng dần. Tới lượt bắt đầu ngày $a$, nếu có phòng đã rảnh trước ngày $a$ thì dùng lại, không thì mở phòng mới. Cách này dùng đúng số phòng bằng số lượt cùng chung một ngày nhiều nhất: mỗi lần phải mở phòng mới là lúc mọi phòng đang có đều bận vào ngày $a$. Không thể ít hơn số đó, nên là tối ưu.

Bước 1: sắp chỉ số theo ngày bắt đầu. Giữ chỉ số gốc để in phòng theo thứ tự đầu vào.

sort(id + 1, id + n + 1, cmp);

Bước 2: phòng rảnh sớm nhất. pq chứa các phòng đang dùng dưới dạng (ngày cuối, số phòng), sắp theo ngày cuối tăng dần. Ngày cuối nhỏ hơn hẳn $a$ (ngày đóng, nên phải nhỏ hơn hẳn) thì dùng lại phòng đó; ngược lại mở phòng mới. Cuối cùng đẩy lại (ngày cuối của lượt này, phòng).

for (ll t = 1; t <= n; t++) {
    ll i = id[t];
    if (!pq.empty() && pq.top().first < a[i]) {
        room[i] = pq.top().second;
        pq.pop();
    } else room[i] = ++k;
    pq.push({b[i], room[i]});
}

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

const ll N = 2e5 + 5;
ll n, a[N], b[N], id[N], room[N];

bool cmp(ll x, ll y) {
    return a[x] < a[y];
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (ll i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];
        id[i] = i;
    }
    sort(id + 1, id + n + 1, cmp);
    priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
    ll k = 0;
    for (ll t = 1; t <= n; t++) {
        ll i = id[t];
        if (!pq.empty() && pq.top().first < a[i]) {
            room[i] = pq.top().second;
            pq.pop();
        } else room[i] = ++k;
        pq.push({b[i], room[i]});
    }
    cout << k << '\n';
    for (ll i = 1; i <= n; i++) cout << room[i] << ' ';
    cout << '\n';
}

ChạyInput4
1 2
2 3
4 4
3 5

Output2
1 2 2 1

Độ phức tạp: $O(n \log n)$.

Quét kèm Fenwick

Khi câu hỏi có hai chiều, quét theo chiều thứ nhất và giữ chiều thứ hai trong Fenwick (bài 16).

Đoạn $[c, d]$ nằm trong $[a, b]$ khi $a \le c$ và $d \le b$. Sắp các đoạn theo đầu trái tăng dần (bằng nhau thì đầu phải giảm dần): đoạn nằm trong $[a, b]$ là đoạn đứng sau nó có đầu phải không quá $b$. Quét từ cuối, Fenwick theo đầu phải đã nén đếm các đoạn đã thêm có đầu phải $\le b$.

Đếm giao điểm giữa đoạn ngang và đoạn dọc cũng thế. Quét theo $x$: đoạn ngang vào Fenwick theo $y$ khi đường quét gặp đầu trái và bị gỡ khi gặp đầu phải. Đoạn dọc đếm số đoạn ngang đang có trong khoảng $y$ của nó, bằng hai tổng tiền tố.

Ví dụĐếm Đoạn Bao Chứa

Đề. $n \le 2 \cdot 10^5$ đoạn khác nhau. Với mỗi đoạn, đếm số đoạn khác nằm trong nó và số đoạn khác chứa nó.

Lời giải. Sắp các đoạn theo $x$ tăng, cùng $x$ thì $y$ giảm. Khi đó đoạn chứa đoạn $i$ luôn đứng trước $i$ (đầu trái không lớn hơn, cùng đầu trái thì dài hơn), và đoạn nằm trong $i$ luôn đứng sau. Đoạn chứa $i$ là đoạn đứng trước có $y \ge y_i$; đoạn nằm trong $i$ là đoạn đứng sau có $y \le y_i$. Hai câu đếm này làm bằng Fenwick theo $y$ đã nén, một lần quét xuôi và một lần quét ngược.

Bước 1: nén $y$ và sắp. r[i] là hạng của $y_i$, dùng làm chỉ số Fenwick.

sort(ys + 1, ys + n + 1);
for (ll i = 1; i <= n; i++) r[i] = lower_bound(ys + 1, ys + n + 1, y[i]) - ys;
sort(id + 1, id + n + 1, cmp);

Bước 2: quét xuôi, đếm đoạn chứa. Có $t - 1$ đoạn đã thêm; trừ đi những đoạn có $y$ nhỏ hơn hẳn (get(r[i] - 1)), vì chúng không chứa $i$, còn lại là số đoạn chứa $i$.

for (ll t = 1; t <= n; t++) {
    ll i = id[t];
    out[i] = (t - 1) - get(r[i] - 1);
    update(r[i], 1);
}

Bước 3: xóa Fenwick, quét ngược, đếm đoạn nằm trong. get(r[i]) là số đoạn đứng sau có $y \le y_i$.

for (ll i = 1; i <= n; i++) bit[i] = 0;
for (ll t = n; t >= 1; t--) {
    ll i = id[t];
    in[i] = get(r[i]);
    update(r[i], 1);
}

Hai đoạn khác nhau cùng $x$ có $y$ khác nhau, nên không có trường hợp bằng nhau cần tách.

So mọi cặp chậm hơn quét kèm Fenwick cỡ vài trăm lần ở $n = 40000$, và $n$ càng lớn khoảng cách càng rộng.

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

const ll N = 2e5 + 5;
ll n, x[N], y[N], id[N], ys[N], r[N], bit[N], in[N], out[N];

bool cmp(ll a, ll b) {
    return x[a] != x[b] ? x[a] < x[b] : y[a] > y[b];
}

void update(ll pos, ll val) {
    for (; pos <= n; pos += pos & -pos) bit[pos] += val;
}

ll get(ll pos) {
    ll res = 0;
    for (; pos > 0; pos -= pos & -pos) res += bit[pos];
    return res;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (ll i = 1; i <= n; i++) {
        cin >> x[i] >> y[i];
        id[i] = i;
        ys[i] = y[i];
    }
    sort(ys + 1, ys + n + 1);
    for (ll i = 1; i <= n; i++) r[i] = lower_bound(ys + 1, ys + n + 1, y[i]) - ys;
    sort(id + 1, id + n + 1, cmp);
    for (ll t = 1; t <= n; t++) {
        ll i = id[t];
        out[i] = (t - 1) - get(r[i] - 1);
        update(r[i], 1);
    }
    for (ll i = 1; i <= n; i++) bit[i] = 0;
    for (ll t = n; t >= 1; t--) {
        ll i = id[t];
        in[i] = get(r[i]);
        update(r[i], 1);
    }
    for (ll i = 1; i <= n; i++) cout << in[i] << ' ';
    cout << '\n';
    for (ll i = 1; i <= n; i++) cout << out[i] << ' ';
    cout << '\n';
}

ChạyInput5
1 10
2 5
3 4
6 9
1 7

Output4 1 0 0 2
0 2 3 1 1

Độ phức tạp: $O(n \log n)$.

Ngưỡng ngoại tuyến

“Đếm phần tử lớn hơn $k$ trên đoạn $[l, r]$” có hai chiều: chỉ số và giá trị. Coi giá trị là trục quét: sắp phần tử và câu hỏi theo giá trị giảm dần; tới câu hỏi ngưỡng $k$ thì mọi phần tử lớn hơn $k$ đã được bật trong Fenwick theo chỉ số, đáp án là tổng đoạn $[l, r]$. Mỗi phần tử bật một lần, tổng $O((n + q) \log n)$. Cùng kỹ thuật cho câu hỏi theo thời điểm, theo trọng số cạnh (thêm cạnh khi ngưỡng tới, như bài 23), theo độ cao.

Ví dụĐếm Phần Tử Vượt Ngưỡng

Đề. Mảng $n \le 3 \cdot 10^4$ số, $q \le 2 \cdot 10^5$ câu hỏi $(l, r, k)$: đếm phần tử lớn hơn $k$ trong $[l, r]$.

Lời giải. Trả lời ngoại tuyến: xếp câu hỏi theo $k$ giảm dần. Với ngưỡng $k$, chỉ các phần tử lớn hơn $k$ được “bật”; ngưỡng giảm dần thì tập phần tử bật chỉ lớn thêm, không bao giờ phải tắt. Đáp án của câu hỏi là số phần tử đã bật trong $[l, r]$, đếm bằng Fenwick theo vị trí.

Bước 1: hai thứ tự. ia là chỉ số phần tử sắp theo giá trị giảm, iq là chỉ số câu hỏi sắp theo $k$ giảm.

sort(ia + 1, ia + n + 1, ca);
sort(iq + 1, iq + q + 1, cq);

Bước 2: con trỏ trên phần tử. Con trỏ j chỉ tiến: trước mỗi câu hỏi, bật mọi phần tử có giá trị lớn hơn $k$ chưa bật. Đáp án ghi theo chỉ số câu hỏi gốc, cuối cùng in lại theo thứ tự đầu vào.

for (ll t = 1, j = 1; t <= q; t++) {
    ll i = iq[t];
    while (j <= n && a[ia[j]] > qk[i]) update(ia[j++]);
    ans[i] = get(qr[i]) - get(ql[i] - 1);
}

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

const ll N = 3e4 + 5, Q = 2e5 + 5;
ll n, q, a[N], ia[N], bit[N], ql[Q], qr[Q], qk[Q], iq[Q], ans[Q];

bool ca(ll x, ll y) {
    return a[x] > a[y];
}

bool cq(ll x, ll y) {
    return qk[x] > qk[y];
}

void update(ll pos) {
    for (; pos <= n; pos += pos & -pos) bit[pos]++;
}

ll get(ll pos) {
    ll res = 0;
    for (; pos > 0; pos -= pos & -pos) res += bit[pos];
    return res;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (ll i = 1; i <= n; i++) {
        cin >> a[i];
        ia[i] = i;
    }
    cin >> q;
    for (ll i = 1; i <= q; i++) {
        cin >> ql[i] >> qr[i] >> qk[i];
        iq[i] = i;
    }
    sort(ia + 1, ia + n + 1, ca);
    sort(iq + 1, iq + q + 1, cq);
    for (ll t = 1, j = 1; t <= q; t++) {
        ll i = iq[t];
        while (j <= n && a[ia[j]] > qk[i]) update(ia[j++]);
        ans[i] = get(qr[i]) - get(ql[i] - 1);
    }
    for (ll i = 1; i <= q; i++) cout << ans[i] << '\n';
}

ChạyInput6
4 1 7 4 9 2
4
1 6 4
2 5 3
3 3 7
4 6 1

Output2
3
0
3

Độ phức tạp: $O((n + q) \log n)$ cộng hai lần sắp.

Diện tích hợp

Quét theo $x$; mỗi hình chữ nhật cho sự kiện $+1$ trên khoảng $[y_1, y_2)$ tại $x_1$ và $-1$ tại $x_2$. Giữa hai sự kiện liên tiếp, diện tích phủ là (tổng độ dài các $y$ đang được phủ ít nhất một lần) nhân (khoảng cách hai sự kiện). Độ dài phủ giữ trong cây phân đoạn trên các khoảng $y$ cơ sở sau khi nén: mỗi nút lưu cnt là số lần nó được phủ trọn và len là độ dài phủ trong đoạn của nó. Nút có cnt > 0 thì phủ trọn, ngược lại len là tổng hai con. Không cần đẩy nhãn xuống, vì mỗi lần trừ luôn khớp với một lần cộng trước đó trên đúng các nút ấy.

Ví dụDiện Tích Hợp Hình Chữ Nhật

Đề. $n \le 10^5$ hình chữ nhật song song trục, tọa độ trong $[-10^6, 10^6]$. Tính diện tích phần được ít nhất một hình phủ.

Lời giải. Quét theo $x$. Giữa hai sự kiện liên tiếp, phần được phủ trên trục $y$ không đổi, nên diện tích của dải đó là độ dài phủ nhân bề rộng dải. Cần một cấu trúc giữ “tổng độ dài các khoảng $y$ đang được ít nhất một hình phủ” khi thêm và bớt khoảng: cây phân đoạn trên các tọa độ $y$ đã nén.

Bước 1: nén $y$. Các $y$ thành dãy ys[1..k]; lá $i$ của cây là khoảng $[ys_i, ys_{i+1})$, nên cây có $k - 1$ lá.

sort(ys + 1, ys + k + 1);
k = unique(ys + 1, ys + k + 1) - ys - 1;

Bước 2: độ dài phủ của một nút. cnt[id] đếm số hình phủ trọn đoạn của nút. Nút có cnt > 0 được phủ trọn, độ dài là cả khoảng của nó; ngược lại là tổng hai con (lá chưa phủ thì 0).

void pull(ll id, ll l, ll r) {
    if (cnt[id]) len[id] = ys[r + 1] - ys[l];
    else if (l == r) len[id] = 0;
    else len[id] = len[id * 2] + len[id * 2 + 1];
}

Bước 3: thêm, bớt một khoảng. Cộng val vào cnt của các nút phủ trọn đoạn lá cần cập nhật, rồi pull ngược lên. Không đẩy nhãn xuống: mỗi lần trừ khớp đúng một lần cộng trước đó trên cùng các nút, nên cnt không bao giờ âm và len[1] luôn đúng.

void update(ll id, ll l, ll r, ll u, ll v, ll val) {
    if (v < l || r < u) return;
    if (u <= l && r <= v) {
        cnt[id] += val;
        pull(id, l, r);
        return;
    }
    ll mid = (l + r) >> 1;
    update(id * 2, l, mid, u, v, val);
    update(id * 2 + 1, mid + 1, r, u, v, val);
    pull(id, l, r);
}

Bước 4: quét sự kiện. Trước khi xử lý sự kiện tại $x$, cộng len[1] nhân khoảng cách từ sự kiện trước. Khoảng $y$ từ $y_1$ tới $y_2$ ứng với các lá từ vị trí của $y_1$ tới ngay trước vị trí của $y_2$.

for (array<ll, 4> e : ev) {
    area += len[1] * (e[0] - px);
    px = e[0];
    ll l = lower_bound(ys + 1, ys + k + 1, e[2]) - ys;
    ll r = lower_bound(ys + 1, ys + k + 1, e[3]) - ys - 1;
    update(1, 1, k - 1, l, r, e[1]);
}

Diện tích tới $4 \cdot 10^{12}$, dùng ll.

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

const ll N = 2e5 + 5;
ll n, k, ys[N], cnt[4 * N], len[4 * N];
vector<array<ll, 4>> ev;

void pull(ll id, ll l, ll r) {
    if (cnt[id]) len[id] = ys[r + 1] - ys[l];
    else if (l == r) len[id] = 0;
    else len[id] = len[id * 2] + len[id * 2 + 1];
}

void update(ll id, ll l, ll r, ll u, ll v, ll val) {
    if (v < l || r < u) return;
    if (u <= l && r <= v) {
        cnt[id] += val;
        pull(id, l, r);
        return;
    }
    ll mid = (l + r) >> 1;
    update(id * 2, l, mid, u, v, val);
    update(id * 2 + 1, mid + 1, r, u, v, val);
    pull(id, l, r);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (ll i = 1; i <= n; i++) {
        ll x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        ev.push_back({x1, 1, y1, y2});
        ev.push_back({x2, -1, y1, y2});
        ys[++k] = y1;
        ys[++k] = y2;
    }
    sort(ys + 1, ys + k + 1);
    k = unique(ys + 1, ys + k + 1) - ys - 1;
    sort(ev.begin(), ev.end());
    ll area = 0, px = ev[0][0];
    for (array<ll, 4> e : ev) {
        area += len[1] * (e[0] - px);
        px = e[0];
        ll l = lower_bound(ys + 1, ys + k + 1, e[2]) - ys;
        ll r = lower_bound(ys + 1, ys + k + 1, e[3]) - ys - 1;
        update(1, 1, k - 1, l, r, e[1]);
    }
    cout << area << '\n';
}

ChạyInput3
0 0 4 2
2 1 5 4
5 0 7 1

Output17

Độ phức tạp: $O(n \log n)$.