Shil and Magic of Arrays
Practice
4.5 (2 votes)
Ready
Mathematics
Hard
Approved
Sqrt Decomposition
Mathematics
Mathamatics
Problem
86% Success 868 Attempts 50 Points 4s Time Limit 512MB Memory 1024 KB Max Code
Shil has an array of N elements A1 , A2 .... AN . He wants to perform two types of operations on this array.
- 1 i K: Update the value of Ai to K i.e do Ai = K
- 2 P : Find the magical value of subarray A1, A2 .... AP
Input:
First line of input contains N and Q denoting length of array A and number of operations to be performed respectively.
Next Q lines consists of operations of type 1 or type 2 in the format mentioned above. Each element of array is initially initialized to 0.
Output:
For each operation of type 2 , output the magical value modulo 109 + 7.
Constraints:
- 1 ≤ N ≤ 2 * 105
- 1 ≤ Q ≤ 2 * 105
- 1 ≤ P, K ≤ N
Submissions
Please login to view your submissions
Similar Problems
Points:50
Tags:
HardMath
Points:30
23 votes
Tags:
AlgorithmsMedium
Points:50
1 votes
Tags:
HardRecruitGrammar-VerifiedReadyMathematicsApprovedMathematicsMathamatics
Editorial