5676 음주 코딩 (파이썬)

문제

오늘은 ACM-ICPC 대회 전 날이다. 상근이는 긴장을 풀기 위해서 팀원들과 근처 술집으로 갔다.

상근이와 친구들은 다음 날 있을 대회를 연습하기 위해서 작은 게임을 하기로 했다.

먼저, 선영이는 상근이에게 총 N개의 정수로 이루어진 수열 X1, X2, ... XN을 적어준다. 게임은 총 K번 라운드로 이루어져있고, 매 라운드마다 선영이는 상근이에게 명령을 하나씩 내린다. 명령은 아래와 같이 두 가지가 있다.

• 변경: 이 명령은 친구가 수열의 한 값을 바꾸고 싶을 때 사용한다.
• 곱셈: 선영이는 상근이에게 i와 j를 말한다. 상근이는 Xi × Xi+1 × ... × Xj-1 × Xj 의 값이 양수인지, 음수인지, 0인지를 대답한다.

곱셈 명령에서 상근이가 대답을 잘못했을 때의 벌칙은 소주 한 잔이다. 상근이는 갑자기 대회가 걱정되기 시작했다. 또, 상근이는 발머의 피크 이론을 증명하고 싶지 않다.

다행히 선영이는 상근이에게 노트북 사용을 허락했다. 상근이는 자신의 수학 실력보다 코딩 실력을 더 믿는다.

상근이를 돕는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스의 첫째 줄에는 수열의 크기 N과 게임의 라운드 수 K가 주어진다. (1 ≤ N, K ≤ 105)

둘째 줄에는 총 N개의 숫자 Xi가 주어진다. (-100 ≤ Xi ≤ 100)

다음 K개 줄에는 선영이가 내린 명령이 주어진다. 명령은 C 또는 P로 시작한다.

C로 시작하는 명령은 변경 명령이고, 그 다음에 i와 V가 주어진다. Xi를 V로 변경하는 명령이다. (1 ≤ i ≤ N, -100 ≤ V ≤ 100)

P로 시작하는 명령은 곱셈 명령이고, 그 다음에 i와 j가 주어진다. (1 ≤ i ≤ j ≤ N)

각 테스트 케이스에 곱셈 명령은 항상 한 번 이상있다.

출력

각 테스트 케이스마다 곱셈 명령의 결과를 한 줄에 모두 출력하면 된다. 출력하는 i번째 문자는 i번째 곱셈 명령의 결과이다. 양수인 경우에는 +, 음수인 경우에는 -, 영인 경우에는 0을 출력한다.

 

=====

문제 풀이

세그먼트 트리를 통해 각 인덱스의 범위내의 곱들의 부호를 저장한다.

이때 배열 인덱스의 세그먼트 트리에 저장되어 있는 노드 포인트 또한 기록해둔다.

이후 문자열 C를 만나면 인덱스의 부호가 기존과 반대라면 그 인덱스의 노드 포인트부터 시작하여 루트까지 부호를 반대로 수정해준다.

우선 세그먼트 초기화 하는 방법은 아래와 같다.

자연수는 1로 기록하고 음수는 -1로 기록할 것이다. ( 0또한 자연수로 지정하여 일단은 +인 1을 기록) 

만약 0이라면 zeroIndexSet에 저장하여 P로 출력할 때 그 범위 내에 zero가 하나라도 있다면 0 출력하기 위함

const nodePointOfArrayIndex = {};

    const segmentTree = [undefined];

    const signOfIndex = (index) => {
        return arr[index] >= 0 ? 1 : -1;
    };
    const zeroIndexSet = new Set();

    const initSegmentTree = (leftIndex, rightIndex, nodePoint) => {
        if (leftIndex > rightIndex) return 1;
        if (leftIndex === rightIndex) {
            if (arr[leftIndex] === 0) {
                zeroIndexSet.add(leftIndex);
            }
            const sign = signOfIndex(leftIndex);
            segmentTree[nodePoint] = sign;
            nodePointOfArrayIndex[leftIndex] = {
                nodePoint,
                sign,
            };

            return sign;
        }
        const mid = Math.floor((leftIndex + rightIndex) / 2);

        const leftNode = initSegmentTree(leftIndex, mid, nodePoint * 2);
        const rightNode = initSegmentTree(
            mid + 1,
            rightIndex,
            nodePoint * 2 + 1
        );
        const sign = leftNode * rightNode;
        segmentTree[nodePoint] = sign;
        return sign;
    };

범위 내 부호를 출력하는 함수

const calculateSignOfRange = (
        startRange,
        endRange,
        leftIndex,
        rightIndex,
        nodePoint
    ) => {
        if (leftIndex > endRange || rightIndex < startRange) return 1;
        if (startRange <= leftIndex && endRange >= rightIndex) {
            return segmentTree[nodePoint];
        }
        const mid = Math.floor((leftIndex + rightIndex) / 2);
        const leftSign = calculateSignOfRange(
            startRange,
            endRange,
            leftIndex,
            mid,
            nodePoint * 2
        );
        const rightSign = calculateSignOfRange(
            startRange,
            endRange,
            mid + 1,
            rightIndex,
            nodePoint * 2 + 1
        );

        return leftSign * rightSign;
    };

