DQUERY - D-query
English | Vietnamese |
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
hide comments
|
killshot667:
2020-12-27 21:28:39
good to question to learn mo's algorithm. Can probably also be solved using Segment trees |
|
mr_cchef:
2020-12-18 15:12:15
Guys, please help me. I am doing this using mo's Algorithm but somehow I get WA.
|
|
trungnt2910:
2020-11-23 13:15:19
Persistent Segment Tree Online queries easy AC in one go.
|
|
sowmiksarker:
2020-11-21 14:23:44
Solved it with:
|
|
ankush08:
2020-11-12 06:34:24
I dont know what is Mo's Algo ! Any approach using segment trees ? or will i have to first learn what this algorithm is ? |
|
kapil16garg:
2020-11-08 12:59:10
Those are getting TLE after using Mo's algo...use vector for store frequency instead of map |
|
soumalya_1:
2020-10-21 16:33:49
use fenwick/bit tree |
|
tpriyanshu:
2020-09-15 00:13:40
MO's Algorithm, implementation. Do read MO's Algo first. |
|
thelegend27101:
2020-07-23 09:22:42
MO's ALgo in python gives TLE |
|
wahidmshafin:
2020-07-03 09:32:27
Offline solution is easier. |
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 |