Submission #1238312

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238312		lhn	Birthday gift (IZhO18_treearray)	C++17	100 / 100	765 ms	93716 KiB

treearray

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
set<int> baolinh[200001];
set<int> bling[200001];
vector<int> E[200001];
int st[4000001], a[200001], m, q, up[20][200001], h[200001];
void dfs(int u)
{
    for (int x : E[u])
    {
        if (up[0][u] == x) continue;
        up[0][x] = u;
        h[x] = h[u] + 1;
        for (int i = 1; i < 20; ++i)
        {
            up[i][x] = up[i - 1][up[i - 1][x]];
        }
        dfs(x);
    }
}
int lca(int u, int v)
{
    if (h[u] != h[v])
    {
        if (h[u] < h[v]) swap(u, v);
        int dis = h[u] - h[v];
        for (int i = 0; i < 20; ++i)
        {
            if (dis >> i & 1) u = up[i][u];
        }
    }
    if (u == v) return u;
    int k = __lg(h[u]);
    for (int i = k; i >= 0; --i)
    {
        if (up[i][u] != up[i][v])
        {
            u = up[i][u];
            v = up[i][v];
        }
    }
    return up[0][u];
}
int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> q;
    for (int i = 1; i < n; ++i)
    {
        int u, v;
        cin >> u >> v;
        E[u].push_back(v);
        E[v].push_back(u);
    }
    dfs(1);
    for (int i = 1; i <= m; ++i)
    {
        cin >> a[i];
        bling[a[i]]. insert(i);
        if (i >= 2) baolinh[lca(a[i], a[i - 1])].insert(i);
    }
    while(q--)
    {
        int type, l, r, v;
        cin >> type >> l >> r;
        if (type == 1)
        {
            if (l >= 2)
            {
                baolinh[lca(a[l], a[l - 1])].erase(l);
                baolinh[lca(r, a[l - 1])].insert(l);
            }
            if (l != n)
            {
                baolinh[lca(a[l], a[l + 1])].erase(l + 1);
                baolinh[lca(r, a[l + 1])].insert(l + 1);
            }
            bling[a[l]].erase(l);
            bling[r].insert(l);
            a[l] = r;

        }
        else
        {
            cin >> v;
            auto bl = baolinh[v].upper_bound(l);
            auto blg = bling[v].lower_bound(l);
            int ans = -1, res = -1;
            if (bl != baolinh[v].end() && (*bl) <= r)
            {
                ans = (*bl) - 1;
                res = (*bl);
            }
            if (blg != bling[v].end() && (*blg) <= r)
            {
                ans = res = *blg;
            }
            cout << ans << " " << res << "\n";
        }
    }
}

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