제출 #867691

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
867691		sleepntsheep	Birthday gift (IZhO18_treearray)	C++17	0 / 100	6 ms	27228 KiB

treearray

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <deque>
#include <set>
#include <utility>
#include <array>

using namespace std;
#define ALL(x) x.begin(), x.end()
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false);
using ll = long long;
#define N 200005

int n, m, q, timer, a[N], P[N], J[N], L[N];
int b[N][2];
vector<int> g[N];
set<int> s[N], t[N];

void dfs(int u, int p)
{
    b[u][0] = timer++;
    for (auto v : g[u]) if (v^p) {
        P[v] = u; L[v] = L[u] + 1;
        J[v] = (L[u] - L[J[u]] == L[J[u]] - L[J[J[u]]]) ? J[J[u]]: u;
        dfs(v, u);
    }
    b[u][1] = timer++;
}

int lca(int u, int v)
{
    if (L[u]<L[v])swap(u,v);
    for(;L[u]>L[v];) u=(L[J[u]]>=L[v])?J[u]:P[u];
    for(;u^v;) if (J[u]^J[v])u=J[u],v=J[v]; else u=P[u],v=P[v];
    return u;
}

int main()
{
    ShinLena;
    cin >> n >> m >> q;
    for (int u, v, i = 1; i < n; ++i) cin >> u >> v, g[u].push_back(v), g[v].push_back(u);
    P[1] = J[1] = 1; dfs(1, 1);
    for (int i = 1; i <= m; ++i) cin >> a[i], s[a[i]].insert(i);
    for (int i = 2; i <= m; ++i) t[lca(a[i-1], a[i])].insert(i);

    for (int o, x, y, v; q--;)
    {
        cin >> o >> x >> y;
        if (o == 1) 
        {
            s[a[x]].erase(x);
            if (x>1) t[lca(a[x-1], a[x])].erase(x), t[lca(a[x-1], y)].insert(x);
            if (x<m) t[lca(a[x], a[x+1])].erase(x+1), t[lca(y, a[x+1])].insert(x);
            s[y].insert(x);
            a[x] = y;
        }
        else
        {
            cin >> v;
            auto i = s[v].lower_bound(x);
            auto j = t[v].lower_bound(x+1);
            if (i != s[v].end() && *i <= y) cout << *i << ' ' << *i << '\n';
            else if (j != t[v].end() && *j <= y) cout << *j - 1 << ' ' << *j << '\n';
            else cout << "-1 -1\n";
        }
    }

    return 0;
}

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