Submission #1235805

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235805		bach25089	Birthday gift (IZhO18_treearray)	C++20	0 / 100	2 ms	5184 KiB

treearray

#include <bits/stdc++.h>
using namespace std;
int n, m, q, t = 0;
vector<int> g[200005];
int up[20][200005], dep[200005], in[200005], out[200005];
int a[200005];

void dfs(int u, int p)
{
    in[u] = ++t;
    up[0][u] = p;
    dep[u] = dep[p] + 1;
    for (int v : g[u])
    {
        if (v != p) dfs(v, u);
    }
    out[u] = t;
}

int lca(int u, int v)
{
    if (dep[u] < dep[v]) swap(u, v);
    int d = dep[u] - dep[v];
    for (int k = 0; k < 20; k++)
    {
        if (d >> k & 1) u = up[k][u];
    }
    if (u == v) return u;
    for (int k = 19; k >= 0; k--)
    {
        if (up[k][u] != up[k][v])u = up[k][u], v = up[k][v];
    }
    return up[0][u];
}

struct N
{
    int l, r;
    int lca, mi, ma;
} st[800005];

N mg(N A, N B)
{
    return
    {
        A.l,
        B.r,
        lca(A.lca, B.lca),
        min(A.mi, B.mi),
        max(A.ma, B.ma)
    };
}

void bd(int p, int l, int r)
{
    if (l == r)
    {
        st[p] = {l, r, a[l], in[a[l]], in[a[l]]};
    }
    else
    {
        int m = (l + r) / 2;
        bd(p*2, l, m);
        bd(p*2+1, m+1, r);
        st[p] = mg(st[p*2], st[p*2+1]);
    }
}

void updt(int p, int i, int v)
{
    if (st[p].l == st[p].r)
    {
        a[i] = v;
        st[p] = {i, i, v, in[v], in[v]};
    }
    else
    {
        int m = (st[p].l + st[p].r) / 2;
        if (i <= m) updt(p*2, i, v);
        else updt(p*2+1, i, v);
        st[p] = mg(st[p*2], st[p*2+1]);
    }
}

pair<int, int> qry(int p, int l, int r, int v)
{
    N &nd = st[p];
    if (nd.r < l || nd.l > r) return {-1, -1};
    if (l <= nd.l && nd.r <= r)
    {
        if (nd.mi < in[v] || nd.ma > out[v]) return {-1, -1};
        if (nd.lca == v) return {max(nd.l, l), min(nd.r, r)};
        if (nd.l == nd.r) return {-1, -1};
    }
    auto L = qry(p*2, l, r, v);
    if (L.first != -1) return L;
    return qry(p*2+1, l, r, v);
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> q;
    for (int i = 1, u, v; i < n; i++)
    {
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1, 0);
    for (int k = 1; k < 20; k++)
    {
        for (int i = 1; i <= n; i++)
        {
            up[k][i] = up[k-1][up[k-1][i]];
        }
    }
    for (int i = 1; i <= m; i++)
    {
        cin >> a[i];
    }
    bd(1, 1, m);
    while (q--)
    {
        int ty;
        cin >> ty;
        if (ty == 1)
        {
            int i, v;
            cin >> i >> v;
            updt(1, i, v);
        }
        else
        {
            int l, r, v;
            cin >> l >> r >> v;
            auto ans = qry(1, l, r, v);
            if (ans.first == -1) cout << "-1 -1\n";
            else cout << ans.first << " " << ans.second << "\n";
        }
    }
}

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