Fast Search

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type

Chunky Munky has an array of N numbers a_1, a_2, \ldots, a_N, along with Q queries.

Each query is one of the following 2 types:

  • 1 p x: Set a_p=x.
  • 2 l r k: Chunky Munky picks up a_l, then a_{l+1}, a_{l+2}, \ldots all the way until a_r, and would like to know the index of the first element he picks up with a value strictly less than k. It's guaranteed that the value of k will always be such that he will pick up a value strictly less than k during the process.

Help Chunky Munky answer his queries!

Note that this problem will be online enforced, meaning that input will be given in an encrypted format. To encrypt the data, the values p,x,l,r,k in queries will be given as p \oplus \text{lastAns},x \oplus \text{lastAns},l \oplus \text{lastAns},r \oplus \text{lastAns}, and k \oplus \text{lastAns}, where \oplus denotes the bitwise XOR operation. Note that \text{lastAns} at any time is defined as the answer to the latest type 2 query. If no type 2 queries have occurred so far, \text{lastAns}=0.

Constraints

For all subtasks:

1 \le N, Q \le 10^6

1 \le a_i, x, k \le 10^9

1 \le p \le N

1 \le l \le r \le N

For 3 of 20 points, 1 \le N, Q \le 2\,000.

For 10 of 20 points, 1 \le N, Q \le 100\,000.

For all 20 points, no additional constraints apply.

Input Specification

The first line contains the integers N and Q.

The second line contains the array a_1, a_2, \ldots, a_N.

The next Q lines each contain a query of one of the above types.

Output Specification

For each query of type 2, output its answer on a separate line.

Sample Input

10 5
3 1 4 1 5 9 2 6 5 3
2 6 10 6
2 2 14 1
2 6 2 6
1 0 14
2 7 3 7

Sample Input (Unencrypted)

10 5
3 1 4 1 5 9 2 6 5 3
2 6 10 6
2 5 9 6
2 3 7 3
1 4 10
2 3 7 3

Sample Output

7
5
4
7

Comments

There are no comments at the moment.