Submission #1249226

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249226		MinhKien	Birthday gift (IZhO18_treearray)	C++20	100 / 100	859 ms	90920 KiB

treearray

#include <iostream>
#include <vector>
#include <set>

using namespace std;

#define ii pair <int, int>
const int N = 2e5 + 1;
const int M = 4e5 + 1;

int n, m, q, x, y, A[N];
vector <int> v[N];
int tin[N], tout[N], tim;
int arr[M][19], node[M], Log2[M];
set <ii> ms[N];

void DFS(int s = 1, int p = -1) {
    tin[s] = tout[s] = ++tim;
    arr[tim][0] = tin[s];
    node[tim] = s;

    if (tim >= 2) Log2[tim] = Log2[tim >> 1] + 1;

    for (int z: v[s]) {
        if (z == p) continue;
        DFS(z, s);
        tout[s] = ++tim;
        arr[tim][0] = tin[s];

        if (tim >= 2) Log2[tim] = Log2[tim >> 1] + 1;
    }
}

int LCA(int A, int B) {
    int k = Log2[B - A + 1];
    int Min = min(arr[A][k], arr[B - (1 << k) + 1][k]);
    return node[Min];
}

int LCA2(int A, int B) {
    if (tin[A] > tin[B]) swap(A, B);
    int k = Log2[tout[B] - tin[A] + 1];
    int Min = min(arr[tin[A]][k], arr[tout[B] - (1 << k) + 1][k]);
    return node[Min];
}

int main() {
    cin.tie(0); cout.tie(0);
    ios_base::sync_with_stdio(false);

    cin >> n >> m >> q;
    for (int i = 1; i < n; ++i) {
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }

    DFS();
    for (int i = 1; i <= 18; ++i) {
        for (int j = 1; j + (1 << i) - 1 <= tim; ++j) {
            arr[j][i] = min(arr[j][i - 1], arr[j + (1 << (i - 1))][i - 1]);
        }
    }

    for (int i = 1; i <= m; ++i) {
        cin >> A[i];

        if (i > 1) {
            ms[LCA2(A[i], A[i - 1])].insert(ii(i - 1, i));
        }
        ms[A[i]].insert(ii(i, i));
    }

    int t, p;
    while (q--) {
        cin >> t >> x >> y;

        if (t == 1) {
            if (x < m) {
                ms[LCA2(A[x], A[x + 1])].erase(ii(x, x + 1));
                ms[LCA2(y, A[x + 1])].insert(ii(x, x + 1));
            }

            if (x > 1) {
                ms[LCA2(A[x], A[x - 1])].erase(ii(x - 1, x));
                ms[LCA2(y, A[x - 1])].insert(ii(x - 1, x));
            }

            ms[A[x]].erase(ii(x, x));
            ms[y].insert(ii(x, x));

            A[x] = y;
        } else {
            cin >> p;
            auto it = ms[p].lower_bound(ii(x, x));
            if (it == ms[p].end()) cout << "-1 -1\n";
            else if ((*it).second <= y) cout << (*it).first << " " << (*it).second << "\n";
            else cout << "-1 -1\n";
        }
    }

    return 0;
}

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