제출 #893799

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
893799		vjudge1	Birthday gift (IZhO18_treearray)	C++17	0 / 100	1 ms	6492 KiB

treearray

// 以上帝的名义
// 候选硕士
#include <bits/stdc++.h>

#ifdef local
#include "algo/debug.h"
#else
#define dbg(x...) 0
#endif

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#define Node int
#define at(i) find_by_order(i)
#define which(x) order_of_key(x)
#define SET tree<Node, null_type,less<Node>, rb_tree_tag,tree_order_statistics_node_update>

using namespace std ;
using ll = long long ;
using ld = long double ;

const int N = 2e5 + 5 ;

int n , m , q, a[N], p[N] ;
vector<int> g[N] ;

int tin[N], tout[N], timer , up[N][20] ;

void dfs(int v, int p) {
    tin[v] = ++timer ;
    up[v][0] = p ;
    for (int i = 1 ; i < 20 ; i++) {
        up[v][i] = up[up[v][i - 1]][i - 1] ;
    }
    for (auto to : g[v]) {
        if (to != p) {
            dfs(to, v) ;
        }
    }
    tout[v] = ++timer ;
}

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

int lca(int u, int v) {
    if (is(u, v)) return u ;
    if (is(v, u)) return v ;
    for (int i = 19 ; ~i ; i--) {
        if (!is(up[u][i], v)) {
            u = up[u][i] ;
        }
    }
    return up[u][0] ;
}

int32_t main() {
    ios::sync_with_stdio(false) ;
    cin.tie(nullptr) ;
    cin >> n >> m >> q ;
    for (int i = 1 ; i < n ; i++) {
        int u , v ; cin >> u >> v;
        g[u].push_back(v) ;
        g[v].push_back(u) ;
    }
    for (int i = 1 ; i <= m ; i++) {
        cin >> a[i] ;
    }
    dfs(1, 1) ;
    set<int> pos[n + 1], difSubtree[n + 1] ;
    for (int i = 1 ; i <= m ; i++) {
        pos[a[i]].insert(i) ;
        if (i < m)
            difSubtree[lca(a[i], a[i + 1])].insert(i) ;
    }
    for (int i = 0 ; i < q ; i++) {
        int cmd ; cin >> cmd ;
        if (cmd == 1) {
            int p, v; cin >> p >> v ;
            int x = a[p] ;
            a[p] = v;
            if (p < m) difSubtree[lca(a[p + 1], x)].erase(i) ;
            if (p > 1) difSubtree[lca(x, a[p - 1])].erase(p - 1) ;
            pos[x].erase(p) ;
            pos[v].insert(p) ;
            if (p < m) difSubtree[lca(a[p + 1], v)].insert(i) ;
            if (p > 1) difSubtree[lca(v, a[p - 1])].insert(p - 1) ;
        } else {
            int l, r, v; cin >> l >> r >> v ;
            auto it = pos[v].lower_bound(l) ;
            if (it != pos[v].end() && *it <= r) {
                cout << *it << ' ' << *it << "\n" ;
            } else {
                auto it = difSubtree[v].lower_bound(l) ;
                if (it != difSubtree[v].end() && *it + 1 <= r) {
                    cout << *it << ' ' << *it + 1 << '\n' ;
                } else {
                    cout << -1 << ' ' << -1 << "\n" ;
                }
            }
        }
    }
    return 0 ;
}

// 希望白银

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