Naruto - The New Hokage
Practice
4.5 (6 votes)
Advanced data structures
Data structures
Medium
Segment trees
Problem
46% Success 1531 Attempts 30 Points 2s Time Limit 256MB Memory 1024 KB Max Code

Naruto was declared as the \(7^{th}\) Hokage because of his great contribution in the \(4^{th}\) Shinobi World War. As soon as he aquires office, he changes the process of ranking of Shinobis. Instead of the Genin (Beginner), Chuunin (Intermediate) and Jounin (Expert), the new ranks are numbers ranging from 1 (lowest) to \(10\) (highest).
There are a total of N ninjas in the Leaf Village, \(i^{th}\) of which has \(A_{i}\) amount of chakra (energy). A ninja with rank P would have a strength of \({A_{i}}^{P}\).
Naruto has Q pending tasks to perform which can be of one of the following types:-

  • \(1\; i\; K\) : Update the result of training of the \(i^{th}\) ninja i.e. increase the amount of chakra of the \(i^{th}\) ninja by K.
  • \(2\; L\; R\; K\) : Update the result of training of the ninjas ranging from L to R i.e. increase the amount of chakra of the ninjas ranging from L to R by K.
  • \(3\; L\; R\; P\) : Calculate the total strength of the ninjas ranging from L to R provided that each of these ninjas have rank P for sending them to a mission assigned to the Leaf Village. As the value can be very large, calculate it modulo \(10^{9} + 7\).

Naruto asked you to take care of these tasks.

INPUT FORMAT
The first line of input contains a single integer T denoting the number of test cases.
The first line of each test case contains a single integer N denoting the number of ninjas in the Leaf Village.
The next line contains N space separated integers. \(i^{th}\) integer denotes the amount of chakra \(A_{i}\) in the \(i^{th}\) ninja.
The third line contains a single integer Q denoting the number of pending tasks that Naruto has.
This is followed by Q lines each containing the description of a task that Naruto has to perform.

OUTPUT FORMAT
The output should consist of the answer of all the queries of the \(3^{rd}\) type printed on a new line.

CONSTRAINTS

  • \(1 \le T \le 3\)
  • \(1 \le N \le 10^{5}\)
  • \(1 \le A_{i}, K \le 10^{6}\)
  • \(1 \le Q \le 2\times10^{4}\)
  • \(1 \le L \le R \le N\)
  • \(1 \le P \le 10\)

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:30
6 votes
Tags:
ApprovedData StructuresFenwick TreeMediumOpenTrees
Points:30
103 votes
Tags:
MediumSegment TreesTrees
Points:30
36 votes
Tags:
ApprovedDynamic ProgrammingMediumOpenReadySegment TreesTrees