All Tracks>Data Structures> Advanced Data Structures> Segment Trees> Problem
Incremental queries
★★★★★

3.3

22 votes
Segment Trees, Fenwick Tree, Advanced Data Structures, Data Structures, Mathematics, Segment tree
Problem

You are given an array A consisting of N elements A1,A2,A3, ...,AN. You must process N queries and there are two types of queries:

  • 1 L R: Replace Lth element by R, that is, AL=R.
  • 2 L R: You are required to print the minimum number of operations to make all elements equal in subarrays AL,AL+1, ...,AR.

You can perform the following operation in order to make elements equal:

  • Select any index L and replace AL with AL+1 or AL+2.

Note: You do not have to modify the original array in a query of type 2.

Input format

  • The first line contains two space-separated integers N and Q.
  • The second line contains space-separated integers A1,A2,A3, ...,AN.
  • Each of next Q lines contains three integers type L, R denoting the type of query and its parameters.

Output format

Print a single integer for every query of the second type.

Constraints

  • 1≤N≤500000
  • 1≤Q≤500000
  • 1≤Ai≤1e9∀i∈[1,N]

The types of queries are either 1 or 2.

If the type is 1:

  • 1≤L≤N
  • 1≤R≤1e9

If the type is 2:

  • 1≤L≤R≤N

 

Sample Input
4 3
1 3 4 1
2 1 2
1 2 4
2 2 3
Sample Output
1
0
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

Our initial array is [1,3,4,1] and now we will process the queries:

  • We need to consider subarray [1,3] if we once increment first element by 2 we will get [3,3] so minimum operations required will be 1 and our array will remain [1,3,4,1].
  • We need to replace and index by 4, so array will be [1,4,4,1]
  • We need to consider subarray [4,4] since this subarray is already equal, number of operations are 0.

 

Contributers:
Editor Image

?