NOI Singapore 2026 - Gemstones - LQDOJ: Le Quy Don Online Judge

NOI Singapore 2026 - Gemstones

Dạng bài

Ngôn ngữ cho phép

Assembly, Awk, C, C#, C++, Clang, Cobol, D, Haskell, JS, Java, Kotlin, Lua, Node JS, OCaml, ObjectiveC, Output, PHP, Pascal, Perl, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Scratch

Điểm: 2400 (p) Thời gian: 2.5s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Có \(n\) viên đá quý xếp thành một hàng, đánh số từ \(1\) đến \(n\). Viên thứ \(i\) có màu \(c_i\).

Trong một thao tác, bạn chọn hai viên kề nhau và cùng màu rồi xóa cả hai. Các viên ở hai phía trượt lại để lấp khoảng trống, có thể tạo ra những cặp kề nhau mới.

Có \(q\) kịch bản độc lập. Trong kịch bản thứ \(j\), chỉ xét đoạn đá từ \(l_j\) đến \(r_j\). Nếu thực hiện tối ưu các thao tác, hãy tìm số viên nhỏ nhất còn lại.

Dữ liệu vào

Dòng đầu chứa \(n,q\).
Dòng thứ hai chứa \(c_1,c_2,\ldots,c_n\).
\(q\) dòng tiếp theo, dòng thứ \(j\) chứa \(l_j,r_j\).

Dữ liệu ra

In \(q\) dòng; dòng thứ \(j\) là đáp án của kịch bản thứ \(j\).

Giới hạn

\[ 1\le n\le10^6,\quad 1\le q\le500\,000,\quad 1\le c_i\le10^9 \]

\[ 1\le l_j\le r_j\le n \]

Chấm điểm

Phần	Điểm	Giới hạn thêm
1	2	\(c_1=c_2=\cdots=c_n\)
2	5	Các viên cùng màu tạo thành một đoạn liên tiếp
3	9	\(n,q\le2000\)
4	4	\(l_j=1\) với mọi truy vấn
5	8	Mỗi màu xuất hiện đúng hai lần
6	16	\(c_i\le2\)
7	18	\(n,q\le100\,000\)
8	15	\(n,q\le300\,000\)
9	23	Không có giới hạn thêm

Ví dụ

Ví dụ 1

Input

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

Output

Note

Trong truy vấn đầu, xóa hai trong ba viên màu \(3\) và còn lại một viên. Truy vấn thứ hai có thể xóa hết. Truy vấn thứ ba còn tối thiểu một viên. Trong truy vấn cuối không thể thực hiện thao tác nào.