DQUERY - D-query


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 


hide comments
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.

cjn2007: 2021-11-02 08:25:51

Binary Indexed Tree with off line algorithms.
AC in one go :)

darksun: 2021-11-01 10:33:18

Can anyone tell me the solution using Binary indexed trees ?


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