제출 #1172977

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1172977		AtabayRajabli	Birthday gift (IZhO18_treearray)	C++20	100 / 100	805 ms	95376 KiB

treearray

#include <bits/stdc++.h>
#define int long long
#define all(v) v.begin(), v.end()
using namespace std;

const int sz = 2e5 + 1, inf = 1e18;
int n, m, q, cnt, dp[20][sz], in[sz], out[sz], sg[sz << 2], a[sz];
vector<int> g[sz];
set<int> nds[sz], ind[sz];

void dfs(int v, int p)
{
    dp[0][v] = p;
    in[v] = ++cnt;
    for(int i : g[v])
    {
        if(i == p) continue;
        dp[0][i] = v;
        dfs(i, v);
    }
    out[v] = cnt;
}

bool anc(int x, int y)
{
    return in[x] <= in[y] && out[y] <= out[x];
}

int lca(int u, int v)
{
    if(anc(u, v)) return u;
    if(anc(v, u)) return v;
    for(int i = 19; i >= 0; i--)
    {
        if(!anc(dp[i][u], v)) u = dp[i][u];
    }
    return dp[0][u];
}

void upd(int ind, int l, int r, int x, int v)
{
    if(l == r)
    {
        sg[ind] = v;
        return;
    }
    int mid = (l + r) >> 1;
    if(x <= mid) upd(ind << 1, l, mid, x, v);
    else upd(ind << 1 | 1, mid + 1, r, x, v);
    sg[ind] = lca(sg[ind << 1], sg[ind << 1 | 1]);
}

void solve()
{
    out[0] = inf;
    cin >> n >> m >> q;
    for(int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1, 0);
    for(int i = 1; i < 20; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            dp[i][j] = dp[i - 1][dp[i - 1][j]];
        }
    }
    for(int i = 1; i <= m; i++)
    {
        cin >> a[i];
        ind[a[i]].insert(i);
    }
    for(int i = 1; i < m; i++)
    {
        nds[lca(a[i], a[i + 1])].insert(i);
    }
    while(q--)
    {
        int t;
        cin >> t;
        if(t == 1)
        {
            int pos, v;
            cin >> pos >> v;
            if(1 < pos)
            {
                nds[lca(a[pos - 1], a[pos])].erase(pos - 1);
                nds[lca(a[pos - 1], v)].insert(pos - 1);
            }
            if(pos < m)
            {
                nds[lca(a[pos], a[pos + 1])].erase(pos);
                nds[lca(v, a[pos + 1])].insert(pos);
            }
            ind[a[pos]].erase(pos);
            ind[v].insert(pos);
            a[pos] = v;
        }
        else
        {
            int l, r, v, x = -1, y = -1;
            cin >> l >> r >> v;
            auto fnd = ind[v].lower_bound(l);
            auto lb = nds[v].lower_bound(l);
            if(lb != nds[v].end() && *lb < r)
            {
                x = *lb, y = *lb + 1;
            }
            if(x == -1)
            {
                if(fnd != ind[v].end() && *fnd <= r) x = y = *fnd;
            }
            cout << x << " " << y << '\n';
        }
    }
}

signed main()
{                                                                  
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int t = 1;
    // cin >> t;
    while(t--) solve();
}

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