Submission #345446

#	Time	Username	Problem	Language	Result	Execution time	Memory
345446		koketsu	Birthday gift (IZhO18_treearray)	C++14	100 / 100	1432 ms	172216 KiB

treearray

#include <bits/stdc++.h>
#define pb push_back
#define LL long long
#define Kultivator ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

const LL Mxn = 1e6 + 7;
const LL Mod = 1e9 + 7;
const LL Inf = 1e14 + 7;

int N, M, Q, d[Mxn][20], lvl[Mxn], LCA[Mxn], W[Mxn];

vector <int> g[Mxn];

set <int> St[Mxn], Stpos[Mxn];

void Dfs(int x, int p){
    d[x][0] = p;
    lvl[x] = lvl[p] + 1;
    for(int i = 1; i <= 18; i++){
        d[x][i] = d[d[x][i - 1]][i - 1];
    }
    for(int to : g[x]){
        if(to == p) continue;
        Dfs(to, x);
    }
}

int lca(int u, int v){
    if(lvl[u] < lvl[v]) swap(u, v);
    int dif = (lvl[u] - lvl[v]);
    for(int i = 0; i <= 18; i++){
        if((1 << i) & dif) u = d[u][i];
    }
    if(u == v) return u;
    for(int i = 18; i >= 0; i--){
        if(d[u][i] != d[v][i]) u = d[u][i], v = d[v][i];
    }
    return d[u][0];
}

void Replace(int Pos, int v, int type){
    St[lca(W[Pos], W[Pos + type])].erase(min(Pos, Pos + type));
    St[lca(v, W[Pos + type])].insert(min(Pos, Pos + type));
}

int main(){
    Kultivator;
    cin >> N >> M >> Q;
    for(int i = 1, A, B; i < N; i++){
        cin >> A >> B;
        g[A].pb(B);
        g[B].pb(A);
    }
    for(int i = 1; i <= M; i++){
        cin >> W[i];
    }
    Dfs(1, 0);
    for(int i = 1; i < M; i++){
        Stpos[W[i]].insert(i);
        St[lca(W[i], W[i + 1])].insert(i);
    }
    Stpos[W[M]].insert(M);
    while(Q--){
        int T;
        cin >> T;
        if(T == 1){
            int Pos, v;
            cin >> Pos >> v;
            if(Pos != M) Replace(Pos, v, 1);
            if(Pos != 1) Replace(Pos, v, -1);
            Stpos[W[Pos]].erase(Pos);
            Stpos[v].insert(Pos);
            W[Pos] = v;
        } else {
            int L, R, v;
            pair <int, int> Ans = {-1, -1};
            cin >> L >> R >> v;
            set <int> :: iterator it = Stpos[v].lower_bound(L);
            if(it != Stpos[v].end() && L <= *it && *it <= R) Ans.first = *it, Ans.second = *it;
            it = St[v].lower_bound(L);
            if(it != St[v].end() && L <= *it && *it + 1 <= R) Ans.first = *it, Ans.second = (*it + 1);
            cout << Ans.first << ' ' << Ans.second << '\n';
        }
    }
}

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