Submit | All submissions | Best solutions | Back to list |
DQUERY - D-query |
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ử a1, a2, ..., an 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 ai, ai+1, ..., aj.
Dữ liệu
- Dòng 1: n (1 ≤ n ≤ 30000).
- Dòng 2: n số a1, a2, ..., an (1 ≤ ai ≤ 106).
- 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 ai, ai+1, ..., aj 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
Added by: | Jimmy |
Date: | 2008-10-26 |
Time limit: | 1s-1.5s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |
Resource: | Minesweeper |
hide comments
|
|||||
2024-03-08 23:14:32
AC IN 1E9+7 LET'S GOOOOOOOOOOOOOOOO! |
|||||
2023-07-27 12:41:32
莫队和树没有关系吧(雾 |
|||||
2023-03-15 06:07:16
just use president Tree to solve this |
|||||
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 |
|||||
2022-12-03 21:27:43
Solved in one go using your mom |
|||||
2022-07-25 17:36:04
AC in one go with sorting + range sum |
|||||
2022-07-25 12:14:01
Solved using MO's in one go |
|||||
2022-06-29 09:08:44
If you want to solve using segment tree (online) then lookup merge sort tree first. |
|||||
2021-11-02 08:25:51
Binary Indexed Tree with off line algorithms. AC in one go :) |
|||||
2021-11-01 10:33:18
Can anyone tell me the solution using Binary indexed trees ? |