Array Queries

시간 제한2초메모리 제한512 MB

요약
배열에 구간 제곱근 내림 갱신, 구간 덧셈, 구간 합 질의를 처리한다.
난이도

보통10점 중 7점

유형
세그먼트 트리, 수학, 연결 리스트, 완전 탐색
정답자
아직 제출이 없습니다

문제

We all love problems without a story, who doesn’t?! Here’s one more.

In this problem you are given an array of N integers a1, a2, · · · , aN. Followed by Q queries, each query will be in one of the following types:

  1. For each integer ai where L ≤ i ≤ R, replace it with floor(sqrt(ai)). Where sqrt(a) is the square root of a, and floor(b) is the integer value of b after removing everything on the right of the decimal point.
  2. Print the sum of all integers ai where L ≤ i ≤ R.
  3. Add x to each integer ai where L ≤ i ≤ R.

입력

Your program will be tested on one or more test cases. The first line of the input will be a single integer T (1 ≤ T ≤ 100) representing the number of test cases. Followed by T test cases.

Each test case starts with a line containing 2 integers separated by a space, N (1 ≤ N ≤ 105)

representing the number of integers in the array and Q (1 ≤ Q ≤ 20, 000) representing the number of queries.

Followed by a line containing N integers separated by a space, which are the initial integers in the array a1, a2, . . . , aN (1 ≤ ai ≤ 106).

Followed by Q lines, each line will be in one of the following formats (1 ≤ L ≤ R ≤ N) and (1 ≤ x ≤ 106):

  • A query of the first type: 1 L R
  • A query of the second type: 2 L R
  • A query of the third type: 3 L R x

출력

For each query of the second type, print the corresponding answer in a single line.

예제1

  1. 예제 1

    입력
    1
10 7
1 5 123 53 12 2901 12 1234 657 3419
2 3 7
3 5 8 1
1 2 4
3 1 6 1000
2 1 10
2 2 8
1 3 5
    예상 출력
    3101
14260
9183