제출 #167557

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
167557		combi1k1	Birthday gift (IZhO18_treearray)	C++14	100 / 100	1212 ms	84216 KiB

treearray

#include<bits/stdc++.h>

using namespace std;

const int   N   = 2e5 + 1;

vector<int> g[N];

int p[N][20];
int h[N];

void dfs(int u,int pu)  {
    for(int i = 0 ; i < 17 ; ++i)
        p[u][i + 1] = p[p[u][i]][i];
    for(int v : g[u])   if (v ^ pu) {
        p[v][0] = u;
        h[v] = h[u] + 1;
        dfs(v,u);
    }
}
int par(int u,int d)    {
    for(int i = 0 ; i < 18 ; ++i)   if (d >> i & 1)
        u = p[u][i];
    return  u;
}
int lca(int u,int v)    {
    if (h[u] < h[v])    swap(u,v);

    u = par(u, h[u] - h[v]);

    if (u == v) return  u;

    for(int i = 17 ; i >= 0 ; --i)
        if (p[u][i] != p[v][i]) {
            u = p[u][i];
            v = p[v][i];
        }
    return  p[u][0];
}

set<int> pos[N];
set<int> two[N];

int a[N];

int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;  cin >> n;
    int m;  cin >> m;
    int q;  cin >> q;

    for(int i = 1 ; i < n ; ++i)    {
        int x;  cin >> x;
        int y;  cin >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    dfs(1,0);

    for(int i = 1 ; i <= m ; ++i)   {
        cin >> a[i];
        pos[a[i]].insert(i);

        if (i > 1)
            two[lca(a[i - 1],a[i])].insert(i);
    }
    for(int i = 1 ; i <= q ; ++i)   {
        int t;  cin >> t;

        if (t == 1) {
            int p;  cin >> p;
            int v;  cin >> v;

            pos[a[p]].erase(p);

            if (p > 1)  two[lca(a[p],a[p - 1])].erase(p);
            if (p < m)  two[lca(a[p],a[p + 1])].erase(p + 1);

            a[p] = v;

            pos[a[p]].insert(p);

            if (p > 1)  two[lca(a[p],a[p - 1])].insert(p);
            if (p < m)  two[lca(a[p],a[p + 1])].insert(p + 1);
        }
        if (t == 2) {
            int l;  cin >> l;
            int r;  cin >> r;
            int v;  cin >> v;

            if (pos[v].lower_bound(l) != pos[v].upper_bound(r)) {
                int x = (*pos[v].lower_bound(l));

                cout << x << " " << x << "\n";
                continue;
            }
            if (two[v].upper_bound(l) != two[v].upper_bound(r)) {
                int x = (*two[v].upper_bound(l));

                cout << x - 1 << " " << x << "\n";
                continue;
            }
            cout << "-1 -1\n";
        }
    }
}

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