Bài tập

Cô giáo trường tiểu học \(X\) đang dạy \(n\) học sinh tập xe đạp, các học sinh được đánh số từ \(1\) tới \(n\), học sinh thứ \(j\) có trọng lượng là \(a_{j}\). Có một xe đạp duy nhất với tải trọng là \(m\), hai học sinh chỉ có thể cùng lên xe nếu tổng trọng lượng của hai học sinh không vượt quá \(m\).

Cô giáo tự hỏi có bao nhiêu cách chọn hai học sinh khác nhau cho cùng lên xe, sau nhiều giờ tính toán không có kết quả, cô quyết định hỏi các chuyên gia lập trình giải bài toán Counting Student Pairs (CSP)

Yêu cầu: Đếm số cặp chỉ số \(i, j\) trong đó \(i < j\) và \(a_i + a_j \leq m\)

Input

• Dòng \(1\) chứa hai số nguyên dương \(n, m\ (m \leq 10^6)\)
• Dòng \(2\) chứa \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\) (\(\forall{i}: a_i \leq 10^6\))

Output

Ghi một số nguyên duy nhất là đáp số

Example

10 18
8 4 14 3 17 9 4 14 8 3

29

Scoring

• Subtask \(1\) (\(60\%\) số điểm): \(n \leq 10^4\).
• Subtask \(2\) (\(20\%\) số điểm): \(n \leq 10^5\).
• Subtask \(3\) (\(20\%\) số điểm): \(n \leq 10^6\).

Tương truyền, San Hà Xã Tắc Đồ là một pháp bảo vô cùng cường đại do Nữ Oa nương nương thời thượng
cổ lưu lại. Uy lực của bức họa này có thể tạo dựng cả một thế giới riêng -- thiên địa sinh thành, nhật nguyệt vận hành, vạn vật hữu linh đều có thể hiện ra trong tranh. Ai nắm giữ được bức họa, chẳng khác nào nắm giữ một cõi thế giới riêng biệt trong lòng bàn tay.

Lâm là một đạo sĩ đã tu luyện đến cảnh giới gần kề thánh nhân, trong một lần cơ duyên gặp gỡ, tìm được một bức họa cổ, tương truyền là bản phác San Hà Xã Tắc Đồ.

Sau nhiều năm tu hành và nghiên ngẫm, ông Lâm quyết định dựng lại bức họa, từng đoạn từng nét. Bức tranh cần được vẽ lên một tấm lụa dài \(n\) thước, chia làm \(n\) đoạn liên tiếp, mỗi đoạn ứng với một phần của thế giới trong tranh. Ông đã xác định được mức màu sắc thích hợp cho từng đoạn, được lưu dưới dạng dãy chuỗi dài \(n\) số, mỗi số cho biết độ sáng, tối tương ứng được sử dụng.

Ban đầu, toàn bộ tấm lụa trắng trơn. Mỗi lần hành pháp (tức là vẽ), ông có thể tô một đoạn liên tiếp trên lụa bằng một màu duy nhất, nhưng ông không được tô màu sáng hơn lên màu tối hơn, vì điều đó sẽ khiến thiên địa trong tranh lộn ngược, âm dương đảo lộn. Chỉ có thể tô màu tối hơn chỗ chưa vẽ, hoặc lên màu sáng hơn.

Tuy nhiên, do thiên mệnh hữu hạn, Lâm không thể hoàn thành toàn bộ bức họa trong một lần. Vì thế, ông đang cân nhắc bỏ trống một số đoạn nhất định, không vẽ vào đó nữa -- để sau này hậu nhân hoàn thiện. Hiện tại có \(q\) kịch bản khác nhau, mỗi kịch bản cho biết một đoạn liên tiếp từ \(l\) đến \(r\) trên tấm lụa sẽ được vẽ.

Yêu cầu: Với mỗi kịch bản như vậy, hãy giúp ông Lâm tính xem: số lần hành pháp (vẽ) ít nhất cần thiết để hoàn thành bức họa, đúng theo màu sắc đã định, và không vi phạm quy tắc sáng tối.

Input

