[백준 / BOJ] 1275 커피숍2

문제

출처 : https://www.acmicpc.net/problem/1275

1275번: 커피숍2

커피숍 마담 동호는 손님들과 게임을한다.

 

게임 방식은 다음과 같다.

 

N개의 수가 있으면 동호는 손님에게 3~7번째 수를 묻는다. 

이때, 손님이 답은 000 입니다 라고 대답을한다.

그후, 8번째 수를 2로 고친다. 

 

풀이

기본적인 세그먼트 트리로 풀리는 문제였다.

 

구현은 다음과 같다. 

 

1. 입력받은 정수N개를 세그먼트 트리구조로 저장해놓는다.

 

2. 쿼리를 입력받을때마다 세그먼트 트리에서 해당 구간을 찾아 구해주고, 수를 바꿔준다.

 

이때, 입력받는 수를 다 더할경우, 2^31 * 100000 만큼 증가할수있으므로, long long 을 사용해서 저장해야한다.

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/1275%20%EC%BB%A4%ED%94%BC%EC%88%8D2/main.cpp

devxb/JJUNalgo