Submission #1249205

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249205		MinhKien	Birthday gift (IZhO18_treearray)	C++20	56 / 100	4094 ms	81024 KiB

treearray

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

using namespace std;

const int N = 2e5 + 1;
const int M = 4e5 + 1;

int n, m, q, x, y;
vector <int> v[N];
int tin[N], tout[N], tim;
int arr[M][19], node[M], Log2[M];
set <int> 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 A[N];
vector <pair < pair <int, int>, int > > maybe;
bool Found;
struct SEG {
    struct Node {
        int Min, Max;

        Node () {
            Min = 1e9;
            Max = -1e9;
        }

        Node (int Mn, int Mx) {
            Min = Mn;
            Max = Mx;
        }

        Node operator + (const Node &o) const {
            return Node(min(Min, o.Min), max(Max, o.Max));
        }
    } st[N << 2];

    void build(int l, int r, int id) {
        if (l == r) {
            st[id] = Node(tin[A[l]], tout[A[l]]);
            return;
        }

        int m = (l + r) >> 1;
        build(l, m, id << 1);
        build(m + 1, r, id << 1 | 1);

        st[id] = st[id << 1] + st[id << 1 | 1];
    }

    void update(int l, int r, int u, int VAL, int id) {
        if (l == r) {
            st[id] = Node(tin[VAL], tout[VAL]);
            return;
        }

        int m = (l + r) >> 1;
        if (u <= m) update(l, m, u, VAL, id << 1);
        else update(m + 1, r, u, VAL, id << 1 | 1);

        st[id] = st[id << 1] + st[id << 1 | 1];
    }

    void get(int l, int r, int u, int v, int par, int id) {
        if (Found) return;
        if (l > v || r < u) return;
        if (st[id].Min > tout[par] || st[id].Max < tin[par]) return;

        if (l >= u && r <= v) {
            if (st[id].Min >= tin[par] && st[id].Max <= tout[par]) {
                int lca = LCA(st[id].Min, st[id].Max);
                maybe.push_back(pair < pair <int, int>, int >(pair <int, int>(l, r), lca));
                if (lca == par) Found = true;
                return;
            }
        }

        if (l == r) return;

        int m = (l + r) >> 1;
        get(l, m, u, v, par, id << 1);
        get(m + 1, r, u, v, par, id << 1 | 1);
    }
} seg;

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];
        ms[A[i]].insert(i);
    }
    seg.build(1, m, 1);

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

        if (t == 1) {
            ms[A[x]].erase(x);
            A[x] = y;
            ms[A[x]].insert(x);
            seg.update(1, m, x, y, 1);
        } else {
            cin >> p;

            auto it = ms[p].lower_bound(x);
            if (it != ms[p].end() && *it <= y) {
                cout << *it << " " << *it << "\n";
                continue;
            }

            Found = false;
            maybe.clear();
            seg.get(1, m, x, y, p, 1);

            if (maybe.empty()) {
                cout << "-1 -1\n";
            } else {
                int l = maybe[0].first.first, r = maybe[0].first.second;
                int lca = maybe[0].second;

                bool ck = true;
                if (lca == p) {
                    cout << l << " " << r << "\n";
                    ck = false;
                }

                for (int i = 1; i < maybe.size() && ck; ++i) {
                    if (maybe[i].first.first == r + 1) {
                        r = maybe[i].first.second;
                        lca = LCA2(lca, maybe[i].second);
                    } else {
                        l = maybe[i].first.first;
                        r = maybe[i].first.second;
                        lca = maybe[i].second;
                    }

                    if (lca == p) {
                        cout << l << " " << r << "\n";
                        ck = false;
                        break;
                    }
                }

                if (ck) cout << "-1 -1\n";
            }
        }
    }

    return 0;
}

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