cho.sh계산 최적화
아직 제출이 없습니다시간 제한2초메모리 제한512 MB문제 설명
예제1
문제
현욱은 덧셈과 곱셈을 계산할 수 있는 간단한 계산 장치를 만들었다. 이 계산 장치는 처음에 값 0에서 시작해서 N(1≤N≤5⋅105)번의 연산을 순서대로 수행한 결과값을 반환한다. 연산은 아래의 두 종류가 있다.
- + k : 이전 값에 k를 더한다(1≤k≤109)
- * k : 이전 값에 k를 곱한다(1≤k≤109)
연산 결과값이 아주 커질 수 있기 때문에 이 계산 장치는 항상 계산 결과값을 109+7로 나눈 나머지를 저장한다.
현욱은 이 계산 장치에서 일부 연산을 변경한 후 계산 결과가 어떻게 달라지는지를 확인하고 싶다. 현욱은 총 Q(1≤Q≤5⋅105)번 계산 장치의 연산을 변경할 예정이며, 연산 변경은 다음과 같은 형태로 주어진다.
- i + k : i번째 연산을 이전 값에 k를 더하는 연산으로 변경한다(1≤i≤N,1≤k≤109).
- i * k : i번째 연산을 이전 값에 k를 곱하는 연산으로 변경한다(1≤i≤N,1≤k≤109).
모든 변경 사항은 누적된다.
현욱은 연산 변경이 하나 일어날 때마다 다시 처음부터 계산을 하는게 너무 비효율적이라고 생각한다. 현욱을 도와 현욱의 계산 장치를 최적화해서, 연산 변경이 일어날 때 결과를 빠르게 다시 계산하는 프로그램을 작성해보자.
입력
첫줄에 연산의 개수 N과 연산을 변경할 횟수 Q가 공백으로 구분되어 주어진다(1≤N,Q≤5⋅105).
둘째 줄부터 N줄에 걸쳐 맨 처음 계산 장치를 구성하는 N개의 연산이 순서대로 주어진다.
그 다음부터 Q줄에 걸쳐 계산 장치의 연산을 어떻게 변경했는지 정보가 순서대로 주어진다.
출력
Q줄에 걸쳐 연산이 바뀔 때마다 계산 장치의 계산 결과값이 어떻게 바뀌는지 출력한다.