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

 

5676번: 음주 코딩

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

www.acmicpc.net

세그먼트 트리에서 

음수의 갯수( 짝수 -> 양수, 홀수 -> 음수 )

0의 존재여부( 하나라도 존재한다면 0 )

의 파악이 핵심인 문제이다. "V =100" 인 숫자를 곱하다보면 금방 long long 범위에도 담기지 않기 때문이다.

#include <iostream>
#include <cstring>
using namespace std;
 
#define MAX_N 100001
 
// { 음수의갯수, 0의 존재여부 }
pair<int,bool> tree[MAX_N * 4];
 
void update_tree(int now, int target, int start, int end, int value) {
     if (target > end || target < start) return;
     if (start == end) {
          if (value == 0) 
              tree[now] = { 0,true };
          else if (value < 0) 
             tree[now] = { 1,false };
          else 
              tree[now] = { 0, false };
          return;
     }
     int mid = (start + end) / 2;
     update_tree(now * 2, target, start, mid, value);
     update_tree(now * 2 + 1, target, mid + 1, end, value);
 
     tree[now].first = tree[now * 2].first + tree[now * 2 + 1].first;
     (tree[now * 2].second || tree[now * 2 + 1].second)? tree[now].second = true : tree[now].second = false;
}
 
pair<int, bool> query(int now, int left, int right, int start, int end) {
     if (left > end || right < start) return {0,false};
     if (left <= start && end <= right) {
          return tree[now];
     }
     int mid = (start + end) / 2;
     pair<int, bool> ret = { 0,false };
     pair<int, bool> left_ret = query(now * 2, left,right, start, mid);
     pair<int, bool> right_ret = query(now * 2 + 1, left, right, mid + 1, end);
     ret.first = left_ret.first + right_ret.first;
     (left_ret.second == true || right_ret.second == true)?ret.second = true: ret.second = false;
     return ret;
}
 
int main() {
     ios::sync_with_stdio(false);
     cin.tie(0);
     cout.tie(0);
     int N, K;
     while (cin >> N >> K) {
          for (int i = 0; i <= 4 * N; i++) {
               tree[i].first = 0;
               tree[i].second = false;
          }
          for (int i = 0; i < N; i++) {
               int data; cin >> data;
               update_tree(1, i, 0, N - 1, data);
          }
          for (int i = 0; i < K; i++) {
               char tag; cin >> tag;
               if (tag == 'C') {
                    int a, b; cin >> a >> b;
                    update_tree(1, a - 1, 0, N - 1, b);
               }
               else {
                    int a, b; cin >> a >> b;
                    pair<int, bool> ret = query(1, a - 1, b - 1, 0, N - 1);
                    if (ret.second) cout << "0";
                    else {
                         if (ret.first % 2 == 1) cout << "-";
                         else cout << "+";
                    }
               }
          }
          cout << "\n";
     }
}
저작자표시

'알고리즘 > [C++]BOJ' 카테고리의 다른 글

[백준] 3392_화성지도 (C++)  (0) 2019.09.30
[BOJ]7469_K번째 수(C++)  (0) 2019.09.30
[백준]1275_커피숍2(C++)  (0) 2019.09.29

+ Recent posts

티스토리툴바