Distinct Query With Updates

Hard

0/120

Average time to solve is 60m

Contributed by

2 upvotes

Asked in company

Problem statement

Given a sequence of n numbers a1, a2, ..., an, and a number of d-queries of the following types.

1. For each d-query (1, i, j),You have to return the number of distinct elements in the subsequence (i,j)i.e., ai, ai+1, ..., aj. where (1 ≤ i ≤ j ≤ n).
2. For each d-query (2, i, x), you have to update a[i]=x. where(1 ≤ x ≤ 10^6)

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

Line 1: n (1 ≤ n ≤ 30000).
Line 2: n numbers a1, a2, ..., an (1 ≤ ai ≤ 10^6).
Line 3: q (1 ≤ q ≤ 200000), the number of d-queries.
In the next q lines, each line contains 3 numbers, (type, i, j) representing a d-query (1 ≤ i ≤ j ≤ n).

Output Format:

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

Sample Input 1:

Sample Output 1:

3
2

Approaches (1)

Approach 1

MO'S Algorithm

Time Complexity

Space Complexity

(100% EXP penalty)

Distinct Query With Updates

Console