Submission #1262996

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262996		tubication	Birthday gift (IZhO18_treearray)	C++20	56 / 100	4091 ms	75268 KiB

treearray

/*
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠃⡀⡀⡀⠠⢄⣠⣴⣼⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣯⢿⣿⣿⣿⣾⣆⡀⡀⢻
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠟⡀⡀⠄⡐⣰⣷⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡄⣿⣿⣿⣿⣿⣷⡀⠈
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠉⡀⢀⣔⣷⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠘⣿⣿⣿⣿⣿⣿⡄
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⡀⢀⢢⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡆⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠟⢀⣦⣿⠰⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠋⡠⣷⣿⡟⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢸⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠁⣰⣿⣿⣿⠇⢼⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠈⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⠁⣴⣿⣿⣿⣿⡀⢸⣿⣿⡏⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⡀⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⠁⣼⣿⣿⣿⣿⣿⡀⠐⣿⣿⠁⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡟⣿⣿⡀⡆⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⡀⣺⣿⣿⣿⣿⣿⣿⡀⡀⢀⢈⡀⠈⢙⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠿⠿⠿⡀⠹⡿⣸⡇⢺⣿⣿⣿⢻⣿
⣿⣿⣿⣿⣿⣿⠁⢰⣿⡅⠻⣿⣿⣿⣿⡀⣿⡀⣿⡀⠐⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣶⣶⠂⡀⣶⢁⣿⣯⢸⣿⣿⠇⢸⣿
⣿⣿⣿⣿⣿⠁⡀⡀⢿⣿⡀⠉⢻⣿⣿⡇⣿⣷⡀⡀⣅⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠃⣼⡆⠋⣾⣿⣿⢸⣿⡿⡀⣾⣿
⣿⣿⣿⣿⠃⢠⣮⡀⡀⣈⠃⠘⣦⣴⣦⣤⣾⣿⣿⣶⣿⡈⣿⡀⣿⣿⣿⣿⣿⣿⣿⣿⡿⢀⣾⣿⣁⣾⣿⣿⡟⠸⠋⡤⢀⣿⣿
⣿⣿⣿⠃⢀⣾⣿⡧⠨⠿⠿⢿⣿⣿⣿⣿⣿⣿⣿⣿⣯⣽⡈⡆⠈⣿⣿⣿⣿⣿⡿⠁⣴⣿⣿⣿⣿⣿⣿⣿⣷⠿⢿⡗⢸⣿⠏
⣿⣿⠏⡀⣽⣿⣿⡇⣀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⣿⣄⢸⣄⠻⡿⠟⢁⣴⣿⠁⡀⡀⡀⡀⡀⡀⡀⡀⡀⣀⠅⣿⡟⣠
⣿⠏⡀⢲⣿⣿⣿⠇⣿⣿⡇⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⣿⣿⣿⣿⣿⣷⣴⣿⣿⣿⣿⡀⡀⡀⡀⡀⡀⡀⡀⡀⣿⡿⠘⣁⣾⣿
⠟⡀⢔⣿⣿⣿⣿⠂⣿⣿⠁⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⡀⡀⡀⡀⡀⡀⡀⡀⢸⣿⣶⠠⣿⣿⣿
⡀⡀⣺⣿⣿⣿⣿⡀⣿⣿⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡀⡀⡀⡀⡀⡀⡀⡀⡀⣿⣿⠇⣼⣿⣿⣿
⡀⡐⣿⣿⣿⣿⣿⡀⣿⣿⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡀⡀⡀⡀⡀⡀⡀⡀⢠⣿⣿⡀⣿⣿⣿⣿
⡀⢿⣿⣿⣿⣿⣿⡂⢿⣿⣷⡀⡀⡀⡀⡀⡀⡀⡀⣴⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡀⡀⡀⡀⡀⡀⡀⢀⣿⣿⡏⢰⣿⣿⣿⣿
⢀⣿⣿⣿⣿⣿⣿⡅⢸⣿⣿⣿⣷⣦⣤⣴⣶⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⣀⣀⣀⣤⣶⣿⣿⣿⡀⢼⣿⠫⣿⣿
⢨⣿⣿⣿⣿⣿⣿⡧⠐⣿⣿⣿⣿⣿⣿⣿⠉⡉⠉⣉⣉⠉⣉⣉⢉⠉⢉⡉⠉⠉⠉⠉⠉⠉⢹⣿⣿⣿⣿⣿⡏⡀⣺⡟⢰⣿⣿
⣸⣿⣿⣿⣿⣿⣿⣿⡀⣻⣿⣿⣿⣿⣿⣿⡆⣿⢸⣿⣿⡀⣿⣿⡟⡀⣿⣿⠁⣿⣿⡀⣿⠃⣼⣿⣿⣿⣿⡿⡀⡀⡿⠁⣾⣿⣿
⢺⡟⣿⣿⣿⣿⣿⣿⡀⡀⠻⣿⣿⣿⣿⣿⣿⡈⢸⣿⣿⡀⣿⣿⣷⢸⣿⣿⡀⣿⣿⠰⠋⣴⣿⣿⣿⡿⠋⡀⡀⡀⠁⢠⣿⣿⣿
⠸⡇⠹⣿⣿⣿⣿⣿⣇⡀⡀⡀⠛⢿⣿⣿⣿⣿⣄⠙⡿⢰⣿⣿⣿⢸⣿⣿⠠⡿⠋⣤⣿⣿⣿⠟⠉⡀⡀⡀⡀⡀⡀⣿⣿⣿⣿
⡀⠈⡀⠙⢿⣿⣿⣿⣿⡀⡀⡀⡀⡀⡀⣈⠉⠛⠿⢿⣶⣤⣉⣙⢉⣉⣉⣁⣤⠾⠛⠋⠉⡀⡀⡀⡀⡀⢀⣠⣤⣴⠴⠷⠶⠚⠋
⡀⡀⢰⣷⣄⡀⠛⠿⣿⣷⡀⣆⡀⡀⡀⠘⣿⣿⣿⣶⠖⣀⠲⣶⣶⣶⣶⠆⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⢀⡀⡀⡀⢈⠉⠉⠉⠉
⡀⡀⡪⣿⣿⣧⡀⢠⣤⣀⡁⡀⡀⡀⡀⣆⠈⠿⠛⣠⣿⣿⣦⠈⢿⣿⡟⢠⡀⡀⡀⡀⡀⡀⡀⡀⢽⣿⠿⡿⣿⣿⢿⡿⣿⣿⣿
⣀⡀⠱⣿⣿⣿⡀⣿⣿⣿⠟⡀⡀⡀⡀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⣤⣴⣿⠇⡀⡀⡀⣄⡀⡠⡆⠘⣿⢸⣗⣥⣿⣿⣿⣰⣴⣬
⠋⢠⣦⡀⡹⠻⣷⡟⠛⠁⡀⡀⡀⡀⡀⡀⡀⠉⠉⠋⠙⠛⠛⠛⠛⠛⠉⠉⡀⡀⡀⡀⢹⣦⠘⢿⡀⣿⡎⣾⣿⣫⡶⣾⡿⣽⣭ 
*/

