18436 수열과 쿼리 37

구간..! 보고 세그트리인 걸 알았다.

세그트리 예전에 한 번 써보고 안 써봐서 적응하는데 시간이 조금 걸렸다.

아이디어는 생각외로 간단하다. 짝수는 0을 저장하고 홀수는 배열에 1을 저장한다. 

그래서 구간합을 구하는데 홀수면 구간합 자체가 홀수의 개수가 되고

짝수면 구간 - 구간합을 하면 짝수의 개수가 나온다. 

 

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>
#include <stdio.h>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using iis = pair<int, string>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;

constexpr int clog2(int n) { return ((n < 2) ? 1 : 1 + clog2(n / 2)); }

int sum(int a, int b){
    return a + b;
}

template<typename T>
class SegmentTree
{
public:
    template<typename M>
    SegmentTree(const M& m) : merge(m) {}

    void init(const vector<T>& raw_)
    {
        raw = raw_;
        n = (int)raw.size();
        int sz = (1 << (clog2(n) + 1));
        data.resize(sz);

        _init(raw, 1, 0, n - 1);
    }

    T modify(int idx, function<T(T)> modifier) { return update(idx, modifier(raw[idx])); }
    T update(int idx, const T& newVal) { raw[idx] = newVal; return _update(1, 0, n - 1, idx, newVal); }
    T query(int left, int right) { return _query(1, 0, n - 1, left, right); }

private:
    vector<T> raw;
    vector<T> data;
    int n;
    using Merge = function<T(const T&, const T&)>;
    Merge merge;

    T _init(const vector<T>& raw, int node, int start, int end)
    {
        int mid = (start + end) / 2;
        if (start == end)
            return data[node] = raw[start];
        else
            return data[node] = merge(_init(raw, node * 2, start, mid),
                _init(raw, node * 2 + 1, mid + 1, end));
    }

    T _update(int node, int start, int end, int index, const T& newVal)
    {
        if (index < start || index > end)
            return data[node];

        if (start == end)
            data[node] = newVal;
        else
        {
            int mid = (start + end) / 2;
            data[node] = merge(_update(node * 2, start, mid, index, newVal),
                _update(node * 2 + 1, mid + 1, end, index, newVal));
        }

        return data[node];
    }

    T _query(int node, int start, int end, int left, int right)
    {
        if (left <= start && end <= right)
            return data[node];

        int mid = (start + end) / 2;

        if (mid < left)
            return _query(node * 2 + 1, mid + 1, end, left, right);

        if (mid + 1 > right)
            return _query(node * 2, start, mid, left, right);

        return merge(_query(node * 2, start, mid, left, right),
            _query(node * 2 + 1, mid + 1, end, left, right));
    }
};

int main() {
    auto tree = SegmentTree<int>([](int l, int r) { return l + r; });
    int n, q;
    scanf("%d", &n);
    
    vector<int> v(n);
    for (int i = 0; i < n; i++) {
        int tmp;
        scanf("%d", &tmp);
        
        v[i] = tmp % 2;
    }
    tree.init(v);
    
    scanf("%d", &q);
    for (int i = 0; i < q; i++) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        
        if (a == 1) {
            c %= 2;
            tree.update(b - 1, c);
            continue;
        }
        
        int numOfOdd = tree.query(b - 1, c - 1);
        if (a == 2)
            printf("%d\n", c - b + 1 - numOfOdd); 
        else
            printf("%d\n", numOfOdd); 
    }
    
    
    return 0;
}