Sequence Master codechef solution- Given is a sequence AA of length NN. Define f(i,j)f(i,j) to be the number of distinct elements in Ai,Ai+1,…,AjAi,Ai+1,…,Aj. You need to process QQ queries of the following two types: 1 x y1 x y — set Ax=yAx=y. 2 k2 k — print ∑i=1k∑j=ikf(i,j)∑i=1k∑j=ikf(i,j).

 Sequence Master solution codechef

 

Given is a sequence AA of length NN.

Define f(i,j)f(i,j) to be the number of distinct elements in Ai,Ai+1,,AjAi,Ai+1,…,Aj.

You need to process QQ queries of the following two types:

  • 1 x y1 x y — set Ax=yAx=y.
  • 2 k2 k — print i=1kj=ikf(i,j)∑i=1k∑j=ikf(i,j).

Input Format

  • The first line of input contains two integers NN and QQ — the size of the array and the number of queries.
  • The second line of input contains NN space-separated integers A1,A2,,ANA1,A2,…,AN.
  • Then, QQ lines follow, describing queries in the format given in the statement.

Output Format

For each type 22 query, print the answer to it on a new line.

Constraints

  • 1N,Q21051≤N,Q≤2⋅105
  • 1AiN1≤Ai≤N
  • 1x,yN1≤x,y≤N
  • 1kN1≤k≤N

Subtasks

  • Subtask 1 (20 points): No type 11 queries
  • Subtask 2 (80 points): Original constraints

Sample Input 1 

3 2
1 2 2
2 2
2 3

Sample Output 1 

4
8

Explanation

Test Case 11: The answer is f(1,1)+f(1,2)+f(2,2)=1+2+1=4f(1,1)+f(1,2)+f(2,2)=1+2+1=4.

Test Case 22: The answer is f(1,1)+f(1,2)+f(1,3)+f(2,2)+f(2,3)+f(3,3)=1+2+2+1+1+1=8f(1,1)+f(1,2)+f(1,3)+f(2,2)+f(2,3)+f(3,3)=1+2+2+1+1+1=8.

Sample Input 2 

5 5
1 2 3 4 5
2 5
1 1 2
2 3
2 4
2 5

Sample Output 2 

35
8
17
31

Leave a Comment

Your email address will not be published.