만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

수열과 쿼리 19

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

요약
수열에 구간 덧셈, 구간 d로 나눈 몫으로 치환을 적용하고 구간 최솟값과 구간 합을 구한다.
난이도

어려움10점 중 8점

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

문제

길이가 nn인 수열 A0,A1,…,An−1A_0, A_1, \dots, A_{n-1}이 있다. 다음 네 가지 쿼리를 처리하는 프로그램을 작성하시오.

  • 1 l r c: l≤i≤rl \le i \le r인 모든 AiA_i에 cc를 더한다.
  • 2 l r d: l≤i≤rl \le i \le r인 모든 AiA_i를 ⌊Ai/d⌋\lfloor A_i / d \rfloor로 바꾼다.
  • 3 l r: l≤i≤rl \le i \le r인 모든 AiA_i 중에서 가장 작은 값을 출력한다.
  • 4 l r: l≤i≤rl \le i \le r인 모든 AiA_i의 합을 출력한다.

⌊x⌋\lfloor x \rfloor는 xx 이하의 정수 중 가장 큰 값이다. 예를 들어 ⌊−2.5⌋=−3\lfloor -2.5 \rfloor = -3이고, ⌊−7⌋=−7\lfloor -7 \rfloor = -7이다.

입력

첫째 줄에 수열의 크기 nn과 쿼리의 개수 qq가 주어진다. (1≤n,q≤100 0001 \le n, q \le 100\,000)

둘째 줄에 A0,A1,…,An−1A_0, A_1, \dots, A_{n-1}이 주어진다. (−109≤Ai≤109-10^9 \le A_i \le 10^9)

다음 qq개 줄에 쿼리가 한 줄에 하나씩 주어진다. (0≤l≤r≤n−10 \le l \le r \le n-1, −104≤c≤104-10^4 \le c \le 10^4, 2≤d≤1092 \le d \le 10^9)

출력

3번 쿼리와 4번 쿼리가 주어질 때마다 답을 한 줄에 하나씩 출력한다.

예제2

  1. 예제 1

    입력
    10 10
-5 -4 -3 -2 -1 0 1 2 3 4
1 0 4 1
1 5 9 1
2 0 9 3
3 0 9
4 0 9
3 0 1
4 2 3
3 4 5
4 6 7
3 8 9
    예상 출력
    -2
-2
-2
-2
0
1
1

  2. 예제 2

    입력
    1 6
-7
3 0 0
4 0 0
2 0 0 2
3 0 0
1 0 0 10
4 0 0
    예상 출력
    -7
-7
-4
6