DQUERY - D-query


{assign var="code" value="DQUERY"} {if $par==""} {assign var=par value=$locale} {/if}

{if $par=="vn"} {literal}

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 

{/literal}{elseif ($par=="en" || $par=="")}{literal}

Given a sequence of n numbers a1, a2, ..., an and a number of d-queries. A d-query is a pair (i, j) (1 ≤ i ≤ j ≤ n). For each d-query (i, j), you have to return the number of distinct elements in the subsequence ai, ai+1, ..., aj.

Input

  • Line 1: n (1 ≤ n ≤ 30000).
  • Line 2: n numbers a1, a2, ..., an (1 ≤ ai ≤ 106).
  • Line 3: q (1 ≤ q ≤ 200000), the number of d-queries.
  • In the next q lines, each line contains 2 numbers i, j representing a d-query (1 ≤ i ≤ j ≤ n).

Output

  • For each d-query (i, j), print the number of distinct elements in the subsequence ai, ai+1, ..., aj in a single line.

     

Example

Input
5
1 1 2 1 3
3
1 5
2 4
3 5

Output
3
2
3 

{/literal} {/if}


hide comments
chandan kumar: 2017-12-15 08:59:47

Offline BIT with fast I/O - 0.10s

Last edit: 2017-12-15 09:03:36
pratham_1: 2017-12-15 08:28:34

BIT - 0.17s , MO-0.30s , AC ;)

chandan kumar: 2017-12-15 06:25:15

offline fenwick tree/segment tree

suraj_: 2017-12-13 07:18:28

thanks!! @tanavya
MO jai ho

Last edit: 2017-12-13 10:47:23
chachaji_harsh: 2017-12-09 12:53:56

can somebody pls tell why my code is printing unexpectedly wrong output (only sometimes)while my mo's implementation looks all good
https://ideone.com/hMdw6I

tanavya: 2017-12-01 13:08:35

Use ceil(sqrt(Q)) instead of int(sqrt(Q)) to get it to pass!!

gaurav__404: 2017-10-31 20:59:31

AC in one go ;). Use Mo's Algo(see https://www.hackerearth.com/practice/notes/mos-algorithm/) and scanf / printf instead of cin / cout.

themast3r: 2017-10-21 06:20:35

AC in one go ;). Use Mo's Algo(see https://www.hackerearth.com/practice/notes/mos-algorithm/) and scanf / printf instead of cin / cout.

sahil_1994: 2017-10-14 21:02:40

Hint for solving using segment tree(offline).
1.start with thinking how to find number of different elements in a given range i to j.A simple solution is to iterate from i to j and make the corresponding element 0 or 1 depending on whether you have found that element previously or not.
2.Now update the above information using a segment tree previously built to get the answer for the sub range problems in the range i to j.
3.To make a segment tree you have to merge the original array with the right range value of query i.e b in[a,b] of query value and then sort this array according to primary index of the original array of the primary index but if b==some primary index you have to make a query just after this primary index.

Last edit: 2017-10-14 21:03:18
Shubham Gupta: 2017-10-12 11:49:45

Remember to use scanf/printf instead of cin/cout.


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