Status:  Past  Start:  20160409 10:00:00  End:  20160409 14:00:00 
Liga Cubana de Programación 2016 (Etapa III  OPEN)
Problem
3417  Below The Root
Created by  Luis Manuel Díaz Barón 
Added by  luismo (20151123) 
Limits 
Total Time: 8000 MS

Test Time:
2000 MS
Memory: 512 MB  Output: 64 MB  Size:
9 KB

Enabled languages  
Available in 
Description
Once you bought your cellphone with Android, you realized that you wanted to become a developer, by the time you had a certain level developing apps, you found out that you needed to get Super User access into your phone’s operative system, so you needed to “root” it. To achieve you goal, your cellphone will put you through an easy task.
You will be given an array of N (1 <= N <= 10^5) integers randomly generated between 1 and 10^9 and you will perform Q (1 <= Q <= 10^5) queries on it:
Query 1: Given an interval [i, j], with i and j between 1 and N you will reduce to its square root each of the array inside this interval. Is the resulting value is not an integer you will truncate it.
Query 2: Given two integers i and v, you will change the value at position i by v.
Query 3: Given an interval [i, j], with i and j between 1 and N you will print the sum of the values of the array inside this interval.
Once you finish the task correctly you will get Super User access in your phone.
Once you bought your cellphone with Android, you realized that you wanted to become a developer, by the time you had a certain level developing apps, you found out that you needed to get Super User access into your phone’s operative system, so you needed to “root” it. To achieve you goal, your cellphone will put you through an easy task.
You will be given an array of N (1 <= N <= 10^5) integers randomly generated between 1 and 10^9 and you will perform Q (1 <= Q <= 10^5) queries on it:
Query 1: Given an interval [i, j], with i and j between 1 and N you will reduce to its square root each of the array inside this interval. Is the resulting value is not an integer you will truncate it.
Query 2: Given two integers i and v, you will change the value at position i by v.
Query 3: Given an interval [i, j], with i and j between 1 and N you will print the sum of the values of the array inside this interval.
Once you finish the task correctly you will get Super User access in your phone.
Once you bought your cellphone with Android, you realized that you wanted to become a developer, by the time you had a certain level developing apps, you found out that you needed to get Super User access into your phone’s operative system, so you needed to “root” it. To achieve you goal, your cellphone will put you through an easy task.
You will be given an array of N (1 <= N <= 10^5) integers randomly generated between 1 and 10^9 and you will perform Q (1 <= Q <= 10^5) queries on it:
Query 1: Given an interval [i, j], with i and j between 1 and N you will reduce to its square root each of the array inside this interval. Is the resulting value is not an integer you will truncate it.
Query 2: Given two integers i and v, you will change the value at position i by v.
Query 3: Given an interval [i, j], with i and j between 1 and N you will print the sum of the values of the array inside this interval.
Once you finish the task correctly you will get Super User access in your phone.
Input specification
In the first line two space separated integers N (1 <= N <= 10^5) and Q (1 <= Q <= 10^5)
The second line contains N spaced separated integers, the values of the randomly generated array
The next Q lines contain three space separated integers representing the description of a single query in the format below:
1 i j – for the first query
2 i v – for the first query
3 i j – for the first query
In the first line two space separated integers N (1 <= N <= 10^5) and Q (1 <= Q <= 10^5)
The second line contains N spaced separated integers, the values of the randomly generated array
The next Q lines contain three space separated integers representing the description of a single query in the format below:
1 i j – for the first query
2 i v – for the first query
3 i j – for the first query
In the first line two space separated integers N (1 <= N <= 10^5) and Q (1 <= Q <= 10^5)
The second line contains N spaced separated integers, the values of the randomly generated array
The next Q lines contain three space separated integers representing the description of a single query in the format below:
1 i j – for the first query
2 i v – for the first query
3 i j – for the first query
Output specification
For each
query of type 3 print the asked value
For each
query of type 3 print the asked value
In the first line two space separated integers N (1 <= N <= 10^5) and Q (1 <= Q <= 10^5)
The second line contains N spaced separated integers, the values of the randomly generated array
The next Q lines contain three space separated integers representing the description of a single query in the format below:
1 i j – for the first query
2 i v – for the first query
3 i j – for the first query
Sample input
6 54 3 3 4 5 81 1 42 3 53 1 61 3 53 4 6
Sample output
2311
Hint(s)
Cambiar los jds que tienen a > b en la query
Cambiar los jds que tienen a > b en la query
Cambiar los jds que tienen a > b en la query