The maximum distance

3.7

32 votes
Advanced Data Structures, Algorithms, Data Structures, Segment Trees, Square Root Decomposition
Problem

You are given an array a1, a2, , aN consisting of N elements. You are given Q queries. Each query is of the following types:

  1. The format of the first type of query is 1 L R x. You must increase the values of all elements in range L to R (both inclusive) by integer x.
  2. The format of the second type of query is 2 L R y. You must multiply the values of all elements in range L to R (both inclusive) by the integer y.
  3. The format of the third type of query is 3 z. You are required to find the maximum distance between elements that are equal to z in the array. If the element is not present in the array, print -1.

Input format

  • The first line contains an integer N.
  • The next line contains N integers a1, a2, , aN denoting the elements of the array.
  • The next line contains Q denoting the number of queries.
  • The next Q lines contain one of the 3 queries mentioned above.

Output format

For every query of Type 3, print an integer denoting the maximum distance ji+1 where 1i, jn.

Note: The query of type 3 is present at least once in the problem.

Constraints

1N4000001ai1091L, RN1Q100001x, y, z1000000000

Note: No ai exceeds 1018 after updates.

Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

after 1st query, the array becomes:

 2 3 3 4 5

after 2nd query, the array becomes:

 6 9 9 12 5

3rd query: the distance is 2 (a= 9 & a= 9)

after 4th query, the array becomes:

6 9 9 12 6

5th query: the distance is 5 (a1 = 6 & a= 6)

Editor Image

?