Submission #1129324

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129324		Gray	Birthday gift (IZhO18_treearray)	C++20	56 / 100	590 ms	327680 KiB

treearray

#include <algorithm>
#include <bits/stdc++.h>
#include <cassert>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define ff first
#define ss second
#define ln "\n"
#define mp make_pair

const ll INF = 2e18;
const ll MOD = 1e9+7;

struct LCATree{
    vector<vector<ll>> A;
    vector<vector<pair<ll, ll>>> st;
    vector<ll> log, eid, enter, exit;
    vector<pair<ll, ll>> euler;
    ll n, ne;
    LCATree(ll N){
        n=N; A.resize(n+1);
    }
    void add_edge(ll u, ll v){
        A[u].push_back(v);
        A[v].push_back(u);
    }
    void dfs(ll u, ll p, ll &time, ll level){
        euler.push_back({level, u});
        eid[u] = euler.size()-1;
        enter[u]=time++;
        for (auto v:A[u]){
            if (v==p) continue;
            dfs(v, u, time, level+1);
            euler.push_back({level, u});
        }
        exit[u]=time++;
    }
    void init(){
        eid.resize(n+1); enter.resize(n+1); exit.resize(n+1);
        ll time=0;
        dfs(1, 1, time, 1);
        ne = euler.size();
        log.resize(ne+1);
        for (ll i=2; i<=ne; i++) log[i]=log[i/2]+1;
        st.resize(log[ne]+1, vector<pair<ll, ll>>(ne));
        st[0]=euler;
        // cout << "Came" << endl;
        for (ll i=1; i<=log[ne]; i++){
            for (ll j=0; j<ne-(1<<(i-1)); j++){
                st[i][j] = min(st[i-1][j], st[i-1][j+(1<<(i-1))]);
            }
        }
    }
    ll lca(ll l, ll r){
        l=eid[l]; r=eid[r];
        if (l>r) swap(l, r);
        ll len = log[r-l+1];
        return min(st[len][l], st[len][r-(1<<len)+1]).ss;
    }
};

struct SegTree{
    vector<set<pair<ll, ll>>> t;
    ll sz, rsz;
    SegTree(ll N){
        sz=N*4; rsz=N;
        t.resize(sz);
    }

    void build(ll tl, ll tr, ll v, vector<ll> &a){
        if (tl==tr){
            t[v].insert({a[tl], tl});
        }else{
            ll tm = (tl+tr)/2;
            build(tl, tm, v*2, a);
            build(tm+1, tr, v*2+1, a);
            for (auto ch:t[v*2]) t[v].insert(ch);
            for (auto ch:t[v*2+1]) t[v].insert(ch);
        }
    }
    void build(vector<ll> &a){
        build(0, rsz-1, 1, a);
    }
    void update(ll i, ll fx, ll tx, ll tl, ll tr, ll v){
        if (tl==tr){
            assert(i==tl);
            t[v].erase({fx, tl}); t[v].insert({tx, tl});
        }else{
            ll tm = (tl+tr)/2;
            t[v].erase({fx, i}); t[v].insert({tx, i});
            if (i<=tm) update(i, fx, tx, tl, tm, v*2);
            else update(i, fx, tx, tm+1, tr, v*2+1);
        }
    }
    void update(ll i, ll fx, ll tx){
        update(i, fx, tx, 0, rsz-1, 1);
    }
    ll query(ll l, ll r, ll x, ll tl, ll tr, ll v){
        if (l>r) return -1;
        else if (tl==l and tr==r){
            auto it = t[v].lower_bound({x, 0});
            return ((it!=t[v].end() and (*it).ff==x)?(*it).ss:-1);
        }else{
            ll tm = (tl+tr)/2;
            return max(query(l, min(r, tm), x, tl, tm, v*2), query(max(l, tm+1), r, x, tm+1, tr, v*2+1));
        }
    }
    ll query(ll l, ll r, ll x){
        return query(l, r, x, 0, rsz-1, 1);
    }
};

void solve(){
    ll n, m, q; cin >> n >> m >> q;
    LCATree tree(n);
    for (ll i=0; i<n-1; i++){
        ll u, v; cin >> u >> v;
        tree.add_edge(u, v);
    }
    tree.init();
    // return;
    vector<ll> a(m), lca(m);
    for (ll i=0; i<m; i++){
        cin >> a[i];
        if (i) lca[i] = tree.lca(a[i], a[i-1]);
    }
    SegTree tr(m); tr.build(lca);
    SegTree self(m); self.build(a);
    // return;
    while (q--){
        ll t; cin >> t;
        if (t==1){
            ll i, v; cin >> i >> v; i--;
            self.update(i, a[i], v);
            a[i]=v;
            if (i) {tr.update(i, lca[i], tree.lca(a[i-1], a[i])); lca[i]=tree.lca(a[i-1], a[i]); }
            if (i+1<m) {tr.update(i+1, lca[i+1], tree.lca(a[i], a[i+1])); lca[i+1]=tree.lca(a[i], a[i+1]);}
        }else{
            ll l, r, v;
            cin >> l >> r >> v; l--; r--;
            bool found=0;
            for (ll i=l; i<=r; i++){
                if (a[i]==v){
                    cout << i+1 << " " << i+1 << ln; found=1; break;
                }else if (i>l and tree.lca(a[i], a[i-1])==v){
                    cout << i << " " << i+1 << ln; found=1; break;
                }
            }
            if (!found) cout << "-1 -1" << ln;
            continue;
            ll op=self.query(l, r, v);
            // cout << "CAME" << endl;
            if (op!=-1) cout << op+1 << " " << op+1 << ln;
            else if (l<r){
                // cout << l+1 << "-" << r << endl;
                op = tr.query(l+1, r, v);
                // cout << "CAME" << endl;
                if (op!=-1){
                    cout << op << " " << op+1 << ln;
                }else{
                    cout << "-1 -1\n";
                }
            }else{
                cout << "-1 -1\n";
            }
        }
        // cout << "Done" << endl;
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    auto start = chrono::high_resolution_clock::now();
    ll t=1;
    // cin >> t;
    while (t--) solve();
    #ifdef LOCAL
    auto duration = chrono::duration_cast<chrono::microseconds>(chrono::high_resolution_clock::now() - start);
    cout << setprecision(0) << fixed << "time: " << (double)duration.count()/1000.0 << " milliseconds" << endl;
    #endif
}

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