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
navin_chandra: 2019-12-26 09:44:16

Nice Problem :)

fardin_abir: 2019-12-22 18:25:15

solved using mo's algo... nice problem...

bp274: 2019-12-21 22:58:44

I used binary search to solve this. Stored the next index for each distinct element in the tree node and for each query used binary search to find how many elements from a node were occuring again. AC time was 1.60 but when I replaced cin/cout with printf/scanf it became 0.6

Last edit: 2019-12-21 23:10:37
scolar_fuad: 2019-12-02 11:32:21

Nice problem Ever
AC With MO's Algorithm

resources :Anudeep blog

Happy coding

madhukeshk3: 2019-11-23 10:53:54

Did it with segment tree in one go

hwvdev: 2019-11-19 12:03:03

using persistent segment tree makes it much easier

ab_biswas09: 2019-11-09 16:46:22

Offline query + BIT
Nyc problem

subodh898: 2019-11-08 13:55:59

Offline query + standard BIT

vjvjain0: 2019-10-22 22:36:00

My Java solution passes for Mo's algo

harry_shit: 2019-10-22 13:41:35

@surajgoel1225 did you get ac by using segtree and sets??
mine is giving tle by doing the same

edit:got ac by BIT

Last edit: 2019-10-23 13:20:21

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