Submission #683836

#	Time	Username	Problem	Language	Result	Execution time	Memory
683836		opPO	Birthday gift (IZhO18_treearray)	C++17	100 / 100	1104 ms	93732 KiB

treearray

#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>

using namespace std;

#define int long long
#define f first
#define s second
#define pb push_back
#define ld long double
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define vec vector

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
const ld eps = 1e-6;
const int mod = 998244353;
const int oo = 2e9;
const ll OO = 2e18;
const int N = 2e5 + 10;
const int K = 20;
int n, m, q, a[N], timer, tin[N], tout[N], p[N][K];
vec<int> g[N];
set<pii> pos[N];

void dfs(int v, int pr = 1)
{
    tin[v] = ++timer;
    p[v][0] = pr;
    for (int k = 1; k < K; k++) p[v][k] = p[p[v][k - 1]][k - 1];
    for (int &to : g[v])
    {
        if (to == pr) continue;
        dfs(to, v);
    }
    tout[v] = timer;
}

bool upper(int u, int v)
{
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}

int LCA(int u, int v)
{
    if (upper(u, v)) return u;
    if (upper(v, u)) return v;
    for (int k = K - 1; k >= 0; k--) if (!upper(p[u][k], v)) u = p[u][k];
    return p[u][0];
}

void solve()
{
    cin >> n >> m >> q;
    for (int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    dfs(1);
    for (int i = 1; i <= m; i++) cin >> a[i];
    for (int i = 1; i <= m; i++)
    {
        pos[a[i]].insert({i, i});
        if (i + 1 <= m) pos[LCA(a[i], a[i + 1])].insert({i, i + 1});
    }
    while (q--)
    {
        int type;
        cin >> type;
        if (type == 1)
        {
            int idx, v;
            cin >> idx >> v;
            pos[a[idx]].erase({idx, idx});
            if (idx > 1) pos[LCA(a[idx - 1], a[idx])].erase({idx - 1, idx});
            if (idx + 1 <= m) pos[LCA(a[idx], a[idx + 1])].erase({idx, idx + 1});
            a[idx] = v;
            pos[a[idx]].insert({idx, idx});
            if (idx > 1) pos[LCA(a[idx - 1], a[idx])].insert({idx - 1, idx});
            if (idx + 1 <= m) pos[LCA(a[idx], a[idx + 1])].insert({idx, idx + 1});
        }
        else
        {
            int l, r, v;
            cin >> l >> r >> v;
            auto it = pos[v].lower_bound({l, l});
            if (it == pos[v].end()) cout << "-1 -1";
            else
            {
                pii p = *it;
                if (p.f >= l && p.s <= r) cout << p.f << " " << p.s;
                else cout << "-1 -1";
            }
            cout << "\n";
        }
    }
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    solve();
    return 0;
}

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