Untitled

mail@pastecode.io avatar
unknown
plain_text
a month ago
4.1 kB
3
Indexable
Never
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
template<class T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define ll long long
#define db double
#define all(v) v.begin(), v.end()
#define allr(v) v.rbegin(), v.rend()
#define speed ios_base::sync_with_stdio(false);cin.tie(0), cout.tie(0);
/*
                    " وَأَن لَّيْسَ لِلْإِنسَانِ إِلَّا مَا سَعَى ﴿39﴾ وَأَنَّ سَعْيَهُ سَوْفَ يُرَى ﴿40﴾ ثُمَّ يُجْزَاهُ الْجَزَاء الْأَوْفَى "
*/
const ll N = 2e5 + 5, inf = 2e18, mod = 1e9 + 7;
ll dx[] = {0, 0, -1, 1, -1, 1, 1, -1};
ll dy[] = {1, -1, 0, 0, 1, 1, -1, -1};
char di[] = {'R', 'L', 'U', 'D'};
int tin[N], tout[N], timer;

struct segtree {
    ll tree_size;
    vector<ll> segdata;

    segtree(ll n) {
        tree_size = 1;
        while (tree_size < n)
            tree_size *= 2;
        segdata.assign(2 * tree_size, 0);
    }

    void init(vector<ll> &a, ll ni, ll lx, ll rx) {
        if (rx - lx == 1) {
            if (lx < a.size())
                segdata[ni] = a[lx];
            return;
        }
        ll m = (lx + rx) / 2;
        init(a, 2 * ni + 1, lx, m);
        init(a, 2 * ni + 2, m, rx);
        segdata[ni] = megre(segdata[2 * ni + 1], segdata[2 * ni + 2]);
    }

    void init(vector<ll> &a) {
        init(a, 0, 0, tree_size);
    }

    ll megre(ll &l, ll &r) {
        return (l ^ r);
    }

    void set(ll idx, ll val, ll ni, ll lx, ll rx) {
        if (rx - lx == 1) {
            segdata[ni] = val;
            return;
        }
        ll mid = (rx + lx) / 2;
        if (idx < mid)
            set(idx, val, 2 * ni + 1, lx, mid);
        else set(idx, val, 2 * ni + 2, mid, rx);
        segdata[ni] = megre(segdata[2 * ni + 1], segdata[2 * ni + 2]);
    }

    void set(ll idx, ll val) {
        set(idx, val, 0, 0, tree_size);
    }

    ll get(ll l, ll r, ll ni, ll lx, ll rx) {
        if (lx >= l and rx <= r)
            return segdata[ni];
        if (lx >= r or rx <= l)
            return 0;
        ll mid = (rx + lx) / 2;
        ll lf = get(l, r, 2 * ni + 1, lx, mid);
        ll ri = get(l, r, 2 * ni + 2, mid, rx);
        return megre(lf, ri);
    }

    ll get(ll l, ll r) {
        return get(l, r, 0, 0, tree_size);
    }
};

vector<ll> adj[N];
vector<ll> euler, val;

void dfs(int u, int p) {
    tin[u] = timer++;
    euler.push_back(val[u]);
    for (auto v: adj[u]) {
        if (v != p)
            dfs(v, u);
    }
    tout[u] = timer++;
    euler.push_back(val[u]);
}

void solve() {
    ll n, q;
    cin >> n >> q;
    for (int i = 0; i < n; ++i) {
        ll x;
        cin >> x;
        val.push_back(x);
    }
    for (int i = 0; i < n - 1; ++i) {
        ll a, b;
        cin >> a >> b;
        a--, b--;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    dfs(0, -1);
    segtree st(euler.size());
    st.init(euler);

    while (q--) {
        ll type;
        cin >> type;
        if (type == 1) {
            ll node, x;
            cin >> node >> x;
            node--;
            st.set(tin[node], x);
            st.set(tout[node], x);
        } else {
            ll u, v;
            cin >> u >> v;
            u--, v--;
            cout << st.get(tin[u], tout[v]) << "\n";
        }
    }
}

void file() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}

int main() {
    speed
    file();
//    freopen("cowland.in", "r", stdin);
//    freopen("cowland.out", "w", stdout);
    int testcases = 1;
//    cin >> testcases;
    while (testcases--)
        solve();

}
Leave a Comment