리프 노드부터 시작하여 루트까지 타고 올라가면서 부호를 반대로 수정해주는 함수

const reverseTree = (idx) => {
        segmentTree[idx] = segmentTree[idx] === 1 ? -1 : 1;
    };
    const changeTree = (nodePoint) => {
        if (nodePoint === 1) {
            reverseTree(1);
            return;
        }
        reverseTree(nodePoint);
        const parent = Math.floor(nodePoint / 2);
        changeTree(parent);
};

정답 코드

const input = require('fs')
    .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
    .toString()
    .trim()
    .split('\n');

const answers = [];

while (input.length) {
    const [n, m] = input.shift().split(' ').map(Number);
    const arr = input.shift().split(' ').map(Number);

    const nodePointOfArrayIndex = {};

    const segmentTree = [undefined];

    const signOfIndex = (index) => {
        return arr[index] >= 0 ? 1 : -1;
    };
    const zeroIndexSet = new Set();

    const initSegmentTree = (leftIndex, rightIndex, nodePoint) => {
        if (leftIndex > rightIndex) return 1;
        if (leftIndex === rightIndex) {
            if (arr[leftIndex] === 0) {
                zeroIndexSet.add(leftIndex);
            }
            const sign = signOfIndex(leftIndex);
            segmentTree[nodePoint] = sign;
            nodePointOfArrayIndex[leftIndex] = {
                nodePoint,
                sign,
            };

            return sign;
        }
        const mid = Math.floor((leftIndex + rightIndex) / 2);

        const leftNode = initSegmentTree(leftIndex, mid, nodePoint * 2);
        const rightNode = initSegmentTree(
            mid + 1,
            rightIndex,
            nodePoint * 2 + 1
        );
        const sign = leftNode * rightNode;
        segmentTree[nodePoint] = sign;
        return sign;
    };

    const calculateSignOfRange = (
        startRange,
        endRange,
        leftIndex,
        rightIndex,
        nodePoint
    ) => {
        if (leftIndex > endRange || rightIndex < startRange) return 1;
        if (startRange <= leftIndex && endRange >= rightIndex) {
            return segmentTree[nodePoint];
        }
        const mid = Math.floor((leftIndex + rightIndex) / 2);
        const leftSign = calculateSignOfRange(
            startRange,
            endRange,
            leftIndex,
            mid,
            nodePoint * 2
        );
        const rightSign = calculateSignOfRange(
            startRange,
            endRange,
            mid + 1,
            rightIndex,
            nodePoint * 2 + 1
        );

        return leftSign * rightSign;
    };

    initSegmentTree(0, n - 1, 1);

    const controls = input.splice(0, m).map((s) => {
        const [control, a, b] = s.split(' ');
        if (control === 'C') {
            return [control, +a - 1, +b];
        }
        return [control, +a - 1, +b - 1];
    });

    const answer = [];
    const reverseTree = (idx) => {
        segmentTree[idx] = segmentTree[idx] === 1 ? -1 : 1;
    };
    const changeTree = (nodePoint) => {
        if (nodePoint === 1) {
            reverseTree(1);
            return;
        }
        reverseTree(nodePoint);
        const parent = Math.floor(nodePoint / 2);
        changeTree(parent);
    };
    for (const [ctl, a, b] of controls) {
        if (ctl === 'C') {
            if (zeroIndexSet.has(a) && b !== 0) {
                zeroIndexSet.delete(a);
            }
            if (b === 0) {
                zeroIndexSet.add(a);
            }
            const { nodePoint, sign: originalSign } = nodePointOfArrayIndex[a];
            const chageSign = b >= 0 ? 1 : -1;

            if (chageSign === originalSign) {
                continue;
            }
            nodePointOfArrayIndex[a].originalSign = chageSign;
            changeTree(nodePoint);
        } else {
            let isHasZero = false;
            for (let i = a; i <= b; i++) {
                if (zeroIndexSet.has(i)) {
                    answer.push(0);
                    isHasZero = true;
                    break;
                }
            }
            if (isHasZero) {
                continue;
            }
            const result = calculateSignOfRange(a, b, 0, n - 1, 1);

            answer.push(result);
        }
    }

    const temp = answer
        .map((v) => {
            if (v === 0) {
                return 0;
            }
            if (v === 1) {
                return '+';
            }
            return '-';
        })
        .join('');
    answers.push(temp);
}

console.log(answers.join('\n'));

 

 

const reversetree = (idx) => {
segmentTree [idx] = segmentTree [idx] === 1? -1 : 1;
};
const changetree = (nodepoint) => {
if (nodepoint === 1) {
Reversetree (1);
반품;
}
Reversetree (NodePoint);
const parent = math.floor (nodepoint / 2);
Changetree (부모);
};