(C++) 백준 5676 음주 코딩

문제 및 풀이

https://www.acmicpc.net/problem/5676

구간 곱 구하기(https://velog.io/@minayeah/C-백준-11505-구간-곱-구하기) 문제와 풀이가 동일하다!
다만 여기서는 답의 부호만 판단하면 되므로 값을 0,1,-1 으로 치환해서 입력하면 된다 😊

코드

#include <iostream>
#define ll long long
using namespace std;

const int MAX = 1000000;
int N,K,x;
ll arr[MAX];
ll tree[MAX*4];
char command; int a,b;


int makeTree(int start, int end, int index){
    if(start==end) return tree[index] = arr[start];

    int mid = (start+end)/2;

    return tree[index] = makeTree(start, mid, index*2)
                         *makeTree(mid+1, end, index*2+1);
}


int findTree(int left, int right, int start, int end, int index){

    if(right<start || end<left) return 1;
    if(left<=start && end<=right) return tree[index];
    int mid = (start+end)/2;

    return findTree(left, right, start, mid, index*2)*
           findTree(left, right, mid+1, end, index*2+1);

}

int update(int start, int end, int change, int index, ll val){

    if(change<start || end<change) return tree[index] ;
    if(start==end) return tree[index] = val;

    int mid = (start+end)/2;

    return tree[index] = update(start, mid, change, index*2, val)
                         *update(mid+1, end, change, index*2+1, val);
}



int main(){

    ios_base::sync_with_stdio(0), cin.tie(0);

    auto &is = std::cin;

    while(is >> N >> K){

        fill(arr, arr+MAX, 0);
        fill(tree, tree+4*MAX, 0);

        for(int i=1; i<=N; i++) {
            cin>>x;
            if(x>0) arr[i]=1; else if(x<0) arr[i]=-1; else arr[i]=0;
            arr[i]=x;
            if(x!=0) arr[i]/=abs(x);
        }
        makeTree(1, N, 1);

        for(int round=0; round<K; round++){
            cin>>command>>a>>b;

            if(command=='P') {
                int tmp = findTree(a, b, 1, N, 1);
                if(tmp ==0) cout<<"0";
                else tmp>0 ? cout<<"+" : cout<<"-";
            }
            else if(command=='C') {
                if(b!=0) b>0 ? b=1 : b=-1;
                arr[a]=b;
                update(1, N, a, 1, (ll)b);
                //makeTree(1, N, 1);
            }

        }

        cout<<'\n';
    }



}