bsdlcksdn   9달 전

부분합을 구하길래 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   5달 전

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


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

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