백준 5676번 음주 코딩 - C++(cpp) 풀이

---

 

1. 구간 내 음수의 개수를 저장하는 세그먼트 트리와 0의 개수를 저장하는 세그먼트 트리를 둔다.
2. 주어진 쿼리의 구간에 0이 하나도 없는 경우, 음수의 개수가 홀수개이면 결과값도 음수, 짝수개이면 양수이다.
3. 주어진 쿼리의 구간에 0이 한 개 이상 있는 경우, 결과값은 0이다.

 

1. 구간 내 음수의 개수를 저장하는 세그먼트 트리와 0의 개수를 저장하는 세그먼트 트리를 둔다.

 값의 변경이 계속 이루어지는 상황에서 구간에 대한 쿼리를 수행해야 하므로 세그먼트 트리를 이용하여 해결할 수 있다. 구간곱이 양수인지, 음수인지, 0인지만 알면 되기 때문에 음수의 개수, 0의 개수를 기록하는 두 개의 세그먼트 트리를 만들어준다.

 

2. 주어진 쿼리의 구간에 0이 하나도 없는 경우, 음수의 개수가 홀수개이면 결과값도 음수, 짝수개이면 양수이다.

 주어진 쿼리의 구간에 0이 하나도 없는 경우에는, 구간 내 음수의 개수가 결과값의 부호를 결정한다. 구간 내 음수가 홀수개이면 결과값이 음수가 되고, 반대로 짝수개이면 양수가 된다.

 

3. 주어진 쿼리의 구간에 0이 한 개 이상 있는 경우, 결과값은 0이다.

 주어진 쿼리의 구간에 0이 한 개라도 있으면, 결과값은 0이다.

반응형

---

#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;

struct Segtree {
    int n;
    vector<ll> negative, zero;
    vector<ll> A;
    
    Segtree (vector<ll>& X) {
        A = X;
        n = A.size();
        negative.resize(n*4);
        zero.resize(n*4);
        init(0, n-1, 1);
    }
    
    void init(int left, int right, int node) {
        if (left == right) {
            negative[node] = (A[left] < 0) ? 1 : 0;
            zero[node] = (A[left] == 0) ? 1 : 0;
            return;
        }
        
        int mid = (left+right)/2;
        init(left, mid, node*2);
        init(mid+1, right, node*2+1);
        negative[node] = negative[node*2] + negative[node*2+1];
        zero[node] = zero[node*2] + zero[node*2+1];
    }
    
    ll query(int left, int right, int node, int nodeLeft, int nodeRight, bool zeroSum) {
        if (nodeRight < left || nodeLeft > right) return 0;
        if (left <= nodeLeft && nodeRight <= right) {
            if (zeroSum) return zero[node];
            else return negative[node];
        }
        
        int mid = (nodeLeft+nodeRight)/2;
        ll l = query(left, right, node*2, nodeLeft, mid, zeroSum);
        ll r = query(left, right, node*2+1, mid+1, nodeRight, zeroSum);
        return l+r;
    }
    
    char query(int left, int right) {
        ll negativeCnt = query(left, right, 1, 0, n-1, false);
        ll zeroCnt = query(left, right, 1, 0, n-1, true);
        
        if (zeroCnt > 0) return '0';
        else return (negativeCnt % 2) ? '-' : '+';
    }
    
    void update(int idx, ll val, int node, int nodeLeft, int nodeRight) {
        if (idx < nodeLeft || idx > nodeRight) return;
        
        if (A[idx] == 0 && val != 0) zero[node]--;
        else if (A[idx] != 0 && val == 0) zero[node]++;
        if (A[idx] < 0 && val >= 0) negative[node]--;
        else if (A[idx] >= 0 && val < 0) negative[node]++;
        
        if (nodeLeft == nodeRight) return;
        
        int mid = (nodeLeft+nodeRight)/2;
        update(idx, val, node*2, nodeLeft, mid);
        update(idx, val, node*2+1, mid+1, nodeRight);
    }
    
    void update(int idx, ll val) {
        update(idx, val, 1, 0, n-1);
        A[idx] = val;
    }
};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    int N, K;
    
    while (cin >> N >> K) {
        vector<ll> X(N);
        for (int i=0; i<N; i++) cin >> X[i];
        
        Segtree ST(X);
        
        char t;
        ll a, b;
        for (int i=0; i<K; i++) {
            cin >> t >> a >> b;
            if (t == 'C') ST.update(a-1, b);
            else cout << ST.query(a-1, b-1);
        }
        cout << "\n";
    }
    
    return 0;
}