bsdlcksdn   1년 전

부분합을 구하길래 dp가 생각나서 우선 입력받을때 값을 입력받은 것 까지의 합을 dp배열에 저장합니다.

그리고 a==1이면 visit이라는 배열을 만들어서 visit[][0]에는 위치(idnex)를 , visit[][1]에는 바꿀 값(c)를 저장합니다.

a==2이면 sum이라는 변수에 2~5구간이라고 치면 dp[5]-dp[1]을 하여 구간합을 구하고

visit배열을 탐색하면서 2~5구간 사이에 있는 index(=visit[][0])을 확인하여 있으면 기존의 배열의 값 arr[visit[][0]]을 빼고 / visit[][1]을 더하

는 방식으로 만들었습니다.

testcase도 바꿔가면서 돌려보는데 채점(2%)에서 계쏙 틀리네요;;; 뭐가 문제일까요?

시간도 m,k가 10000씩이니까 최대 20000이고 / visit배열에서 찾아도 10000이면 약 2억정도 돌것같은데;; 시간상에도 문제가있을까요?

nisroeld99   1년 전

일반적으로 펜윅트리로 푸는것같습니다 


https://www.acmicpc.net/blog/view/21#comment-80

rdd6584   3주 전

같은 인덱스에 대해서 2번이상 값이 변경된 경우 값이 이상하게 나올 것 같네요.

rdd6584   3주 전

음수면 더하고 양수면 빼고 부분도 이해가 잘 가지않아요.

rdd6584   3주 전

위 부분 고치니까

916ms로 통과했어요. 조금만 수정해보세요.

시간은 아슬할거 같았는데, 이정도 사이즈에서는 통과하네요.

댓글을 작성하려면 로그인해야 합니다.