Submission #651276

#	Time	Username	Problem	Language	Result	Execution time	Memory
651276		becaido	Birthday gift (IZhO18_treearray)	C++17	0 / 100	13 ms	23800 KiB

treearray

#pragma GCC optimize("O3")
#pragma GCC target("popcnt")
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define Waimai ios::sync_with_stdio(false),cin.tie(0)
#define FOR(x,a,b) for(int x=a,I=b;x<=I;x++)
#define pb emplace_back
#define F first
#define S second

const int SIZE = 2e5 + 5;
const int H = __lg (SIZE) + 1;

int n, m, q;
vector<int> adj[SIZE];
int h[SIZE], to[SIZE][H + 1];
int a[SIZE];
set<int> s[SIZE], ms[SIZE];

void dfs (int pos, int fa) {
    for (int np : adj[pos]) if (np != fa) {
        h[np] = h[pos] + 1;
        to[np][0] = pos;
        dfs (np, pos);
    }
}

int jump (int pos, int k) {
    int c = 0;
    while (k) {
        if (k & 1) pos = to[pos][c];
        k >>= 1;
        c++;
    }
    return pos;
}

int lca (int a, int b) {
    if (h[a] < h[b]) swap (a, b);
    a = jump (a, h[a] - h[b]);
    if (a == b) return a;
    for (int i = H; i >= 0; i--) if (to[a][i] != to[b][i]) {
        a = to[a][i];
        b = to[b][i];
    }
    return to[a][0];
}

void solve() {
    cin >> n >> m >> q;
    FOR (i, 2, n) {
        int a, b;
        cin >> a >> b;
        adj[a].pb (b);
        adj[b].pb (a);
    }
    h[1] = 1;
    dfs (1, 1);
    FOR (j, 1, H) FOR (i, 1, n) to[i][j] = to[to[i][j - 1]][j - 1];
    FOR (i, 1, m) {
        cin >> a[i];
        s[a[i]].insert (i);
    }
    FOR (i, 2, m) {
        ms[lca (a[i - 1], a[i])].insert (i);
    }
    while (q--) {
        int ty, p, x, l, r, lc;
        cin >> ty;
        if (ty == 1) {
            cin >> p >> x;
            s[a[p]].erase (p);
            if (p > 1) {
                lc = lca (a[p - 1], a[p]);
                ms[lc].erase (p);
            }
            if (p < m) {
                lc = lca (a[p], a[p + 1]);
                ms[lc].erase (p + 1);
            }
            a[p] = x;
            s[a[p]].insert (p);
            if (p > 1) {
                lc = lca (a[p - 1], a[p]);
                ms[lc].insert (p);
            }
            if (p < m) {
                lc = lca (a[p], a[p + 1]);
                ms[lc].insert (p + 1);
            }
        } else {
            cin >> l >> r >> x;
            auto it = s[x].lower_bound (l);
            if (it != s[x].end() && *it <= r) {
                cout << *it << ' ' << *it << '\n';
                continue;
            }
            it = ms[x].lower_bound (l);
            if (it == ms[x].end() || *it > r || *it - 1 < l) {
                cout << "-1 -1\n";
                continue;
            }
            cout << *it - 1 << ' ' << *it << '\n';
        }
    }
}

int main() {
    Waimai;
    solve();
}

/*
5 4 4
1 2
3 1
3 4
5 3
4 5 2 3
2 1 3 1
1 3 5
2 3 4 5
2 1 3 1
*/

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