#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;

#define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
#define synchronize {ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);}

#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false); debug("%s time : %.4fs", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))

#define ll long long
#define ld long double
#define ull unsigned long long

#define pii pair <int, int>
#define pli pair <ll, int>
#define pil pair <int, ll>
#define pll pair <ll, ll>

#define vvi vector <vector <int>>

#define all(v) (v).begin(), (v).end()
#define __builtin_popcount __builtin_popcountll

#define fi first
#define se second

template<class X, class Y>
    bool maximize(X &x, const Y &y) {
        if (x < y) {
            x = y;
            return true;
        }
        else return false;
    }

template <class X, class Y>
    bool minimize(X &x, Y y) {
        if (x > y) {
            x = y;
            return true;
        }
        return false;
    }   

const int nmax = 3e5 + 5;
const ll mod = 1e9 + 7;
const ll inf = 1e18;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rngesus(ll l, ll r) {
    return uniform_int_distribution <long long>(l, r)(rng);
}

/** END OF TEMPLATE **/

struct lca {
    int root, timer;
    vector<int> h, tin, tout;
    vector<vector<int>> adj, up;

    void set(int n, int r = 1) {
        root = r;
        timer = 0;

        h.assign(n + 1, 0);
        tin.assign(n + 1, 0);
        tout.assign(n + 1, 0);
        adj.assign(n + 1, {});
        up.assign(n + 1, vector<int>(20, 0));
    }

    void insert(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    void dfs(int u = -1, int p = -1) {
        if (u == -1) u = root;
        up[u][0] = (p == -1 ? u : p);

        for (int j = 1; j < 20; ++j)
            up[u][j] = up[up[u][j - 1]][j - 1];

        tin[u] = ++timer;

        for (int v : adj[u]) {
            if (v == p) continue;
            h[v] = h[u] + 1;
            dfs(v, u);
        }

        tout[u] = timer;
    }

    int query_lca(int u, int v) {
        if (h[u] != h[v]) {
            if (h[u] < h[v]) swap(u, v);
            int k = h[u] - h[v];
            for (int j = 0; j < 20; ++j)
                if (k >> j & 1) u = up[u][j];
        }
        if (u == v) return u;
        for (int j = 19; j >= 0; --j)
            if (up[u][j] != up[v][j]) {
                u = up[u][j];
                v = up[v][j];
            }
        return up[u][0];
    }

    int dist(int u, int v) {
        return h[u] + h[v] - 2 * h[query_lca(u, v)];
    }

    int ancestor_k(int u, int k) {
        for (int j = 0; j < 20; ++j)
            if (k >> j & 1) u = up[u][j];
        return u;
    }

    bool child(int u, int v) {
        return tin[u] <= tin[v] && tout[v] <= tout[u];
    }
} p;

struct seg_tree {
    struct node {
        int mn, mx;
        int val;

