[C++]음주 코딩[백준 5676]

인덱스 범위가 10만이고 인덱스마다 값의 범위는 -100~100인 배열을 입력으로 주고, 

구간을 갱신, 합산출을 M만큼 해주는건데 K의 범위또한 10만이다. 

(즉, -> Prefix_Sum을 사용하거나 세그먼트를 써야한다는건데 갱신이 있으므로 세그먼트를 썻다.)

시간복잡도는 대략 O(KlogN) 인것 같다. 

구현한 세그먼트는 바텀-업 세그먼트를 사용하였다

처음 풀때 실수 했던게 10만개의 인덱스가 전부 100을 갖고 있을때는 곱셈연산이므로 

100의 10만승이라는 1Googol을 훌쩍 넘어버리는.. 수가 발생한다는 것을 뒤늦게 알고, 

( 참고로 1구골이  10의 100승이다 ) 

세그트리를 구축해주는 함수에서 음, 양, 0을 판별하고 부분곱 방식으로 트리를 쌓아올렸다. 

그래도 실행시간은 나쁘지 않게 나와서 좀 만족스럽다 ㅎㅎㅎ

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

5676번: 음주 코딩

문제 오늘은 ACM-ICPC 대회 전 날이다. 상근이는 긴장을 풀기 위해서 팀원들과 근처 술집으로 갔다. 상근이와 친구들은 다음 날 있을 대회를 연습하기 위해서 작은 게임을 하기로 했다. 먼저, 선영이는 상근이에게 총 N개의 정수로 이루어진 수열 X 1 , X 2 , ... X N 을 적어준다. 게임은 총 K번 라운드로 이루어져있고, 매 라운드마다 선영이는 상근이에게 명령을 하나씩 내린다. 명령은 아래와 같이 두 가지가 있다. 변경: 이 명령은 친구가 수열의 한 값을 바꾸고 싶을 때 사용한다. 곱셈: 선영이는 상근이에게 i와 j를

www.acmicpc.net

<Code>

// pda_pro12
#include<algorithm>
#include<iostream>
#define N_ 100001   // 수열의 최대 크기 
#define INT 0x7fff0000
 
using namespace std; 
 
typedef long long ll; 
int seg[N_ * 4], a[N_], t, n, m, k;
 
void init(int node, int x, int y) {
    if (x == y) {
        if (a[x] > 0) seg[node] = 1; 
        else if (a[x] == 0) seg[node] = 0; 
        else if (a[x] < 0)  seg[node] = -1; 
        return; 
    }
    int mid = (x + y) >> 1; 
    init(node << 1, x, mid); 
    init((node << 1) + 1, mid + 1, y); 
    seg[node] = seg[node << 1] * (seg[(node << 1) + 1]); 
    return; 
}
 
void update(int pos, int val, int node, int x, int y) { 
    if (pos < x || pos > y) return; 
    if (x == y) {
        if (val > 0) seg[node] = 1;
        else if (!val) seg[node] = 0; 
        else if (val < 0) seg[node] = -1; 
        return; 
    }
    int mid = (x + y) >> 1; 
    update(pos, val, node << 1, x, mid); 
    update(pos, val, (node << 1) + 1, mid + 1, y); 
    seg[node] = seg[node << 1] * seg[(node << 1) + 1]; 
    return; 
}
 
int query(int lo, int hi, int node, int x, int y) {
    if (lo > y || x > hi) return 1; 
    if (lo <= x && y <= hi) return seg[node]; 
    int mid = (x + y) >> 1; 
    int l = query(lo, hi, node << 1, x, mid); 
    int r = query(lo, hi, (node << 1) + 1, mid + 1, y); 
    return l*r; 
}
 
int main() {
    ios::sync_with_stdio(false); 
    cin.tie(NULL); 
    cout.tie(NULL); 
    
    while (cin >> n >> m) {
        for (int i = 1; i <= n; i++)
            cin >> a[i]; 
 
        init(1, 1, n); 
        while (m--) {
            char inp; int x, y; 
            cin >> inp >> x >> y;
            if (inp == 'C') 
                update(x, y, 1, 1, n);
            else if (inp == 'P'){
                int ans = query(x, y, 1, 1, n);
                if (ans == 0)
                    cout << '0';
                else if (ans > 0)
                    cout << '+';
                else if ( ans < 0)
                    cout << '-'; 
            }
        }
        cout << '\n'; 
    }
    return 0; 
}