백준 5676번 음주 코딩

문제 링크입니다: https://www.acmicpc.net/problem/5676

백준 11505번 구간 곱 구하기(http://jaimemin.tistory.com/816)와 동일한 문제였습니다.

문제에서는 쿼리의 결과의 부호만 궁금해하기 때문에 오버플로우를 방지하기 위해 배열을 입력 받을 때 양수면 1, 0이면 0, 음수면 -1을 입력해주면 됩니다.

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

 

struct segmentTree

{

        //배열의 길이

        int n;

        //각 구간의 부분곱

        vector<long long> pMult;

        segmentTree(const vector<long long> &array)

        {

                 n = array.size();

                 pMult.resize(n * 4);

                 init(array, 0, n - 1, 1);

        }

        //node 노드가 array[left..right]배열을 표현

        //node를 루트로 하는 서브트리 초기화

        long long init(const vector<long long> &array, int left, int right, int node)

        {

                 if (left == right)

                         return pMult[node] = array[left];

 

                 int mid = (left + right) / 2;

                 long long leftSubTree = init(array, left, mid, node * 2);

                 long long rightSubTree = init(array, mid + 1, right, node * 2 + 1);

 

                 return pMult[node] = (leftSubTree*rightSubTree);

        }

        //node가 표현하는 범위 array[nodeLeft..nodeRight]가 주어질 때

        //이 범위와 array[left..right]의 교집합

        long long query(int left, int right, int node, int nodeLeft, int nodeRight)

        {

                 //두 구간이 겹치지 않으면 무시

                 if (right < nodeLeft || nodeRight < left)

                         return 1;

                 //node가 표현하는 범위가 array[left..right]에 완전히 포함

                 if (left <= nodeLeft && nodeRight <= right)

                         return pMult[node];

                 //양쪽 구간을 나눠서 풀고 결과를 합친다

                 int mid = (nodeLeft + nodeRight) / 2;

                 return query(left, right, node * 2, nodeLeft, mid)*query(left, right, node * 2 + 1, mid + 1, nodeRight);

        }

        long long query(int left, int right)

        {

                 return query(left - 1, right - 1, 1, 0, n - 1);

        }

        //array[index]=newValue로 바뀌었을 때 node를 루트로하는 구간트리 갱신

        long long update(int index, int newValue, int node, int nodeLeft, int nodeRight)

        {

                 if (index < nodeLeft || nodeRight < index)

                         return pMult[node];

                 if (nodeLeft == nodeRight)

                         return pMult[node] = newValue;

 

                 int mid = (nodeLeft + nodeRight) / 2;

                 return pMult[node] = update(index, newValue, node * 2, nodeLeft, mid)*update(index, newValue, node * 2 + 1, mid + 1, nodeRight);

        }

        long long update(int index, int newValue)

        {

                 return update(index - 1, newValue, 1, 0, n - 1);

        }

};

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        int N, K;

 

        while(cin >> N)

        {

                 cin >> K;

                

                 vector<long long> v(N);

                 for (int i = 0; i < N; i++)

                 {

                         int temp;

                         cin >> temp;

 

                         if (temp > 0)

                                 v[i] = 1;

                         else if (temp == 0)

                                 v[i] = 0;

                         else

                                 v[i] = -1;

                 }

 

                 segmentTree seg(v);

                 for (int i = 0; i < K; i++)

                 {

                         char op;

                         int a, b;

                         cin >> op >> a >> b;

 

                         if (op == 'C')

                         {

                                 if (b > 0)

                                 {

                                          seg.update(a, 1);

                                          v[a - 1] = 1;

                                 }

                                 else if (b == 0)

                                 {

                                          seg.update(a, 0);

                                          v[a - 1] = 0;

                                 }

                                 else

                                 {

                                          seg.update(a, -1);

                                          v[a - 1] = -1;

                                 }

                         }

                         else

                         {

                                 long long result = seg.query(a, b);

 

                                 if (result > 0)

                                          cout << '+';

                                 else if (result == 0)

                                          cout << '0';

                                 else

                                          cout << '-';

                         }

                 }

                 cout << "\n";

        }

 

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~