Comparing Arrays

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 3.0s
Memory limit: 1G

Author:
Problem types

Given an array, A, of N integers, answer Q queries of 2 types:

1 l_1 r_1 l_2 r_2: Output 1 if the subarray from [l_1, r_1] is identical to [l_2, r_2] or 0 if they are not identical. An array is identical to another if the lengths are equal and the same numbers are present in the same order.

2 i v: Update the integer at index i to v.

Constraints

For all subtasks:

1 \le N, Q \le 5 \times 10^5

1 \le A_i, v \le 10^9

r_1 - l_1 = r_2 - l_2

1 \le l_1 \le r_1 \le N

1 \le l_2 \le r_2 \le N

Subtask 1 [20%]

1 \le N, Q \le 5\,000

Subtask 2 [80%]

No additional constraints.

Input Specification

The first line will contain N and Q, the number of integers in the array and the number of queries, respectively.

The next line will contain N integers, the array's contents.

The next Q lines will contain one of two queries.

Output Specification

For each query of type 1, output 1 if the arrays are identical and 0 if they are not.

Sample Input

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

Sample Output

1
1
0

Comments

There are no comments at the moment.