        node() { 
            mn = INT_MAX; 
            mx = INT_MIN; 
            val = -1;
        }

        node(int v) {
            mn = mx = p.tin[v];
            val = v;
        }

        node operator+ (const node &other) const {
            if (val == -1) return other;
            if (other.val == -1) return *this;

            node res;
            res.mn = min(mn, other.mn);
            res.mx = max(mx, other.mx);
            res.val = p.query_lca(val, other.val);
            return res;
        }
    };

    int n;
    vector<node> tr;

    void set(int _n, int arr[]) {
        n = _n;
        tr.assign(4 * n + 5, node());
        build(1, 1, n, arr);
    }

    void build(int id, int l, int r, int arr[]) {
        if (l == r) {
            tr[id] = node(arr[l]);
            return;
        }

        int mid = (l + r) >> 1;
        build(2 * id, l, mid, arr);
        build(2 * id + 1, mid + 1, r, arr);
        
        tr[id] = tr[2 * id] + tr[2 * id + 1];
    }

    void update(int id, int l, int r, int idx, int v) {
        if (idx < l || idx > r) return;
        if (l == r) {
            tr[id] = node(v);
            return;
        }

        int mid = (l + r) >> 1;
        update(2 * id, l, mid, idx, v);
        update(2 * id + 1, mid + 1, r, idx, v);
        
        tr[id] = tr[2 * id] + tr[2 * id + 1];
    }

    node query_node(int id, int l, int r, int u, int v) {
        if (u > r || v < l) return node();
        if (u <= l && r <= v) return tr[id];
        
        int mid = (l + r) >> 1;
        node tl = query_node(2 * id, l, mid, u, v);
        node tr = query_node(2 * id + 1, mid + 1, r, u, v);

        return tl + tr;
    }

    int query(int u, int v) {
        return query_node(1, 1, n, u, v).val;
    }

    int find_inside(int id, int l, int r, int u, int v, int x) {
        if (u > r || v < l) return -1;
        if (tr[id].mn > p.tout[x] || tr[id].mx < p.tin[x]) return -1;
        if (l == r) return l;

        int mid = (l + r) >> 1;
        int tl = find_inside(2 * id, l, mid, u, v, x);
        
        if (tl != -1) return tl;
        return find_inside(2 * id + 1, mid + 1, r, u, v, x);
    }

    int find_outside(int id, int l, int r, int u, int v, int x) {
        if (u > r || v < l) return -1;
        if (p.tin[x] <= tr[id].mn && tr[id].mx <= p.tout[x]) return -1;
        if (l == r) return l;
        
        int mid = (l + r) >> 1;
        int tl = find_outside(2 * id, l, mid, u, v, x);
        
        if (tl != -1) return tl;
        return find_outside(2 * id + 1, mid + 1, r, u, v, x);
    }
};


int n, m, q;
int u, v, arr[nmax];
int ty, idx, l, r, x;

set <int> pos[nmax];
seg_tree seg;

void update(int idx, int x) {
    if (arr[idx] == x) return;

    pos[arr[idx]].erase(idx);
    arr[idx] = x;
    pos[arr[idx]].insert(idx);
    
    seg.update(1, 1, m, idx, x);
}

pii query(int l, int r, int x) {
    auto it = pos[x].lower_bound(l);
    if (it != pos[x].end() && *it <= r) return {*it, *it};

    int curl = l;
    while (true) {
        int s = seg.find_inside(1, 1, m, curl, r, x);
        if (s == -1) break;

        int t = seg.find_outside(1, 1, m, s, r, x);
        int e = (t == -1 ? r : t - 1);
        
        int lc = seg.query(s, e);
        if (lc == x) return {s, e};
        
        curl = e + 1;
        if (curl > r) break;
    }

    return {-1, -1};
}

int main() {
    synchronize;

    cin >> n >> m >> q;

    p.set(n);

    for (int i = 1; i < n; ++i) {
        cin >> u >> v;
        p.insert(u, v);
    }

    p.dfs();

    for (int i = 1; i <= m; ++i) {
        cin >> arr[i];
        pos[arr[i]].insert(i);
    }

    seg.set(m, arr);

    while (q--) {
        cin >> ty;
        if (ty == 1) {
            cin >> idx >> x;
            update(idx, x);
        } else {
            cin >> l >> r >> x;
            auto res = query(l, r, x);
            cout << res.fi << ' ' << res.se << '\n';
        }
    }

    return (0 ^ 0);
}

• Subtask 1: 12 / 12
• Subtask 2: 18 / 18
• Subtask 3: 26 / 26
• Subtask 4: 0 / 44