CSES - Subarray Distinct Values | Giá trị phân biệt trong đoạn con
Xem PDF
Điểm:
1500 (p)
Thời gian:
1.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Với một mảng gồm \(n\) số nguyên, nhiệm vụ của bạn là tính toán số lượng đoạn con có nhiều nhất \(k\) giá trị phân biệt.
Input
- Dòng đầu vào đầu tiên có hai số nguyên \(n\) và \(k\): kích thước của mảng và số lượng giả trị phân biệt tối đa.
- Dòng tiếp theo có \(n\) số nguyên \(x_1,x_2,\ldots,x_n\): nội dung của mảng.
Output
- In một số nguyên: số lượng đoạn con.
Constraints
- \(1 \le k \le n \le 2 \cdot 10^5\)
- \(1 \le x_i \le 10^9\)
Example
Sample input
5 2
1 2 3 1 1
Sample output
10
Bình luận
có ai cho mình hint với ...........
^-^
-
0
Haidepzai
10:05 p.m. 31 Tháng 7, 2024
-
0
votrongkhoinguyen
10:35 a.m. 18 Tháng 2, 2024
3 bình luận nữabạn tạo 1 map để lưu tần suất các phần tử xuất hiện trong 1 đoạn con, rồi tạo 2 biến left right để duyệt qua toàn mảng. cho right chạy qua các phần tử đồng thời cập nhật vào map, khi nào thấy số phần tử right đi qua nhiều hơn k thì rút map lại rồi tăng left lên.......