Hướng dẫn cho Chọn nhóm

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Tóm tắt đề bài

Cho một hoán vị \(p\) gồm \(n\) số nguyên từ \(1\) đến \(n\). Một cặp \((L, R)\) với \(1 \leq L \leq R \leq n\) được gọi là đẹp nếu tập hợp các giá trị \(\{p_L, p_{L+1}, \dots, p_R\}\) tạo thành một dãy các số nguyên liên tiếp.
Yêu cầu: Đếm số lượng cặp \((L, R)\) đẹp.

Phân tích

Một tập hợp các số \(\{p_L, \dots, p_R\}\) gồm \(R - L + 1\) phần tử là một dãy số nguyên liên tiếp khi và chỉ khi:

\[ \max(p_L, \dots, p_R) - \min(p_L, \dots, p_R) = R - L \]

Biến đổi biểu thức trên, ta có:

\[ \max(p_L, \dots, p_R) - \min(p_L, \dots, p_R) - (R - L) = 0 \]

Với mọi đoạn \([L, R]\), ta luôn có \(\max - \min \geq R - L\). Do đó, giá trị nhỏ nhất của biểu thức \(f(L, R) = \max - \min - R + L\) luôn là \(0\). Bài toán trở thành đếm số cặp \((L, R)\) sao cho \(f(L, R) = 0\).

Ràng buộc

\(n \leq 3 \cdot 10^5\).
Độ phức tạp cần đạt: \(O(n \log n)\) hoặc \(O(n)\).

Hướng giải quyết

Thuật toán: Cây phân đoạn (Segment Tree) kết hợp Stack

Ta sẽ duyệt \(R\) từ \(1\) đến \(n\). Với mỗi \(R\), ta cần đếm số lượng \(L \in [1, R]\) thỏa mãn:

\[ \max(L, R) - \min(L, R) + L = R \]

Tại mỗi bước \(R\), ta duy trì một cây phân đoạn lưu giá trị \(V_L = \max(L, R) - \min(L, R) + L\) cho mọi \(L \leq R\).

Duy trì \(\max\) và \(\min\):
- Sử dụng hai mảng (hoặc stack) đơn điệu để quản lý các vị trí mà tại đó giá trị \(\max\) và \(\min\) của các đoạn kết thúc tại \(R\) thay đổi.
- Khi di chuyển từ \(R-1\) sang \(R\), nếu \(p_R\) lớn hơn các giá trị trước đó trong stack cực đại, ta cập nhật giá trị \(\max\) cho các đoạn tương ứng trên cây phân đoạn.
Cấu trúc cây phân đoạn:
- Mỗi nút trên cây lưu giá trị nhỏ nhất (minVal) của biểu thức \(V_L\) và số lượng vị trí đạt giá trị nhỏ nhất đó (cntMin).
- Khi duyệt đến \(R\), ta cộng thêm \(1\) vào tất cả các \(V_L\) hiện có (vì \(L\) trong công thức tăng lên), hoặc đơn giản hơn là tìm các \(L\) sao cho \(V_L = R\).
- Tuy nhiên, cách tiếp cận phổ biến hơn là lưu \(V_L = \max(L, R) - \min(L, R) - (R - L)\). Khi đó, giá trị nhỏ nhất của \(V_L\) luôn là \(0\). Ta chỉ cần đếm xem trên đoạn \([1, R]\) có bao nhiêu vị trí có giá trị bằng \(0\).
Các bước thực hiện tại mỗi \(R\):
- Giảm toàn bộ giá trị trên cây phân đoạn đi \(1\) (tương ứng với việc \(R\) tăng lên trong phần \(-R\)).
- Cập nhật stack cực đại: Nếu \(p_R\) làm thay đổi \(\max\) của các đoạn \([L, R]\), ta thực hiện rangeAdd phần chênh lệch lên cây phân đoạn.
- Cập nhật stack cực tiểu: Tương tự với \(\min\).
- Truy vấn: Lấy cntMin của đoạn \([1, R]\) nếu minVal == 0.

Độ phức tạp

Thời gian: \(O(n \log n)\) do mỗi phần tử được đẩy vào và lấy ra khỏi stack tối đa một lần, và mỗi lần cập nhật cây phân đoạn mất \(O(\log n)\).
Bộ nhớ: \(O(n)\) để lưu trữ cây phân đoạn và các mảng phụ trợ.

Code tham khảo

C++

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

const int MAXN = 300005;
int p[MAXN];
int minVal[4 * MAXN], cntMin[4 * MAXN], lazy[4 * MAXN];

void build(int node, int l, int r) {
    cntMin[node] = r - l + 1;
    if (l == r) {
        minVal[node] = l;
        return;
    }
    int mid = (l + r) / 2;
    build(2 * node, l, mid);
    build(2 * node + 1, mid + 1, r);
    minVal[node] = min(minVal[2 * node], minVal[2 * node + 1]);
}

void push(int node) {
    if (lazy[node] != 0) {
        minVal[2 * node] += lazy[node];
        lazy[2 * node] += lazy[node];
        minVal[2 * node + 1] += lazy[node];
        lazy[2 * node + 1] += lazy[node];
        lazy[node] = 0;
    }
}

void update(int node, int l, int r, int ql, int qr, int val) {
    if (ql > r || qr < l) return;
    if (ql <= l && r <= qr) {
        minVal[node] += val;
        lazy[node] += val;
        return;
    }
    push(node);
    int mid = (l + r) / 2;
    update(2 * node, l, mid, ql, qr, val);
    update(2 * node + 1, mid + 1, r, ql, qr, val);
    minVal[node] = min(minVal[2 * node], minVal[2 * node + 1]);
    cntMin[node] = 0;
    if (minVal[node] == minVal[2 * node]) cntMin[node] += cntMin[2 * node];
    if (minVal[node] == minVal[2 * node + 1]) cntMin[node] += cntMin[2 * node + 1];
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n; cin >> n;
    for (int i = 1; i <= n; i++) cin >> p[i];

    build(1, 1, n);
    stack<int> sMax, sMin;
    long long ans = 0;

    for (int i = 1; i <= n; i++) {
        // Cập nhật max: max(L, i) - min(L, i) + L = i
        while (!sMax.empty() && p[sMax.top()] < p[i]) {
            int idx = sMax.top(); sMax.pop();
            int prev_idx = sMax.empty() ? 0 : sMax.top();
            update(1, 1, n, prev_idx + 1, idx, p[i] - p[idx]);
        }
        sMax.push(i);

        // Cập nhật min
        while (!sMin.empty() && p[sMin.top()] > p[i]) {
            int idx = sMin.top(); sMin.pop();
            int prev_idx = sMin.empty() ? 0 : sMin.top();
            update(1, 1, n, prev_idx + 1, idx, p[idx] - p[i]);
        }
        sMin.push(i);

        // minVal[1] sẽ luôn là i nếu có cặp thỏa mãn f(L, i) = i
        if (minVal[1] == i) ans += cntMin[1];
    }

    cout << ans << endl;
    return 0;
}

Bình luận

Tải bình luận...

Không có bình luận nào.