배열 쿼리

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

요약

배열에서 구간의 각 원소를 정수 제곱근으로 바꾸고, 구간 합을 구하고, 구간에 값을 더하는 쿼리를 처리합니다.

난이도: 보통10점 중 7점
유형: 세그먼트 트리, 수학
정답자: 아직 제출이 없습니다

문제

이야기가 없는 문제를 좋아하지 않는 사람이 있을까? 여기 또 하나 있다.

정수 배열 $a_1, a_2, \cdots, a_N$ 이 주어진다. 이어서 $Q$ 개의 쿼리가 주어지며, 각 쿼리는 다음 세 가지 유형 중 하나이다.

$L \le i \le R$ 인 모든 $a_i$ 를 $\lfloor \sqrt{a_i} \rfloor$ 로 바꾼다. 여기서 $\sqrt{a}$ 는 $a$ 의 제곱근이고, $\lfloor b \rfloor$ 는 $b$ 의 소수점 이하를 버린 정수 값이다.
$L \le i \le R$ 인 모든 $a_i$ 의 합을 출력한다.
$L \le i \le R$ 인 모든 $a_i$ 에 $x$ 를 더한다.

입력

첫 줄에 테스트 케이스의 수 $T$ ( $1 \le T \le 100$ )가 하나의 정수로 주어진다. 각 테스트 케이스는 정수 $N$ ( $1 \le N \le 10^5$ )과 $Q$ ( $1 \le Q \le 20{,}000$ )가 공백으로 구분되어 적힌 줄로 시작한다.

다음 줄에는 초기 값 $a_1, a_2, \cdots, a_N$ ( $1 \le a_i \le 10^6$ )이 공백으로 구분되어 주어진다.

이어서 $Q$ 개의 줄에 다음 형식 중 하나의 쿼리가 주어진다 ( $1 \le L \le R \le N$ , $1 \le x \le 10^6$ ).

유형 1: 1 L R
유형 2: 2 L R
유형 3: 3 L R x

출력

유형 2 쿼리마다 답을 한 줄에 출력한다.

예제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