Tóm tắt đề bài

Cho dãy \(n\) số nguyên \(a_1, a_2, \dots, a_n\) và một số nguyên \(d\). Mỗi số \(a_i\) đại diện cho số lượng vũ trụ \(j < i\) mà vũ trụ \(i\) kết nối tới. Một đoạn con liên tiếp từ chỉ số \(L\) đến \(R\) (độ dài \(k = R - L + 1\)) được coi là thỏa mãn nếu tồn tại một cách thiết lập các kết nối giữa các vũ trụ trong đoạn sao cho:

1. Dãy đặc trưng mới của đoạn này, gọi là \(f_1, f_2, \dots, f_k\), phải khớp với \(a_L, a_{L+1}, \dots, a_R\). Lưu ý rằng khi xét đoạn \([L, R]\), chỉ số của các vũ trụ được tính lại từ \(1\) đến \(k\), do đó \(f_i\) là số lượng vũ trụ \(j < i\) trong đoạn mà vũ trụ \(i\) kết nối tới.
2. Trong tất cả các cách kết nối thỏa mãn dãy đặc trưng, bậc của mọi đỉnh (số kết nối của mỗi vũ trụ) không được vượt quá \(d\).

Yêu cầu: Đếm số cặp \((L, R)\) thỏa mãn các điều kiện trên.

Phân tích

1. Điều kiện để tồn tại dãy đặc trưng

Khi xét đoạn \([L, R]\), phần tử thứ \(i\) trong đoạn (tương ứng với \(a_{L+i-1}\) trong dãy gốc) cho biết nó kết nối với \(a_{L+i-1}\) vũ trụ đứng trước nó trong đoạn.

• Để điều này khả thi, số lượng vũ trụ đứng trước nó trong đoạn phải lớn hơn hoặc bằng \(a_{L+i-1}\).
• Vị trí hiện tại trong đoạn là \(i' = i - L + 1\). Số lượng phần tử đứng trước nó là \(i' - 1\).
• Điều kiện: \(a_i \le i - L\) với mọi \(i \in [L, R]\).
• Viết lại: \(L \le i - a_i\) với mọi \(i \in [L, R] \iff L \le \min_{i=L}^R (i - a_i)\).

2. Điều kiện về bậc tối đa \(d\)

Bậc của vũ trụ \(i\) trong đoạn \([L, R]\) được tính bằng:

• Số lượng vũ trụ \(j < i\) mà \(i\) kết nối tới (cố định là \(a_i\)).
• Số lượng vũ trụ \(k > i\) mà \(k\) kết nối tới \(i\).

Để bậc của \(i\) không vượt quá \(d\) trong mọi khả năng, ta xét trường hợp xấu nhất. Trong trường hợp xấu nhất, các vũ trụ \(k > i\) có \(a_k > 0\) sẽ ưu tiên kết nối với vũ trụ \(i\).

• Nếu \(a_k > 0\), vũ trụ \(k\) có thể kết nối với vũ trụ \(i\). Để đảm bảo bậc của \(i\) luôn \(\le d\), ta giả định tất cả các vũ trụ \(k \in (i, R]\) có \(a_k > 0\) đều "có khả năng" kết nối với \(i\).
• Tuy nhiên, đề bài nói "Trong tất cả các khả năng... mỗi vũ trụ kết nối không quá \(d\)". Điều này có nghĩa là ngay cả khi ta cố tình chọn các kết nối sao cho bậc của \(i\) lớn nhất, nó vẫn phải \(\le d\).
• Thực tế, với một dãy \(a_L, \dots, a_R\), bậc lớn nhất có thể của vũ trụ \(i\) là \(a_i + (\text{số lượng } k \in [i+1, R] \text{ sao cho } a_k > 0)\).
• Điều kiện: \(a_i + \sum_{k=i+1}^R [a_k > 0] \le d\) với mọi \(i \in [L, R]\).

3. Tổng hợp điều kiện

Đoạn \([L, R]\) thỏa mãn khi và chỉ khi với mọi \(i \in [L, R]\):

1. \(L \le i - a_i\)
2. \(a_i + (cnt_R - cnt_i) \le d\), trong đó \(cnt_x\) là số lượng các chỉ số \(j \le x\) mà \(a_j > 0\).

Hướng giải quyết

Ta có thể sử dụng phương pháp Chia để trị (Divide and Conquer) để đếm số cặp \((L, R)\).

Thuật toán Chia để trị

Hàm DAC(left, right) tính số cặp \((L, R)\) nằm trong đoạn \([left, right]\) và đi qua trung điểm \(mid = (left + right) / 2\).

1. Đệ quy DAC(left, mid) và DAC(mid + 1, right).
2. Đếm số cặp \((L, R)\) thỏa mãn \(left \le L \le mid < R \le right\).
3. Để kiểm tra nhanh điều kiện cho đoạn \([L, R]\), ta tiền xử lý các giá trị cực trị từ \(mid\) về hai phía.

Với một cặp \((L, R)\) cố định đi qua \(mid\):

