Submit | All submissions | Best solutions | Back to list |
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
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 |
hide comments
|
|||||
2024-08-10 11:56:28
simple MO algorithm |
|||||
2024-03-08 23:14:32
AC IN 1E9+7 LET'S GOOOOOOOOOOOOOOOO! |
|||||
2023-07-27 12:41:32
莫队和树没有关系吧(雾 |
|||||
2023-03-15 06:07:16
just use president Tree to solve this |
|||||
2023-03-14 15:47:38
Me too! AC with MO algorithm Tree Is also ok!! They both are tarjin algorihtm Last edit: 2023-03-14 15:48:01 |
|||||
2022-12-03 21:27:43
Solved in one go using your mom |
|||||
2022-07-25 17:36:04
AC in one go with sorting + range sum |
|||||
2022-07-25 12:14:01
Solved using MO's in one go |
|||||
2022-06-29 09:08:44
If you want to solve using segment tree (online) then lookup merge sort tree first. |
|||||
2021-11-02 08:25:51
Binary Indexed Tree with off line algorithms. AC in one go :) |