English

Vietnamese

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/dquery

Truy vấn-d

Cho một dãy số n phần tử a₁, a₂, ..., a_n và một số các truy vấn-d. Một truy vấn-d là một cặp (i, j) (1 ≤ i ≤ j ≤ n). Với mỗi truy vấn-d (i, j), bạn cần trả về số phần tử phân biệt nằm trong dãy con a_i, a_i+1, ..., a_j.

Dữ liệu

• Dòng 1: n (1 ≤ n ≤ 30000).
• Dòng 2: n số a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁶).
• Dòng 3: q (1 ≤ q ≤ 200000), số lượng truy vấn- d.
• Trong q dòng sau, mỗi dòng chứa 2 số i, j biểu thị một truy vấn-d (1 ≤ i ≤ j ≤ n).

Kết quả

• Với mỗi truy vấn-d (i, j), in ra số phần tử phân biệt thuộc dãy con a_i, a_i+1, ..., a_j trên một dòng.

   

Ví dụ

Dữ liệu
5
1 1 2 1 3
3
1 5
2 4
3 5

Kết quả
3
2
3 

---

hide comments

< Previous 1 2 Next >
	rising_stark: 2024-09-27 12:50:19 One of the worst problems I faced. After repeated submissions, I was facing TLE. Was optimising the code for no reason, when ultimately it turned out to be an issue of cin vs scanf. Really strict time limit for no reason at all.
	amira3: 2024-08-10 11:56:28 simple MO algorithm
	ismaelkno: 2024-03-08 23:14:32 AC IN 1E9+7 LET'S GOOOOOOOOOOOOOOOO!
	zhouyexuan: 2023-07-27 12:41:32 莫队和树没有关系吧（雾
	tiachi: 2023-03-15 06:07:16 just use president Tree to solve this
	ultimate_von: 2023-03-14 15:47:38 Me too! AC with MO algorithm Tree Is also ok!! They both are tarjin algorihtm Last edit: 2023-03-14 15:48:01
	masterbaiter: 2022-12-03 21:27:43 Solved in one go using your mom
	sebastiamestre: 2022-07-25 17:36:04 AC in one go with sorting + range sum
	iskhakkutbilim: 2022-07-25 12:14:01 Solved using MO's in one go
	goku20001: 2022-06-29 09:08:44 If you want to solve using segment tree (online) then lookup merge sort tree first.