fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <cmath>
  5.  
  6. using namespace std;
  7.  
  8. // .first = 홀수의 개수
  9. // .second = 짝수의 개수
  10.  
  11. pair<int, int> init(vector<int>& arr, vector<pair<int, int>>& tree, int node, int start, int end) {
  12.  
  13.    if (start == end) {
  14.       if (arr[start] % 2)// 홀수
  15.          return tree[node] = make_pair(1, 0);
  16.       else // 짝수
  17.          return tree[node] = make_pair(0, 1);
  18.    }
  19.  
  20.    int mid = (start + end) / 2;
  21.  
  22.    pair<int, int> left = init(arr, tree, node * 2, start, mid);
  23.    pair<int, int> right = init(arr, tree, node * 2 + 1, mid + 1, end);
  24.  
  25.    return tree[node] = make_pair(left.first + right.first, left.second + right.second);
  26. }
  27.  
  28. pair<int, int> query(vector<pair<int, int>>& tree, int node, int start, int end, int left, int right) {
  29.  
  30.    if (right < start || end < left)
  31.       return make_pair(0, 0);
  32.  
  33.    if (left <= start && end <= right)
  34.       return tree[node];
  35.  
  36.    int mid = (start + end) / 2;
  37.  
  38.    pair<int, int> left_child = query(tree, node * 2, start, mid, left, right);
  39.    pair<int, int> right_child = query(tree, node * 2 + 1, mid + 1, end, left, right);
  40.  
  41.    return make_pair(left_child.first + right_child.first, left_child.second + right_child.second);
  42.  
  43. }
  44.  
  45. void update(vector<pair<int, int>>& tree, int node, int start, int end, int index, int val) {
  46.  
  47.    if (index < start || end < index) return;
  48.  
  49.    if (val % 2) { // 홀수개수 증가, 짝수 개수 감소
  50.       tree[node].first++;
  51.       tree[node].second--;
  52.    }
  53.    else { // 홀수개수 감소, 짝수 개수 증가
  54.       tree[node].first--;
  55.       tree[node].second++;
  56.    }
  57.  
  58.    if (start != end) {
  59.       int mid = (start + end) / 2;
  60.       update(tree, node * 2, start, mid, index, val);
  61.       update(tree, node * 2 + 1, mid + 1, end, index, val);
  62.    }
  63. }
  64.  
  65. int main() {
  66.  
  67.    ios::sync_with_stdio(false);
  68.    cin.tie(NULL);
  69.    cout.tie(NULL);
  70.  
  71.    int n; // 수열의 개수
  72.    cin >> n;
  73.    vector<int> arr(n);
  74.  
  75.    for (int i = 0; i < n; i++)
  76.       cin >> arr[i];
  77.  
  78.    // 트리의 크기 결정
  79.    int tree_height = (int)(ceil(log2(n)));
  80.    int tree_size = (1 << (tree_height + 1));
  81.  
  82.    vector<pair<int, int>> tree(tree_size);
  83.  
  84.    // .first = 홀수의 개수
  85.    // .second = 짝수의 개수
  86.  
  87.    init(arr, tree, 1, 0, n - 1);
  88.    int m;   // 쿼리의 개수
  89.    cin >> m;
  90.  
  91.    int mode = 0;
  92.    for (int i = 0; i < m; i++) {
  93.       cin >> mode;
  94.  
  95.       if (mode == 1) { // update
  96.          int index, val;
  97.          cin >> index >> val;
  98.  
  99.          // 짝수 -> 짝수, 홀수 -> 홀수 는 개수 업데이트가 필요x
  100.          if (arr[index - 1] % 2 == val % 2) continue;
  101.  
  102.          update(tree, 1, 0, n - 1, index - 1, val);
  103.       }
  104.  
  105.       else if (mode == 2) { // 범위 내 짝수의 개수 출력
  106.          int left, right;
  107.          cin >> left >> right;
  108.          pair<int, int> res = query(tree, 1, 0, n - 1, left - 1, right - 1);
  109.          cout << res.second << "\n";
  110.       }
  111.  
  112.       else if (mode == 3) { // 범위 내 홀수의 개수 출력
  113.          int left, right;
  114.          cin >> left >> right;
  115.          pair<int, int> res = query(tree, 1, 0, n - 1, left - 1, right - 1);
  116.          cout << res.first << "\n";
  117.  
  118.       }
  119.    }
  120.  
  121.    return 0;
  122. }
Success #stdin #stdout 0s 4292KB
comments (?)
stdin
copy 
6
1 2 3 4 5 6
3
1 2 3
1 2 2
2 1 6
stdout
copy 
2
https://ideone.com/NzMTfr
language:
C++ (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!