[백준] 15782 Calculate! 2

IUPC 기출 문제다

세그먼트트리 + lazy를 쓰는문제

한가지 걸리는게 있다면 트리를 세그먼트트리로 바꿔야 한다는 것..!

말로만 들었지 해본적이 없어서 찾아서 공부하며 풀어봤다

후위순회를 돌리고 (내위치-자식수) ~ 내위치 로 구간을 정해주면 된다!

그럼 자식들 모두 업데이트를 시켜줄 수 있다

그것만 한다면 기본적인 lazy문제로 바뀐다!

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
vector<vector<int>> Graph;
int cost[100010], numChild[100010], numbering[100010];
int p[100010], cnt;
bool check[100010];
int init_seg_data(int pos) {
    check[pos] = true;
    int c = 0;
    for (int next : Graph[pos]) {
        if (!check[next]) c += init_seg_data(next);
    }
    p[cnt] = cost[pos];
    numbering[pos] = cnt++;
    numChild[pos] = c;
    return c + 1;
}
 
void init(vector<int>&tree, int node, int start, int end) {
    if (start == end) {
        tree[node] = p[start]; return;
    }
    init(tree, node * 2, start, (start + end) / 2);
    init(tree, node * 2 + 1, (start + end) / 2 + 1, end);
    tree[node] = tree[node * 2] ^ tree[node * 2 + 1];
}
 
void update_lazy(vector<int>&tree, vector<int>&lazy, int node, int start, int end) {
    if (lazy[node]) {
        if ((end - start + 1) & 1) tree[node] ^= lazy[node];
        if (start != end) {
            lazy[node * 2] ^= lazy[node];
            lazy[node * 2 + 1] ^= lazy[node];
        }
        lazy[node] = 0;
    }
}
 
void update_range(vector<int>&tree, vector<int>&lazy, int node, int start, int end, int i, int j,int val) {
    update_lazy(tree, lazy, node, start, end);
    if (i > end || j < start) return;
    if (i <= start && end <= j) {
        if ((end - start + 1) & 1) tree[node] ^= val;
        if (start != end) {
            lazy[node * 2] ^= val;
            lazy[node * 2 + 1] ^= val;
        }
        return;
    }
    update_range(tree, lazy, node * 2, start, (start + end) / 2, i, j, val);
    update_range(tree, lazy, node * 2 + 1, (start + end) / 2 + 1, end, i, j, val);
    tree[node] = tree[node * 2] ^ tree[node * 2 + 1];
}
 
int query(vector<int>&tree, vector<int>&lazy, int node, int start, int end, int i, int j) {
    update_lazy(tree, lazy, node, start, end);
    if (i > end || j < start)return 0;
    if (i <= start && end <= j) return tree[node];
    return query(tree, lazy, node * 2, start, (start + end) / 2, i, j) ^ query(tree, lazy, node * 2 + 1, (start + end) / 2 + 1, end,i, j);
}
int main() {
    int n, m; scanf(" %d %d", &n, &m);
    Graph.resize(n);
    int h = (int)ceil(log2(n + 1));
    int tree_size = (1 << (h + 1));
    vector<int> tree(tree_size), lazy(tree_size);
    for (int i = 0; i < n-1; i++) {
        int u, v; scanf(" %d %d", &u, &v);
        u--; v--;
        Graph[u].push_back(v);
        Graph[v].push_back(u);
    }
    for (int i = 0; i < n; i++) scanf(" %d", &cost[i]);
    init_seg_data(0);
    init(tree, 1, 0, n - 1);
    for (int i = 0; i < m; i++) {
        int x; scanf(" %d", &x);
        if (x == 1) {
            int pos; scanf(" %d", &pos); pos--;
            printf("%d\n", query(tree, lazy, 1, 0, n - 1, numbering[pos] - numChild[pos], numbering[pos]));
        }
        else {
            int pos, val; scanf(" %d %d", &pos, &val); pos--;
            update_range(tree, lazy, 1, 0, n - 1, numbering[pos] - numChild[pos], numbering[pos], val);
        }
    }
}