#686655 (C++14) No.1641 Tree Xor Query

• 問題: No.1641 Tree Xor Query
• ユーザー: nawawan
• 提出日時: 2021-08-06 22:11:24
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 331 ms / 5,000 ms
• コード長: 5,595 bytes
• コンパイル時間: 1,942 ms
• コンパイル使用メモリ: 179,268 KB
• 実行使用メモリ: 22,712 KB
• 最終ジャッジ日時: 2024-09-17 02:12:32
• 合計ジャッジ時間: 3,851 ms
• ジャッジサーバーID （参考情報）: judge6 / judge5

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 6,816 KB
testcase_01	AC	2 ms; 6,944 KB
testcase_02	AC	2 ms; 6,944 KB
testcase_03	AC	2 ms; 6,944 KB
testcase_04	AC	2 ms; 6,944 KB
testcase_05	AC	2 ms; 6,944 KB
testcase_06	AC	2 ms; 6,940 KB
testcase_07	AC	2 ms; 6,944 KB
testcase_08	AC	2 ms; 6,940 KB
testcase_09	AC	2 ms; 6,944 KB
testcase_10	AC	2 ms; 6,944 KB
testcase_11	AC	2 ms; 6,944 KB
testcase_12	AC	2 ms; 6,940 KB
testcase_13	AC	331 ms; 22,704 KB
testcase_14	AC	329 ms; 22,712 KB
testcase_15	AC	6 ms; 6,940 KB
testcase_16	AC	19 ms; 6,940 KB
testcase_17	AC	14 ms; 6,940 KB
testcase_18	AC	10 ms; 6,940 KB
testcase_19	AC	10 ms; 6,940 KB
testcase_20	AC	228 ms; 19,500 KB

ソースコード

#include <bits/stdc++.h>
using namespace std;
struct Euler_Tour{
    vector<int> order;
    vector<int> begin, end;
    vector<vector<int>> G;
    Euler_Tour(vector<vector<int>> &g): begin(g.size()), end(g.size()), G(g){}
    Euler_Tour(int N) : begin(N), end(N), G(N) {}
    void add_edge(int u, int v){
        G[u].push_back(v);
        G[v].push_back(u);
    }
    void build(int root = 0){
        int ind = 0;
        dfs(root, ind, -1, G);
    }
    int size(){
        return order.size();
    }
private:
    void dfs(int now, int &ind, int par, vector<vector<int>>&G){
        order.push_back(now);
        begin[now] = ind;
        ++ind;
        for(int e: G[now]){
            if(e != par){
                dfs(e, ind, now, G);
                order.push_back(now);
                ++ind;
            }
        }
        end[now] = ind;
    }
};
template<typename S, S (*XX)(S, S), S (*id)()> struct segment_tree{
private:
    int n;
    int size;//元の配列の大きさ
    vector<S> dat;
    void update_sub(int k){
        dat[k] = XX(dat[k << 1 | 0], dat[k << 1 | 1]);
    }
public:
    segment_tree(int n_) : n(n_ * 2), size(n_){
        dat.resize(n, id());
    }
    segment_tree(vector<S> &v){
        size = (int)v.size();
        n = size * 2;
        dat.resize(n, id());
        for(int i = 0; i < size; ++i) dat[i + size] = v[i];
        for(int i = size - 1; i >= 1; --i){
            update_sub(i);
        }
    }
    S& operator[](const int i){
        return dat[i + size];
    }
    void update(int ind, S a){
        ind += size;
        dat[ind] = a;
        while(ind > 1){
            ind >>= 1;
            dat[ind] = XX(dat[ind << 1 | 0], dat[ind << 1 | 1]);
        }
    }
    S query(int l, int r){
        if(l >= r) return id();
        S vl = id(), vr = id();
        l += size;
        r += size;
        while(r > l){
            if(l & 1) vl = XX(vl, dat[l++]);
            if(r & 1) vr = XX(dat[--r], vr);
            l >>= 1;
            r >>= 1;
        }
        return XX(vl, vr);
    }
    //[l, r)でf(merge(a[l],..., a[r - 1]))がtrueとなる最大のrを返す
    template<typename F>
    int max_right(int l, F f){
        if(l == size) return size;
        stack<int> s;
        queue<int> q;
        l += size;
        int r = n;
        while(r > l){
            if(l & 1) q.push(l++);
            if(r & 1) s.push(--r);
            r >>= 1;
            l >>= 1;
        }
        while(!s.empty()){
            q.push(s.top());
            s.pop();
        }
        S res = id();
        int now = -1;
        while(!q.empty()){
            int v = q.front();
            q.pop();
            S temp = XX(res, dat[v]);
            if(!f(temp)){
                now = v;
                break;
            }
            res = temp;
        }
        if(now == -1) return size;
        while(now < size){
            now <<= 1;
            S temp = XX(res, dat[now]);
            if(f(temp)){
                res = temp;
                ++now;
            }
        }
        return now - size;
    }
    //[l, r)でf(merge(a[l],..., a[r - 1]))がtrueとなる最小のlを返す
    template<typename F>
    int min_left(int r, F f){
        if(r == 0) return 0;
        stack<int> s;
        queue<int> q;
        int l = size;
        r += size;
        while(r > l){
            if(r & 1) q.push(--r);
            if(l & 1) s.push(l++);
            r >>= 1;
            l >>= 1;
        }
        while(!s.empty()){
            q.push(s.top());
            s.pop();
        }
        S res = id();
        int now = -1;
        while(!q.empty()){
            int v = q.front();
            q.pop();
            S temp = XX(res, dat[v]);
            if(!f(temp)){
                now = v;
                break;
            }
            res = temp;
        }
        if(now == -1) return 0;
        while(now < size){
            now <<= 1;
            ++now;
            S temp = XX(res, dat[now]);
            if(f(temp)){
                res = temp;
                --now;
            }
        }
        return now + 1 - size;
    }
    //上から二分探索する用(現コードはMexを求めるようのやつ)
    int lower_bound(int f){
        int now = 0;
        while(now < size){
            if(now == 0) now += size;
            while((now & 1) == 0) now >>= 1;
            if(dat[now] < f){
                while(now < size){
                    int l = now << 1;
                    int r = (now << 1) | 1;
                    if(dat[l] < f) now = l;
                    else now = r;
                }
            }
            else ++now;
        }
        return now - size;
    }
};
int XX(int x, int y){
    return (x ^ y);
}
int id(){
    return 0;
}
int main(){
    int N, Q;
    cin >> N >> Q;
    vector<int> C(N);
    for(int i = 0; i < N; i++) cin >> C[i];
    vector<vector<int>> G(N);
    for(int i = 0; i < N - 1; i++){
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    Euler_Tour et(G);
    et.build();
    vector<int> c(et.size());
    for(int i = 0; i < N; i++){
        c[et.begin[i]] = C[i];
    }
    segment_tree<int, XX, id> seg(c);
    while(Q--){
        int f;
        cin >> f;
        if(f == 1){
            int x, y;
            cin >> x >> y;
            x--;
            C[x] ^= y;
            seg.update(et.begin[x], C[x]);
        }
        else{
            int x, y;
            cin >> x >> y;
            x--;
            cout << seg.query(et.begin[x], et.end[x]) << endl;
        }
    }
}