시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 261 | 113 | 90 | 53.254% |
현욱은 덧셈과 곱셈을 계산할 수 있는 간단한 계산 장치를 만들었다. 이 계산 장치는 처음에 값 $0$에서 시작해서 $N$($1 \le N \le 5 \cdot 10^5 $)번의 연산을 순서대로 수행한 결과값을 반환한다. 연산은 아래의 두 종류가 있다.
연산 결과값이 아주 커질 수 있기 때문에 이 계산 장치는 항상 계산 결과값을 $10^9+7$로 나눈 나머지를 저장한다.
현욱은 이 계산 장치에서 일부 연산을 변경한 후 계산 결과가 어떻게 달라지는지를 확인하고 싶다. 현욱은 총 $Q$($1 \le Q \le 5 \cdot 10^5 $)번 계산 장치의 연산을 변경할 예정이며, 연산 변경은 다음과 같은 형태로 주어진다.
모든 변경 사항은 누적된다.
현욱은 연산 변경이 하나 일어날 때마다 다시 처음부터 계산을 하는게 너무 비효율적이라고 생각한다. 현욱을 도와 현욱의 계산 장치를 최적화해서, 연산 변경이 일어날 때 결과를 빠르게 다시 계산하는 프로그램을 작성해보자.
첫줄에 연산의 개수 $N$과 연산을 변경할 횟수 $Q$가 공백으로 구분되어 주어진다($1 \le N, Q \le 5 \cdot 10^5 $).
둘째 줄부터 $N$줄에 걸쳐 맨 처음 계산 장치를 구성하는 $N$개의 연산이 순서대로 주어진다.
그 다음부터 $Q$줄에 걸쳐 계산 장치의 연산을 어떻게 변경했는지 정보가 순서대로 주어진다.
$Q$줄에 걸쳐 연산이 바뀔 때마다 계산 장치의 계산 결과값이 어떻게 바뀌는지 출력한다.
$1 \le N, Q \le 1000 $
항상 모든 곱셈 연산은 모든 덧셈 연산보다 뒤에 나온다.
$1 \le N, Q \le 50000 $
추가 제한 없음
6 10 + 3 * 2 + 2 * 3 + 4 * 5 1 + 2 3 * 1 4 * 5 2 + 6 2 * 2 1 * 2 3 * 1 4 + 4 1 + 5 3 * 4
110 80 120 220 120 20 20 40 90 240
Contest > BOJ User Contest > 소프트콘 > 제3회 소프트콘 D번