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
arvindj97: 2018-11-09 09:36:07

Getting tle while using java with fenwick tree

Pls suggest any suitable java code.

davitmarg: 2018-11-07 14:47:01

AC in 14 mo

alexandro5432: 2018-10-26 20:43:37

offline BIT+very fast io+inline functions+many optimisations=AC
I am coding in c++ but I think TL is very strict.

Last edit: 2018-10-26 20:44:25
skirim06: 2018-09-29 00:27:56

MO's + fast io + cpp = AC
MO's + fast io + java = TLE

dipankar12: 2018-09-23 12:13:32

java+mo getting TLE. Anyone solved using JAVA and mo?

Last edit: 2018-09-23 12:13:50
redcenturion: 2018-09-18 08:17:59

Can we solve this by segment tree ?

lax_99: 2018-08-31 08:26:07

If you're using MO's algorithm, make sure you use array instead of vector and array of frequencies instead of Hash Table.

bharat133: 2018-08-10 10:47:31

Last edit: 2018-08-10 10:48:11
sdeven_0245: 2018-08-04 20:17:39

Mo works fine but not the fenwick gives TLE for me..

Last edit: 2018-08-15 18:32:18
wsrstf: 2018-07-14 16:48:01

I guess this can be solved using slide window method? Sort all query segments and everything is much easier then.


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