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
|
aryan_sapra:
2019-08-10 06:48:04
Strictly saying use scanf and printf.....and MO's algo...AC in first gooooo:^)> |
|
danos:
2019-08-01 14:29:41
Use BIT instead of segment tree to avoid TLE. |
|
sudhanshu6324:
2019-06-29 20:14:31
loved the problem but unnecessary time limit constraint |
|
smrtdvlpr:
2019-06-27 14:43:59
Very strict time limit really |
|
eagleshadow:
2019-06-03 15:00:57
Very Strict time Limit!! |
|
amantu_amir:
2019-04-07 21:25:12
Nice problem!! |
|
surajgoel1225:
2019-04-04 18:38:29
segtree and sets ..!! |
|
viniet_sw:
2019-03-27 14:30:38
dimaag ka bhosada kar dia question ne |
|
vartik_s:
2019-03-20 12:09:07
very strict time limit. got tle even after using cin.tie and sync with stdio. Finally got accepted using scanf and printf. Used MO's algorithm. Watch GKCS' video on the topic and you are good to go Last edit: 2019-03-20 12:09:44 |
|
itssanat:
2019-03-09 11:16:03
better to use scanf and printf because of strict time |
Added by: | Duc |
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: | © VNOI |