제출 #167568

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
167568		Flying_dragon_02	Birthday gift (IZhO18_treearray)	C++14	100 / 100	2061 ms	71320 KiB

treearray

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair< int, int > ii;

const int N = 2e5 + 5;

int n, m, q, par[N][20], f[N], a[N];

vector< int > graph[N];

multiset< pair< int, ii > > mst;
multiset< pair< int, ii > >::iterator it;

void dfs(int u, int p) {
    for(int i = 0; i < (int)( graph[u].size() ); i++) {
        int v = graph[u][i];
        if( v == p ) continue;
        par[v][0] = u;
        f[v] = f[u] + 1;
        dfs( v, u );
    }
}

void initLCA() {
    for(int j = 1; j < 20; j++) {
        for(int i = 1; i <= n; i++)
            par[i][j] = par[ par[i][ j - 1 ] ][ j - 1 ];
    }
}

int findLCA(int u, int v) {
    if( f[u] < f[v] ) swap( u, v );
    for(int i = 19; i >= 0; i--) {
        if( par[u][i] != 0 && f[ par[u][i] ] >= f[v] )
            u = par[u][i];
    }
    if( u == v ) return u;
    for(int i = 19; i >= 0; i-- ) {
        if( par[u][i] != 0 && par[v][i] != 0 && par[u][i] != par[v][i] ) {
            u = par[u][i];
            v = par[v][i];
        }
    }
    return par[u][0];
}

int main() {
    cin.tie(0), ios_base::sync_with_stdio(0);
    cin >> n >> m >> q;
    for(int i = 1; i <= n - 1; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].pb( v );
        graph[v].pb( u );
    }
    dfs( 1, 1 );
    initLCA();
    for(int i = 1; i <= m; i++) {
        cin >> a[i];
        mst.insert( mp( a[i], mp( i, i ) ) );
    }
    for(int i = 1; i < m; i++) {
        int u = findLCA( a[i], a[i + 1] );
        mst.insert( mp( u, mp( i, i + 1 ) ) );
    }
    while(q--) {
        int type;
        cin >> type;
        if( type == 1 ) {
            int pos, v, u ;
            cin >> pos >> v;
            if( pos > 1 ) {
                u = findLCA( a[ pos ], a[pos - 1] );
                it = mst.find( mp( u, mp( pos - 1, pos ) ) );
                mst.erase( it );
            }
            it = mst.find( mp( a[ pos ], mp( pos, pos ) ) );
            mst.erase( it );
            if( pos < m ) {
                u = findLCA( a[ pos ], a[pos + 1] );
                it = mst.find( mp( u, mp( pos , pos + 1 ) ) );
                mst.erase( it );
            }
            a[pos] = v;
            if( pos > 1 ) {
                u = findLCA( a[ pos ], a[pos - 1] );
                it = mst.insert( mp( u, mp( pos - 1, pos ) ) );
            }
            it = mst.insert( mp( a[ pos ], mp( pos, pos ) ) );
            if( pos < m ) {
                u = findLCA( a[ pos ], a[pos + 1] );
                it = mst.insert( mp( u, mp( pos , pos + 1 ) ) );
            }
        }
        else {
            int l, r, v;
            cin >> l >> r >> v;
            it = mst.lower_bound( mp( v, mp( l, l ) ) );
            if( it == mst.end() || (*it).fi != v ) {
                cout << "-1 -1\n";
                continue;
            }
            if( (*it).se.fi >= l && (*it).se.se <= r )
                cout << (*it).se.fi << " " << (*it).se.se << "\n";
            else
                cout << "-1 -1\n";
        }
    }
}

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