Elearning CodePath – CTP Online Judge

NEXUS

🟢 Easy

Loki hay Thần lừa lọc là em trai khác cha khác mẹ của Thor, là một trong những vị thần ngoại tộc của xứ Asgard. Hiện nay hắn đang làm quản lí tại Cơ quan Quản lý Phương sai Thời gian (TVA), thế chỗ cho He who remains. Sau khi He who remains cưỡi hạc qui tiên, các sự kiện nexus xảy ra không thể kiểm soát; dẫn đến trong Đa vũ trụ xuất hiện $n$ vũ trụ mới, Loki đánh số các vũ trụ này từ $1$ đến $n$ theo vị trí xuất hiện mà hắn nhìn thấy.

Công nghệ của các vũ trụ này cực kì phát triển, tới nỗi có một số cặp vũ trụ có thể liên hệ với nhau; mối liên hệ giữa hai vũ trụ là hai chiều, có nghĩa là nếu vũ trụ $i$ có thể kết nối tới vũ trụ $j$ thì người ở vũ trụ $j$ cũng có thể gửi lời hồi âm tới vũ trụ $i$.

Mỗi vũ trụ có một chỉ số đặc trưng $a_i$ được tính bằng số vũ trụ $j$ ($j<i$) sao cho hai vũ trụ $i$ và $j$ có thể liên hệ với nhau. Dễ nhận thấy mỗi khả năng các vũ trụ liên kết với nhau sẽ chỉ cho ra duy nhất một dãy đặc trưng, song có thể có nhiều trường hợp các vũ trụ liên kết khác nhau có cùng dãy đặc trưng.

Lo sợ liên minh các vũ trụ quá hùng mạnh, và cũng để giữ sự bình ổn của Đa vũ trụ; Loki muốn xóa đi một số vũ trụ và giữ lại một số liên tiếp nhau các vũ trụ có dãy đặc trưng là $f$ thỏa mãn:

Tồn tại ít nhất một khả năng các vũ trụ liên kết nhau có dãy đặc trưng là $f$

Trong tất cả các khả năng các vũ trụ liên kết với nhau nhận $f$ làm dãy đặc trưng, mỗi vũ trụ có thể kết nối với không quá $d$ vũ trụ khác

Yêu cầu: Cho số nguyên $d$ và dãy đặc trưng $a$ của $n$ vũ trụ mới tạo ra; bạn hãy đếm số cách chọn các vũ trụ liên tiếp nhau có dãy đặc trưng thỏa mãn điều kiện trên, hay nói cách khác bạn hãy đếm số cặp ${L,R}$ $(1 \le L \le R \le n)$ thỏa mãn $a[L \dots R]$ lập thành một dãy đặc trưng thỏa mãn. Hai cặp số gọi là khác nhau nếu có ít nhất một trong hai số tương ứng khác nhau.

**Dữ liệu**

Vào từ file văn bản NEXUS.INP:

Dòng đầu tiên chứa hai số nguyên dương $n, d$ $(0 \le d \le n \le 10^5)$

Dòng thứ hai chứa $n$ số nguyên, số thứ $i$ có giá trị $a_i$ $(1 \le i \le n,; 0 \le a_i \le i-1)$

**Kết quả**

Ghi ra file văn bản NEXUS.OUT một số nguyên duy nhất là số cặp số ${L,R}$ thỏa mãn.

**Ràng buộc**

Có $25%$ số test ứng với $25%$ số điểm của bài toán có $n \le 200$

Có $25%$ số test ứng với $25%$ số điểm của bài toán có $n \le 2000$

Có $25%$ số test ứng với $25%$ số điểm của bài toán có $n \le 10^5$ và $a_i \ge i - 10,\ \forall i: 1 \le i \le n$

Có $25%$ số test ứng với $25%$ số điểm của bài toán có $n \le 10^5$

Ví dụ
Input
4 1
0 1 2 0

Output
3

Giải thích

Có $3$ cặp số thỏa mãn là ${1,1}$, ${4,4}$ và ${1,2}$.

✅ Đã AC: 0 / 0 submissions