%2021. 11. 30. 18:38에 작성된 글입니다%
https://www.acmicpc.net/problem/17477
17477번: 수열과 쿼리 29
길이가 N인 수열 A1, A2, ..., AN이 주어지고, Bi = 0를 만족하는 길이가 N인 수열 B가 있다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 L R X: 모든 L ≤ i ≤ R에 대해서 Ai = Ai + X를 적용한
www.acmicpc.net
한 9개월 전에 도전하다 때려치우고 오늘 다시 잡은 문제인데 결국 풀었다.
쿼리 꼴을 보아하니 '그들만의 웰노운' 세그비츠를 써야 할 것 같다. \(max, min, smax, smin, cmax, cmin\)과 함께 즐거운 세그트리를 짜자.
수열 B를 어떻게 할까 고민을 좀 했다. 일단 1번 쿼리는 lazy 쓰고 마지막에 합쳐주면 간단하게 해결될거고 2번 3번은? 대충 부모자식노드 최소최대정보 태그 달아서 해결했다.
그리고제출했더니\(1\%\)에서\(W\ A\)받았길래뭐가문제일까하다가\(500,000*499,999\)(수열크기*쿼리수)가int넘어가는데4번쿼리가잔뜩모아서한방에터지면다뒤지겠구나싶어서수열B부분을전부8바이트정수형으로갈고제출했더니\(34\%\)에서\(W\ A\)받았길래뭐가문제일까하다가그냥냅다다른놈들자료형도
8바이트정수형으로싸그리갈고제출했더니\(A\ C\)받았다.