• Dòng đầu tiên gồm hai số nguyên \(n, q\) (\(n, q \leq 10^5\)) là số đoạn của tấm lụa và số kịch bản.
• Dòng thứ hai là \(n\) số \(a_1, a_2, \dots, a_n\) (\(0 \leq a_i \leq 10^9\)) biểu thị độ sáng tối của từng đoạn.
• \(q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(l\) và \(r\) (\(1 \leq l \leq r \leq n\)) cho biết đoạn sẽ vẽ.

Output

• Với mỗi kịch bản, in ra một dòng chứa số nguyên là số lần vẽ tối thiểu cần thiết để hoàn thành bức họa.

Example

8 5
1 4 1 2 4 2 3 2
3 4
1 5
2 6
4 7
1 8

2
4
4
3
5

Scoring

• \(30\%\) số điểm thỏa mãn \(n, q \leq 100\)
• \(20\%\) số điểm khác với \(n, q \leq 1000\)
• Còn lại không có điều kiện gì thêm

Trường Đại học Công nghệ Tương lai vừa cho ra mắt một hệ thống AI đặc biệt mang tên "Mai Mối Chuẩn Gen", với nhiệm vụ giúp sinh viên cô đơn tìm được nửa kia phù hợp nhất dựa trên chỉ số "tương thích cảm xúc".

Có \(n\) sinh viên tham gia hệ thống, mỗi người được hệ thống đánh giá bằng một chỉ số \(a_1, a_2, ..., a_n\) thể hiện mức độ đồng điệu về cảm xúc.

Hệ thống hoạt động bằng cách chia dãy chỉ số cảm xúc thành các đoạn con liên tiếp, không giao nhau. Một đoạn được xem là tối ưu nếu trung bình cộng của các chỉ số trong đoạn đúng bằng một giá trị lý tưởng \(x\) mà hệ thống đưa ra.

Mỗi khi có sinh viên đăng ký tham gia, hệ thống sẽ yêu cầu trả lời một truy vấn dạng:

Trong khoảng từ người thứ \(l\) đến người thứ \(r\), có thể chia được tối đa bao nhiêu đoạn con liên tiếp, không giao nhau sao cho trung bình cộng của mỗi đoạn đúng bằng \(x\)?

Bạn được giao nhiệm vụ xử lý \(q\) truy vấn như vậy, để giúp hệ thống hoạt động hiệu quả hơn!

Input

• Dòng đầu tiên chứa ba số nguyên \(n\), \(q\), \(x\) \((1 \le n, q \le 2 \cdot 10^5, 1 \le x \le 10^6)\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, ..., a_n\) là chỉ số cảm xúc của từng sinh viên \((1 \le a_i \le 10^6)\).
• \(q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(l_i\), \(r_i\) \((1 \le l_i \le r_i \le n)\).

Output

• Gồm \(q\) dòng, dòng thứ \(i\) là đáp án cho truy vấn thứ \(i\) --- số đoạn con liên tiếp, không giao nhau trong đoạn \([l_i, r_i]\) sao cho trung bình cộng đúng bằng \(x\).

Example

10 1 5
6 7 2 5 6 1 8 7 4 6
1 10

4

Scoring

• Có \(30\%\) số test tương ứng với \(30\%\) số điểm có \(n, q \leq 200\).
• Có \(30\%\) số test tương ứng với \(30\%\) số điểm có \(n, q \leq 2000\).
• Có \(40\%\) số test tương ứng với \(40\%\) số điểm không có ràng buộc gì thêm.

Trong quá trình huấn luyện để chuẩn bị cho đấu trường ICPC, các bạn trại sinh sẽ được thử sức với nhiều dạng bài tập khác nhau. Một trong những bài toán đầu tiên được đưa ra nhằm kiểm tra tư duy chiến lược và khả năng xử lý xâu của các bạn.

Ban tổ chức Bootcamp cần đặt một cái tên đặc biệt cho phần thưởng dành cho những học viên xuất sắc nhất. Tên này phải được lấy từ một xâu chủ đề cho trước, đó là một chuỗi các ký tự tiếng Anh viết thường. Cụ thể, tên của phần thưởng phải là một xâu con (một dãy các ký tự liên tiếp) của xâu chủ đề.

Để thể hiện sự đa dạng trong kỹ năng của các học viên, tên của phần thưởng còn phải có ít nhất \(k\) ký tự phân biệt.

Yêu cầu: Hãy giúp ban tổ chức đếm số cách chọn một xâu con từ xâu chủ đề thỏa mãn điều kiện trên. Hai cách chọn được coi là khác nhau nếu vị trí bắt đầu hoặc vị trí kết thúc của xâu con khác nhau.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n\) và \(k\) (\(1 \le n \le 10^6, 1 \le k \le 26\)), lần lượt là độ dài của xâu chủ đề và số lượng ký tự phân biệt tối thiểu yêu cầu.
• Dòng thứ hai chứa xâu chủ đề gồm \(n\) ký tự trong bảng chữ cái tiếng Anh viết thường.

Output

• In ra một số nguyên không âm duy nhất là tổng số xâu con thỏa mãn.

Example

5 3
abacd

5

Scoring

• \(20\%\) số test có \(k=1\).
• \(20\%\) số test có \(k=2\).
• \(20\%\) số test có \(n \le 10^2\).
• \(20\%\) số test có \(n \le 10^4\).
• \(20\%\) số test không có ràng buộc gì thêm.