DQUERY - D-query

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.


  • 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).


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


1 1 2 1 3
1 5
2 4
3 5


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

pradeepgangwar: 2017-10-09 15:35:58

My 100th. Mo's Algorithm does it :)

the_phoenixx: 2017-10-08 23:14:45

use scanf/printf only....
using cin/cout even with fast input/output costs several TLE!!

vishesh197: 2017-10-06 19:17:47

solved it using MO's algorithm and frequency array........AC in second go..0.40 sec.I tried to solve it using segment tree too but was'nt able to solve it.Can anybody suggest a solution with segment tree?

prabhat236218: 2017-10-01 15:58:53

@sdibt1 please help me how you did it

prabhat236218: 2017-09-29 18:53:36

i am also getting TLE in java solution using MO's algo and fenwick tree also..... help me....what should i do

hitman007: 2017-09-24 16:07:11

Has anyone solved it in Java using MO algorithm ? I am constantly getting TLE despite using fast I/O.

sirjan13: 2017-09-09 20:32:52

Used Mo's Algorithm:
cout/cin with fast_io -->TLE
scanf/printf --> AC :)

Be Careful

Added by:Duc
Time limit:0.227s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:© VNOI