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
The magical value of array B1 , B2 .... Br is defined as product of (f[i]+1)(f[i]+1) where f[i] is the number of times i occurs in array B.

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

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:50
1 votes
Tags:
HardRecruitGrammar-VerifiedReadyMathematicsApprovedMathematicsMathamatics
Points:30
23 votes
Tags:
AlgorithmsMedium
Points:50
Tags:
HardMath