Dãy cảm biến liên thông
Đề bài
Mô tả
Một lưới phòng thủ quan trọng ở Khu vực 2026 dựa vào một dãy cảm biến tuyến tính gồm nút giám sát, được đặt lần lượt từ đến . Mức hiệu chuẩn của các nút tạo thành một hoán vị của các số nguyên từ đến .
Để phân tích độ ổn định tín hiệu cục bộ, trung tâm điều khiển xem xét mọi đoạn con liên tiếp khác rỗng (với ). Với mỗi đoạn con như vậy, một đồ thị liên lạc vô hướng được xây dựng như sau:
- Các đỉnh của đồ thị là các chỉ số .
- Với hai chỉ số và bất kỳ trong cửa sổ, , có một cạnh vô hướng khi và chỉ khi .
Nói cách khác, hai nút cảm biến được nối trực tiếp khi và chỉ khi mức hiệu chuẩn của chúng tạo thành một nghịch thế. Một đoạn con được gọi là nhất quán khi và chỉ khi đồ thị cảm sinh của nó liên thông. Lưu ý rằng cửa sổ chỉ gồm đúng một đỉnh luôn được coi là liên thông.
Hãy xác định tổng số đoạn con liên tiếp khác rỗng có đồ thị nghịch thế cảm sinh liên thông.
Dữ liệu vào
- Dòng đầu tiên chứa một số nguyên ().
- Dòng thứ hai chứa số nguyên cách nhau bởi dấu cách, tạo thành một hoán vị của .
Dữ liệu ra
In ra một số nguyên duy nhất: số đoạn con liên tiếp tạo thành đồ thị liên thông.
Ràng buộc
- .
- là một hoán vị của các số nguyên từ đến .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 3 1 2 |
5 | Đoạn liên thông vì tạo thành một cạnh. Đoạn không có nghịch thế nên không liên thông. Ba đoạn một phần tử , , hiển nhiên liên thông, và cả dãy liên thông (cạnh và ), tổng cộng đoạn liên thông. |
| 4 1 2 3 4 |
4 | Hoán vị không có nghịch thế nào. Do đó mọi đoạn có độ dài đều không có cạnh và không liên thông. Chỉ có đoạn một phần tử là liên thông. |
| 4 4 3 2 1 |
10 | Mọi cặp phần tử đều tạo thành nghịch thế, nên đồ thị của mọi đoạn con là một đồ thị đầy đủ. Vậy cả đoạn con liên tiếp khác rỗng đều liên thông. |
Bình luận