Bài 4: Phần tử nhìn thấy (TS10 Vĩnh Phúc thi thử - 2026)
Xem PDF
Điểm:
1900 (p)
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Cho dãy số nguyên dương \(a_1, a_2, \dots, a_N\).
Với mỗi đoạn con \([l, r]\) (\(1 \le l \le r \le N\)):
- Một phần tử \(a_i\) (\(l \le i \le r\)) được gọi là nhìn thấy từ bên trái, nếu không tồn tại phần tử \(a_j\) (\(l \le j < i\)) sao cho \(a_j \ge a_i\).
- Một phần tử \(a_i\) (\(l \le i \le r\)) được gọi là nhìn thấy từ bên phải, nếu không tồn tại phần tử \(a_j\) (\(i < j \le r\)) sao cho \(a_j \ge a_i\).
Giá trị của đoạn \([l, r]\), ký hiệu \(f(l, r)\), là số lượng chỉ số \(i\) (\(l \le i \le r\)) khác nhau được nhìn thấy từ ít nhất một trong hai phía.
Yêu cầu: Tính tổng giá trị của tất cả các đoạn con \([l, r]\), nghĩa là tính tổng:
\[\sum_{l=1}^{n} \left( \sum_{r=l}^{n} f(l, r) \right)\]
Input
- Dòng 1: số nguyên \(N\) (\(1 \le N \le 10^5\)).
- Dòng 2: \(N\) số nguyên \(a_1, a_2, \dots, a_N\) (\(1 \le a_i \le 10^9\)).
Output
- In ra một số nguyên — tổng giá trị của tất cả các đoạn con.
Example
Test 1
Input
4
4 2 3 2Output
18Note
- \(f(1,1) = 1\), các đoạn độ dài 1 đều có giá trị bằng 1.
- \(f(2,2) = 1\).
- \(f(3,3) = 1\).
- \(f(4,4) = 1\).
- \(f(1,2) = 2\), các đoạn độ dài 2 đều có giá trị bằng 2.
- \(f(2,3) = 2\).
- \(f(3,4) = 2\).
- \(f(1,3) = 2\), đoạn \([4, 2, 3]\): chỉ có hai phần tử đầu mỗi phía là nhìn thấy.
- \(f(2,4) = 3\), đoạn \([2, 3, 2]\): cả 3 phần tử đều nhìn thấy.
- \(f(1,4) = 3\), đoạn \([4, 2, 3, 2]\): phần tử thứ hai không nhìn thấy được từ cả hai phía.
Test 2
Input
8
7 2 3 2 4 3 3 7Output
81Note
Trong số 36 đoạn con của dãy, có:
- 8 đoạn giá trị bằng 1.
- 14 đoạn giá trị bằng 2.
- 11 đoạn giá trị bằng 3.
- 3 đoạn giá trị bằng 4.
Scoring
- Subtask \(1\) (\(20\%\) số điểm): \(N \le 50\).
- Subtask \(2\) (\(20\%\) số điểm): \(N \le 300\).
- Subtask \(3\) (\(25\%\) số điểm): \(N \le 5000\).
- Subtask \(4\) (\(35\%\) số điểm): Không có ràng buộc bổ sung.
Kỳ thi:
- Thi thử tuyển sinh lớp 10 Chuyên Vĩnh Phúc 2026 (7 Tháng năm, 2026)
Bình luận (1)