글 읽기 - 무엇이 틀렸을까요?

(追記) (追記ここまで)

무엇이 틀렸을까요?

10999번 - 구간 합 구하기 2

zzzzzz 3년 전 0

게시판에서 주어지는 반례 모두 맞게 나오는데 틀리다고 나오네요.

package org.example;
import java.io.*;
import java.util.StringTokenizer;
class Main {
 static int n;
 static long[] elements;
 static class SegmentTree {
 static class Node {
 long value;
 long lazy;
 Node leftChild, rightChild;
 }
 static Node getNode() {
 Node temp = new Node();
 temp.value = 0;
 temp.lazy = 0;
 temp.leftChild = null;
 temp.rightChild = null;
 return temp;
 }
 static void updateLazy(Node node, int left, int right) {
 // 만약 현재 노드에 lazy 값이 있다면
 if (node.lazy != 0) {
 // 현재노드 업데이트 ( 부모노드이므로 구간 길이만큼 업데이트 )
 node.value += node.lazy * (right - left + 1);
 // 만약 자식이 있다면 자식들에게 lazy 값을 전파한다.
 if (node.leftChild != null) {
 node.leftChild.lazy += node.lazy;
 }
 if (node.rightChild != null) {
 node.rightChild.lazy += node.lazy;
 }
 // lazy 값을 업데이트했으므로 0으로 만들어준다.
 node.lazy = 0;
 }
 }
 // 초기화
 private static void initTree(Node node, int index, long updateValue, int left, int right) {
 // 기저사례 (구간에 index 가 없는 경우)
 if (index < left || index > right)
 return;
 // 기저사례 (마지막 구간에 index 가 있는 경우 (수정할 필요 없는 경우))
 // 초기화 과정이 없기 때문에 필요
 if (left == right) {
 node.value = updateValue;
 return;
 }
 int mid = left + (right - left) / 2;
 long leftSum = 0, rightSum = 0;
 if (index <= mid) {
 if (node.leftChild == null) {
 node.leftChild = getNode();
 }
 initTree(node.leftChild, index, updateValue, left, mid);
 } else {
 if (node.rightChild == null) {
 node.rightChild = getNode();
 }
 initTree(node.rightChild, index, updateValue, mid + 1, right);
 }
 if (node.leftChild != null)
 leftSum = node.leftChild.value;
 if (node.rightChild != null)
 rightSum = node.rightChild.value;
 node.value = leftSum + rightSum;
 }
 private static void updateRange(Node node, long updateValue, int updateStart, int updateEnd, int left, int right) {
 // 기저사례 (구간에 쿼리구간이 없는 경우)
 if (updateEnd < left || updateStart > right)
 return;
 updateLazy(node, left, right);
 // 기저사례 (업데이트 구간이 완전히 포함되는 경우)
 if (updateEnd >= right && updateStart <= left) {
 node.value += (updateValue * (right - left + 1));
 if (node.leftChild != null) {
 node.leftChild.lazy += updateValue;
 }
 if (node.rightChild != null) {
 node.rightChild.lazy += updateValue;
 }
 return;
 }
 int mid = left + (right - left) / 2;
 updateRange(node.leftChild, updateValue, updateStart, updateEnd, left, mid);
 updateRange(node.rightChild, updateValue, updateStart, updateEnd, mid + 1, right);
 node.value = node.leftChild.value + node.rightChild.value;
 }
 static long query(Node node, int queryStart, int queryEnd, int left, int right) {
 // 기저사례 (할당되지 않은 경우)
 if (node == null)
 return 0;
 // 기저사례 (구간에 쿼리구간이 없는 경우)
 if (queryEnd < left || queryStart > right)
 return 0;
 updateLazy(node, left, right);
 // 기저사례 (쿼리 구간이 완전히 포함되는 경우)
 if (queryEnd >= right && queryStart <= left) {
 return node.value;
 }
 int mid = left + (right - left) / 2;
 return query(node.leftChild, queryStart, queryEnd, left, mid) + query(node.rightChild, queryStart, queryEnd, mid + 1, right);
 }
 }
 public static void main(String[] args) throws IOException {
 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 StringTokenizer st = new StringTokenizer(br.readLine());
 n = Integer.parseInt(st.nextToken());
 int m = Integer.parseInt(st.nextToken());
 int k = Integer.parseInt(st.nextToken());
 elements = new long[n];
 for(int i=0; i<n; i++) {
 elements[i] = Long.parseLong(br.readLine());
 }
 SegmentTree.Node root = new SegmentTree.Node();
 for (int i=0; i<elements.length; i++)
 SegmentTree.initTree(root, i+1, elements[i], 1, n);
 for(int i=0; i<m+k; i++) {
 st = new StringTokenizer(br.readLine());
 int operation = Integer.parseInt(st.nextToken());
 int left = Integer.parseInt(st.nextToken());
 int right = Integer.parseInt(st.nextToken());
 if(operation == 1) {
 long updateValue = Long.parseLong(st.nextToken());
 SegmentTree.updateRange(root, updateValue, left, right, 1, n);
 }else {
 bw.write(SegmentTree.query(root, left, right, 1, n)+"\n");
 }
 }
 bw.flush();
 bw.close();
 }
}

nahwasa 3년 전 4

반례입니다.

5 6 4
-12
-10
14
0
-6
1 4 5 3
2 1 3
1 1 4 -4
1 3 3 0
1 1 2 4
2 1 5
1 2 5 2
2 2 2
1 5 5 -4
2 5 5
expected output : 
-8
-16
-8
-5
output : 
-8
-19
-8
-5
------
5 2 1
23
-37
48
-37
27
1 3 5 -5
1 3 4 0
2 2 5
expected output : 
-14
output : 
-9
------
5 3 1
22
-40
17
-32
-8
1 2 5 1
1 2 4 3
1 4 5 2
2 2 5
expected output : 
-46
output : 
-47

zzzzzz 3년 전 3

updateLazy 를 기저사례 뒤에 배치해서 틀렸었습니다.

반례를 생각해보다가 부모 노드가 lazy 가 있는 상태에서 자식 노드가 범위를 벗어났다면 lazy 값을 전파받지 못 하고 잘못된 값으로 계산하는 경우도 존재할 수 있다고 생각을 하게 되었습니다.

제 블로그인 [알고리즘] Segment Tree :: 골드에그 (tistory.com) 에 기재하였습니다. 위 반례가 아닐 경우에 답글 달아주시면 감사하겠습니다.

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

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC