結果

問題 No.1641 Tree Xor Query
ユーザー KKT89
提出日時 2021-08-06 21:52:47
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 96 ms / 5,000 ms
コード長 3,233 bytes
コンパイル時間 3,247 ms
コンパイル使用メモリ 225,944 KB
最終ジャッジ日時 2025-01-23 15:10:22
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long ull;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
    return (ull)rng() % B;
}

// from https://yukicoder.me/submissions/552273
template<class Operator> class SegmentTree {
    using TypeNode = typename Operator::TypeNode; 
    size_t length;
    size_t num;
    vector<TypeNode> node;
    vector<pair<size_t,size_t>> range;
    inline void init() {
        for (int i = length - 1; i >= 0; --i) node[i] = Operator::func_node(node[(i<<1)+0],node[(i<<1)+1]);
        range.resize(2 * length);
        for (int i = 0; i < length; ++i) range[i+length] = make_pair(i,i+1);
        for (int i = length - 1; i >= 0; --i) range[i] = make_pair(range[(i<<1)+0].first,range[(i<<1)+1].second);
    }
public:

    //vectorで初期化
    SegmentTree(const vector<TypeNode> & vec) : num(vec.size()) {
        for (length = 1; length <= vec.size(); length *= 2);
        node.resize(2 * length, Operator::unit_node);
        for (int i = 0; i < vec.size(); ++i) node[i + length] = vec[i];
        init();
    }
     
    //[idx,idx+1)
    void update(size_t idx, const TypeNode var) {
        if(idx < 0 || length <= idx) return;
        idx += length;
        // node[idx] = Operator::func_merge(node[idx],var);
        node[idx] ^= var;
        while(idx >>= 1) node[idx] = Operator::func_node(node[(idx<<1)+0],node[(idx<<1)+1]);
    }

    //[l,r)
    TypeNode get(int l, int r) {
        if (l < 0 || length <= l || r < 0 || length < r) return Operator::unit_node;
        TypeNode vl = Operator::unit_node, vr = Operator::unit_node;
        for(l += length, r += length; l < r; l >>=1, r >>=1) {
            if(l&1) vl = Operator::func_node(vl,node[l++]);
            if(r&1) vr = Operator::func_node(node[--r],vr);
        }
        return Operator::func_node(vl,vr);
    }
};

template<class T> struct NodeXorPointUpdate {
    using TypeNode = T;
    inline static constexpr TypeNode unit_node = 0;
    static constexpr TypeNode func_node(TypeNode l,TypeNode r){return (l^r);}
    static constexpr TypeNode func_merge(TypeNode l,TypeNode r){return r;}
    static constexpr bool func_check(TypeNode nodeVal,TypeNode var){return var == nodeVal;}
};

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    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=1;i<n;i++){
        int x,y; cin >> x >> y;
        x--; y--;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    vector<int> v;
    vector<pair<int,int>> sg(n);
    auto dfs=[&](auto dfs,int s,int p)->void{
        sg[s].first=v.size();
        v.push_back(C[s]);
        for(int t:g[s]){
            if(t==p)continue;
            dfs(dfs,t,s);
        }
        sg[s].second=v.size();
    };
    dfs(dfs,0,-1);
    SegmentTree<NodeXorPointUpdate<int>> seg(v);
    while(q--){
        int t,x,y; cin >> t >> x >> y;
        x--;
        if(t==1){
            seg.update(sg[x].first,y);
        }
        else{
            printf("%d\n",seg.get(sg[x].first,sg[x].second));
        }
    }
}
0