結果

問題 No.1641 Tree Xor Query
ユーザー KKT89KKT89
提出日時 2021-08-06 21:52:47
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 92 ms / 5,000 ms
コード長 3,233 bytes
コンパイル時間 3,302 ms
コンパイル使用メモリ 227,824 KB
実行使用メモリ 20,292 KB
最終ジャッジ日時 2023-10-17 03:13:41
合計ジャッジ時間 4,679 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,348 KB
testcase_01 AC 2 ms
4,348 KB
testcase_02 AC 2 ms
4,348 KB
testcase_03 AC 2 ms
4,348 KB
testcase_04 AC 2 ms
4,348 KB
testcase_05 AC 2 ms
4,348 KB
testcase_06 AC 2 ms
4,348 KB
testcase_07 AC 2 ms
4,348 KB
testcase_08 AC 2 ms
4,348 KB
testcase_09 AC 2 ms
4,348 KB
testcase_10 AC 2 ms
4,348 KB
testcase_11 AC 2 ms
4,348 KB
testcase_12 AC 2 ms
4,348 KB
testcase_13 AC 92 ms
20,292 KB
testcase_14 AC 90 ms
20,292 KB
testcase_15 AC 4 ms
4,348 KB
testcase_16 AC 8 ms
4,552 KB
testcase_17 AC 6 ms
4,348 KB
testcase_18 AC 6 ms
4,348 KB
testcase_19 AC 4 ms
4,348 KB
testcase_20 AC 68 ms
16,028 KB
権限があれば一括ダウンロードができます

ソースコード

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