제출 #1114248

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1114248		vjudge1	Birthday gift (IZhO18_treearray)	C++17	0 / 100	4 ms	11812 KiB

treearray

//Dost SEFEROĞLU
#include <bits/stdc++.h>
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<    
#define all(cont) cont.begin(),cont.end()
#define vi vector<int>
const int MOD = 1e9+7,inf = 2e18;
const int N = 2e5+50,Q = 2e5+50;


vi edges[N];
int tin[N],tout[N];
int A[N],B[N];
int timer = 1;
int up[N][20];

void dfs(int node,int p) {
    tin[node] = timer++;
    up[node][0] = p;
    for (auto it : edges[node]) {
        if (it != p) dfs(it,node);
    }
    tout[node] = timer-1;
}

bool anc(int a,int b) {
    return tin[a] <= tin[b] && tout[a] >= tout[b];
}

int lca(int a,int b) {
    if (anc(a,b)) return a;
    if (anc(b,a)) return b;
    for (int i = 19;i>=0;i--) if (!anc(up[a][i],b)) a = up[a][i];
    return up[a][0];
}

void solve() { 
    int n,m,q;
    cin >> n >> m >> q;
    for (int i=1;i<=n-1;i++) {
        int a,b;
        cin >> a >> b;
        edges[a].push_back(b);
        edges[b].push_back(a);
    }
    dfs(1,1);
    set<int> pos[n+1],pos2[n+1];
    for (int i = 1;i<=m;i++) {
        cin >> B[i];
        pos[B[i]].insert(i);
    }
    for (int i=1;i<20;i++) {
        for (int j = 1;j<=n;j++) up[j][i] = up[up[j][i-1]][i-1];
    }
    for (int i=1;i<=m-1;i++) {
        pos2[lca(B[i],B[i+1])].insert(i);
    }
    while (q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int p,v;
            cin >> p >> v;
            if (p>1) pos2[lca(B[p],B[p-1])].erase(p-1);
            if (p<m) pos2[lca(B[p],B[p+1])].erase(p);
            pos[B[p]].erase(p);
            B[p] = v;
            pos[v].insert(p);
            if (p > 1) pos2[lca(B[p],B[p-1])].insert(p-1);
            if (p < m) pos2[lca(B[p],B[p+1])].insert(p);
        }
        else {
            int l,r,v;
            cin >> l >> r >> v;
            auto it = pos[v].lower_bound(l);
            auto it2 = pos2[v].lower_bound(l);
            if ((it == pos[v].end() || *it > r)  && (it2 == pos2[v].end() || *it2>r)) {
                cout << -1 << " " << -1 << '\n';
                continue;
            }
            if (it != pos[v].end() && *it <= r) {
                assert(*it >= 1 && *it <= m);
                cout << *it << " " << *it << '\n';
            }
            else {
                assert(*it2 >= 1 && *it2 < m);
                cout << *it2 << " " << *it2+1 <<'\n';
            }
        }
    }
}                    
                             
signed main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Dodi
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t; 
    while (t --> 0) solve();
}

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