제출 #1175410

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1175410		qrn	Birthday gift (IZhO18_treearray)	C++20	0 / 100	20 ms	47432 KiB

treearray

#include <bits/stdc++.h>
using namespace std;

#define SPEED                     \
    ios_base::sync_with_stdio(0); \
    cin.tie(NULL);                \
    cout.tie(NULL);

#define pb push_back
#define ins insert
#define fi first
#define se second

#define endl "\n"
#define ALL(x) x.begin(), x.end()
#define sz(x) x.size()
#define intt long long

const intt mod = 1e9 + 7;
const intt base = 31;
const intt inf = 1e18;
const intt mxN = 2e6 + 5;
const intt L = 21;

vector<vector<intt>> graph, up;
vector<intt> in(mxN), out(mxN), a(mxN);
intt timer, n, k, q;

void dfs(intt node, intt parent) {
    in[node] = timer++;
    up[0][node] = parent;
    
    for(intt i = 1; i <= L; i++) {
        up[i][node] = up[i-1][up[i-1][node]];
    }
    
    for(auto u : graph[node]) {
        if(u != parent) {
            dfs(u, node);
        }
    }
    out[node] = timer++;
}

bool isata(intt a, intt b) {
    return in[a] <= in[b] && out[a] >= out[b];
}

intt lca(intt a, intt b) {
    if(isata(a, b)) return a;
    if(isata(b, a)) return b;
    
    for(intt i = L - 1; i >= 0; i--) {
        if(!isata(up[i][a], b)) {
            a = up[i][a];
        }
    }
    return up[0][a];
}

void solve() {
    cin >> n >> k >> q;
    graph.assign(n + 1, vector<intt>());
    up.assign(L + 1, vector<intt>(n + 5, 0));
    for(intt i = 1; i <= n - 1; i++) {
        intt a, b;
        cin >> a >> b;
        graph[a].pb(b);
        graph[b].pb(a);
    }
    dfs(1, 1);
    set<intt> pos[n + 5], pos2[n + 5];
    for(intt i = 1; i <= k; i++) {
        cin >> a[i];
        pos2[a[i]].insert(i);
    }
    vector<intt> ls(n + 5, 0);
    for(intt i = 1; i <= k - 1; i++) {
        intt l = lca(a[i], a[i + 1]);
        pos[l].insert(i);
        ls[i] = l;
    }

    while(q--) {
        intt t;
        cin >> t;
        if(t == 1) {
            intt idx, v;
            cin >> idx >> v;
            if (idx != 1) {
                intt pl = lca(a[idx-1], a[idx]), nl = lca(a[idx - 1], v);;
                if (!pos[pl].empty() && pos[pl].find(idx - 1) != pos[pl].end()) {
                    pos[pl].erase(idx - 1);
                }
                pos[nl].insert(idx - 1);
            }
            if (idx != k) {
                intt pl = lca(a[idx], a[idx+1]), nl = lca(v, a[idx + 1]);
                if (!pos[pl].empty() && pos[pl].find(idx) != pos[pl].end()) {
                    pos[pl].erase(idx);
                }
                pos[nl].insert(idx);
            }
            if (!pos2[a[idx]].empty() && pos2[a[idx]].find(idx) != pos2[a[idx]].end()) {
                pos2[a[idx]].erase(idx);
            }
            a[idx] = v;
            pos2[a[idx]].insert(idx);
        } else {
            intt l, r, v;
            cin >> l >> r >> v;
            if (!pos2[v].empty() && pos2[v].lower_bound(l) != pos2[v].end()) {
                if (*pos2[v].lower_bound(l) <= r) {
                    cout << *pos2[v].lower_bound(l) << " " << *pos2[v].lower_bound(l) << endl;
                    continue;
                }
            }
            if (pos[v].empty()) {
                cout << -1 << " " << -1 << endl;
                continue;
            }
            auto it = pos[v].lower_bound(l);
            if (it == pos[v].end()) {
                cout << -1 << " " << -1 << endl;
                continue;
            }
            intt indl = *it;
            if (indl >= r) {
                cout << -1 << " " << -1 << endl;
            } else {
                cout << indl << " " << indl + 1 << endl;
            }
        }
    }
}

signed main() {
    SPEED;
    intt tst = 1;
    // cin >> tst;
    while (tst--) {
        solve();
    }
}

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