문제
길이가 n인 배열 A1, A2, ..., An 이 있다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오.
1 x y v : Ai = (Ai + v) % MOD를 수행한다. (x ≤ i ≤ y)
2 x y v : Ai = (Ai x v) % MOD를 수행한다. (x ≤ i ≤ y)
3 x y v : Ai = v를 수행한다. (x ≤ i ≤ y)
4 x y : Ai 합을 MOD로 나눈 나머지를 출력한다. (x ≤ i ≤ y)
여기서 MOD는 109+7이며, %는 나머지 연산을 의미한다.
이 문제는 O(N log N)에 해결할 수 있도록 하자.
입력
첫째 줄에 배열의 크기 n과 쿼리의 개수 q (1 ≤ n, q ≤ 500,000)가 주어진다.
둘째 줄에는 A1, A2, ..., An이 주어진다. (1 ≤ Ai> ≤ 109)
다음 q개의 줄에는 쿼리가 한 줄에 하나씩 주어진다. (1 ≤ x ≤ y ≤ n, 1 ≤ v ≤ 109)
출력
4번 쿼리가 주어질 때 마다 정답을 한 줄에 하나씩 출력한다.
예제
4 4
1 2 3 4
4 1 4
1 1 3 10
2 2 4 2
4 1 4
10
69
태그
로그인해야 코드를 작성할 수 있어요.