Bài này đọc qua thì có vẻ rất liên quan nhưng thực sự là nó có liên quan đến bài 2 VOI 2021 vừa qua của Bộ Giáo Dục và Đào Tạo: https://oj.vnoi.info/problem/voi22_graph

Gọt \(cnt[x]\) = số lượng chỉ số \(i\) có \(a[i]>0\) và \(i>=x\)

Lúc đó đoạn \([L, R]\) gọi là thỏa mãn nếu và chỉ nếu:

• \(a[i] <= (i-L)\), đây là điều kiện để tồn tại ít nhất một khả năng các vũ trụ liên kết với nhau
• \(cnt[i + 1] - cnt[R + 1] + a[i] <= d\), đảm bảo mọi vũ trụ đều kết nối đến không quá \(d\) vũ trụ khác

với mọi i nằm trong đoạn [L, R]

Hai điều kiện trên có thể viết lại thành:

• \(i-a[i] >=L\)
• \(a[i] + cnt[i + 1] <= d - cnt[R+1]\)

Từ đây ta có ý tưởng đếm số dãy sử dụng chia để trị như sau:

  DAC(left, right):
      mid = (left + right) / 2;
      ans += #(số dãy [L, R] thỏa mãn có L <= mid <= R)
      DAC(left, mid - 1)
      DAC(mid + 1, r)

Để đếm #(số dãy \([L, R]\) thỏa mãn có \(L <= mid <= R\)), ta sẽ sử dụng kĩ thuật hai con trỏ như trong code dưới

Code mẫu: https://pastebin.com/PD3Z3YJg