Submission #343716

#	Time	Username	Problem	Language	Result	Execution time	Memory
343716		Sprdalo	Birthday gift (IZhO18_treearray)	C++17	100 / 100	1626 ms	96632 KiB

treearray

#include <bits/stdc++.h>

using namespace std;

#define int ll
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<double> vd;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<pi> vp;
typedef vector<pl> vpl;

const int maxn = 200010;
vector<vi> p(19, vi(maxn, -1));
vi e[maxn];
vp t(maxn);
int tim;
 
void root(int x){
    for (int i : e[x]){
        if (p[0][x] == i) continue;
        p[0][i] = x;
        root(i);
    }
}

void dfs(int x){
    ++tim;
    int r = p[0][x];
    for (int i = 1; i < 19 && r > -1; ++i){
        p[i][x] = p[i - 1][r];
        r = p[i - 1][r];
    }
 
    t[x].first = tim;
    for (auto& i : e[x]){
        dfs(i);
    }
    t[x].second = tim;
}
 
int ok(int x, int y){
    if (t[x].first <= t[y].first && t[y].second <= t[x].second)
        return x;
    swap(x, y); 
    if (t[x].first <= t[y].first && t[y].second <= t[x].second)
        return x;
 
    return 0;
}

int lca(int x, int y){
    int z = ok(x, y);

    if (z){
        return z;
    }

    for (int i = 18; i > -1; --i){
        int tmp = p[i][x];
        if (tmp == -1 || ok(tmp, y)) continue;
        x = tmp;
    }

    return p[0][x];
}

set<int> s[maxn], d[maxn];
vi a;
int m;

void dodaj(int pos){
    s[a[pos]].insert(pos);
    if (pos < m){ 
        int k = lca(a[pos], a[pos+1]);
        d[k].insert(pos);
    }

    if (pos>1){
        int k = lca(a[pos], a[pos-1]);
        d[k].insert(pos-1);
    }
}

void brisi(int pos){
    s[a[pos]].erase(pos);
    if (pos < m){
        int k = lca(a[pos], a[pos+1]);
        d[k].erase(pos);
    }

    if (pos > 1){
        int k = lca(a[pos-1], a[pos]);
        d[k].erase(pos-1);
    }
}

signed main()
{
    ios_base::sync_with_stdio(false); 
    cin.tie(nullptr); 
    cout.tie(nullptr); 
    cerr.tie(nullptr);    

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

    for (int i = 0; i < n - 1; ++i){
        int u, v;
        cin >> u >> v;

        e[u].push_back(v);
        e[v].push_back(u);
    }

    root(1);

    for (int i = 1; i <= n; ++i){
        e[i].clear();
    }

    for (int i = 2; i <= n; ++i){
        e[p[0][i]].push_back(i);
    }

    dfs(1);

    a = vi(m+1);
    for (int i = 1; i <= m; ++i)
        cin >> a[i];

    for (int i = 1; i <= m; ++i){
        dodaj(i);
    }

    for (int h = 0; h < q; ++h){
        int z;
        cin >> z;

        if (z == 1){
            int pos, val;
            cin >> pos >> val;

            brisi(pos);
            a[pos] = val;
            dodaj(pos);

            continue;
        }

        int l, r, x;
        cin >> l >> r >> x;

        auto it = s[x].lower_bound(l);
        if (it != s[x].end()){
            int ind = *it;
            if (ind <= r){
                cout << ind << ' ' << ind << '\n';
                continue;
            }
        }

        it = d[x].lower_bound(l);
        if (it != d[x].end()){
            int ind = *it;
            if (ind < r){
                cout << ind << ' ' << ind+1 << '\n';
                continue;
            }
        }

        cout << "-1 -1\n";
    }
}
/*
5 4 4
1 2
3 1
3 4
5 3
4 5 2 3
2 1 3 1
1 3 5
2 3 4 5
2 1 3 1
*/

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