제출 #492375

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

treearray

/*#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")*/
 
#include <bits/stdc++.h>
  
#define for1(i,a,b) for (int i = a; i <= b; i++)
#define for2(i,a,b) for (int i = a; i >= b; i--)
#define int long long

#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pb push_back
 
/*
__builtin_popcountll(x) : Number of 1-bit
__builtin_ctzll(x) : Number of trailing 0
*/
 
const long double PI = 3.1415926535897932384626433832795;
const int INF = 1000000000000000000;
const int MOD = 1000000007;
const int MOD2 = 1000000009;
const long double EPS = 1e-6;

using namespace std;

int n, m, q;
int a[200005], d[200005], up[200005][18];
pii res;
set<int> id[200005];
set<pii> se[800005];
vector<int> g[200005];

void dfs(int u, int p) {
    for1(i,1,17) up[u][i] = up[up[u][i - 1]][i - 1];
    for (auto v : g[u]) if (v != p) {
        d[v] = d[u] + 1;
        up[v][0] = u;
        dfs(v, u);
    }
}

int lca(int u, int v) {
    if (d[u] < d[v]) swap(u, v);

    for1(i,0,17) if ((d[u] - d[v]) & (1 << i)) u = up[u][i];
    if (u == v) return u;
    
    for2(i,17,0) if (up[u][i] != up[v][i]) {
        u = up[u][i];
        v = up[v][i];
    }

    return up[u][0];
}

void build(int id, int l, int r) {
    if (l == r) return;

    int m = (l + r) >> 1;
    build(id * 2, l, m);
    build(id * 2 + 1, m + 1, r);

    for (auto p : se[id * 2]) se[id].insert(p);
    for (auto p : se[id * 2 + 1]) se[id].insert(p);
    se[id].insert({lca(a[m], a[m + 1]), m});
}

void query(int id, int l, int r, int tl, int tr, int u) {
    if (l > tr || r < tl) return;
    if (l >= tl && r <= tr) {
        auto it = se[id].lower_bound({u, 0});
        if (it != se[id].end() && (*it).first == u) res = {(*it).second, (*it).second + 1};

        if (l != tl) {
            if (lca(a[l - 1], a[l]) == u) res = {l - 1, l};
        }

        return;
    }

    int m = (l + r) >> 1;
    query(id * 2, l, m, tl, tr, u); 
    query(id * 2 + 1, m + 1, r, tl, tr, u);
}

signed main() {
    
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    // freopen("cf.inp", "r", stdin);
    // freopen("cf.out", "w", stdout);

    cin >> n >> m >> q;
    for1(i,1,n - 1) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    dfs(1, 0);
    for1(i,1,m) {
        cin >> a[i];
        id[a[i]].insert(i);
    }

    build(1, 1, m);
    while (q--) {
        int op;
        cin >> op;

        if (op == 1) {
            int pos, u;
            cin >> pos >> u;
            id[a[pos]].erase(pos);
            a[pos] = u;
            id[a[pos]].insert(pos);
        }
        else {
            int l, r, u;
            cin >> l >> r >> u;

            auto it = id[u].lower_bound(l);
            if (it != id[u].end() && *it <= r) {
                cout << *it << " " << *it << "\n";
                continue;
            }

            res = {-1, -1};
            query(1, 1, m, l, r, u);
            cout << res.first << " " << res.second << "\n";
        }
    }
    
}

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