• Điều kiện 1 trở thành: \(L \le \min(\min_{i=L}^{mid} (i - a_i), \min_{i=mid+1}^{R} (i - a_i))\).
• Điều kiện 2 trở thành: \(\forall i \in [L, R], a_i - cnt_i \le d - cnt_R\).

Để tối ưu, ta có thể sử dụng kỹ thuật hai con trỏ hoặc tìm kiếm nhị phân kết hợp với các mảng tiền xử lý (min, max) khi cố định một đầu (ví dụ cố định \(L\) và tìm các \(R\) hợp lệ).

Các bước chi tiết trong DAC:

• Xây dựng mảng các giá trị thỏa mãn từ \(mid+1\) đến \(right\):
  • Duy trì \(min\_id[R] = \min_{k=mid+1}^R (k - a_k)\).
  • Duy trì \(max\_val[R] = \max_{k=mid+1}^R (a_k - cnt_k)\).
  • Một giá trị \(R\) chỉ có thể hợp lệ nếu \(min\_id[R] \ge L\) và các điều kiện nội bộ phía bên phải \(mid\) được thỏa mãn.
• Với mỗi \(L\) từ \(mid\) xuống \(left\):
  • Kiểm tra điều kiện nội bộ phía bên trái \(mid\).
  • Tìm phạm vi \(R \in [mid+1, right]\) sao cho cả hai phía khớp nhau.
  • Điều kiện \(a_i + cnt_R - cnt_i \le d\) có thể viết lại thành \(cnt_R \le d - (a_i - cnt_i)\). Ta cần \(cnt_R \le \min_{i=L}^R (d - a_i + cnt_i)\).

Độ phức tạp

• Thời gian: \(O(n \log n)\) hoặc \(O(n \log^2 n)\) tùy vào cách cài đặt (hai con trỏ hoặc tìm kiếm nhị phân trong DAC).
• Bộ nhớ: \(O(n)\) để lưu trữ mảng và các cấu trúc phụ trợ.

Code tham khảo

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;
const int N = 1e5 + 5;
const int INF = 1e9 + 7;

int n, d;
int a[N], cnt[N];

// Kiểm tra điều kiện 2 cho một đoạn [L, R]
bool check_d(int L, int R) {
    for (int i = L; i <= R; ++i) {
        if (a[i] + (cnt[R] - cnt[i]) > d) return false;
    }
    return true;
}

// Chia để trị để đếm số cặp (L, R)
ll solve(int left, int right) {
    if (left > right) return 0;
    if (left == right) {
        return (a[left] <= 0 && 0 <= d); // a[i] <= i-L => a[L] <= 0
    }

    int mid = (left + right) / 2;
    ll ans = solve(left, mid) + solve(mid + 1, right);

    // Đếm các cặp L <= mid < R
    vector<pair<int, int>> right_parts;
    int cur_min_id = INF;
    int cur_max_cnt_diff = -INF;

    // Tiền xử lý phía bên phải mid
    for (int R = mid + 1; R <= right; ++R) {
        cur_min_id = min(cur_min_id, R - a[R]);
        // Điều kiện nội bộ phía phải: a[k] + cnt[R] - cnt[k] <= d
        // <=> a[k] - cnt[k] <= d - cnt[R]
        cur_max_cnt_diff = max(cur_max_cnt_diff, a[R] - cnt[R]);

        // Kiểm tra xem đoạn [mid+1, R] có tự thỏa mãn điều kiện 2 không
        bool ok = true;
        if (cur_max_cnt_diff > d - cnt[R]) ok = false;

        if (ok) right_parts.push_back({cur_min_id, cnt[R]});
        else break; // Nếu R không thỏa thì R+1 cũng không thỏa do cnt[R] tăng
    }

    int L_min_id = INF;
    int L_max_val = -INF;
    int j = 0;

    // Duyệt L từ mid về left
    for (int L = mid; L >= left; --L) {
        L_min_id = min(L_min_id, L - a[L]);
        L_max_val = max(L_max_val, a[L] - cnt[L]);

        // Điều kiện nội bộ phía trái: L_min_id >= L và L_max_val <= d - cnt[R]
        if (L_min_id < L) break;

        // Với L cố định, tìm R sao cho:
        // 1. R_min_id >= L
        // 2. cnt[R] <= d - L_max_val
        // 3. R nằm trong right_parts (đã thỏa mãn điều kiện nội bộ phía phải)

        while (j < right_parts.size() && right_parts[j].first >= L) {
            j++;
        }

        // Tìm kiếm nhị phân trong right_parts[0...j-1] để đếm cnt[R] <= d - L_max_val
        int target = d - L_max_val;
        int low = 0, high = j - 1, res = -1;
        while (low <= high) {
            int m = (low + high) / 2;
            if (right_parts[m].second <= target) {
                res = m;
                low = m + 1;
            } else {
                high = m - 1;
            }
        }
        ans += (res + 1);
    }

    return ans;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    if (!(cin >> n >> d)) return 0;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        cnt[i] = cnt[i - 1] + (a[i] > 0);
    }

    cout << solve(1, n) << endl;
    return 0;
}