제출 #1248862

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1248862		LmaoLmao	Birthday gift (IZhO18_treearray)	C++20	100 / 100	657 ms	67224 KiB

treearray

#include<bits/stdc++.h>
#define fi first
#define se second
#define name "a"
#define int long long
using namespace std;

using ll = long long;
using ii = pair<ll, ll>;
using aa = array<int,3>;

const int N = 2e5+5;
const int INF = 1e9;
const int MOD = 1e9+7;

multiset<ii> mp[N];
int s[N], head[N];
int par[N],d[N];
vector<int> adj[N];
int timer=0;
int a[N];
int eu[N];

void dfs(int u,int p) {
    s[u]=1;
    par[u]=p;
    d[u]=d[p]+1;
    for(int v:adj[u]) {
        if(v==p) continue;
        dfs(v,u);
        s[u]+=s[v];
    }
    return;
}
void tour(int u,int p) {
    int t=0;
    for(int v:adj[u]) {
        if(v==p) continue;
        if(s[t]<s[v]) t=v;
    }
    if(!t) return;
    head[t]=head[u];
    tour(t,u);
    for(int v:adj[u]) {
        if(v==p || v==t) continue;
        head[v]=v;
        tour(v,u);
    }
}

int lca(int u,int v) {
    while(head[u]!=head[v]) {
        //cout << u << ' ' << v << endl;
        if(d[head[u]]<d[head[v]]) swap(u,v);
        u=par[head[u]];
    }
    if(d[u]>d[v]) swap(u,v);
    return u;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int n,m,q;
    cin >> n >> m >> q;
    for(int i=1;i<n;i++) {
        int u,v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1,0);
    tour(1,0);
    for(int i=1;i<=m;i++) {
        cin >> a[i];
        if(i!=1) {
            mp[lca(a[i-1],a[i])].insert({i-1,i});
            //cout << lca(a[i-1],a[i]) << endl;
            //cout << i << ' ' << lca(a[i-1],a[i]) << endl;
        }
        mp[a[i]].insert({i,i});
    }
    while(q--) {
        int type;
        cin >> type;
        if(type==1) {
            int pos,v;
            cin >> pos >> v;
            if(pos!=m) {
                int x=lca(a[pos],a[pos+1]);
                auto t=mp[x].lower_bound({pos,pos+1});
                mp[x].erase(t);
            }
            if(pos!=1) {
                int x=lca(a[pos],a[pos-1]);
                auto t=mp[x].lower_bound({pos-1,pos});
                mp[x].erase(t);
            }
            mp[a[pos]].erase({pos,pos});
            a[pos]=v;
            mp[a[pos]].insert({pos,pos});
            if(pos!=m) {
                int x=lca(a[pos],a[pos+1]);
                mp[x].insert({pos,pos+1});
            }
            if(pos!=1) {
                int x=lca(a[pos-1],a[pos]);
                mp[x].insert({pos-1,pos});
            }
        }
        else {
            int l,r,v;
            cin >> l >> r >> v;
            auto t=mp[v].lower_bound({l,-1});
            if(t==mp[v].end()) {
                cout << -1 << ' ' << -1 << '\n';
                continue;
            }
            ii ans=*t;
            if(ans.se>r) {
                cout << -1 << ' ' << -1 << '\n';
                continue;
            }
            cout << ans.fi << ' ' << ans.se << '\n';
        }
    }
    return 0;
}

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