제출 #331560

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
331560		limabeans	Birthday gift (IZhO18_treearray)	C++17	100 / 100	1369 ms	89708 KiB

treearray

#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl







const int maxn = 2e5 + 10;
const int LOG = 19;



int n, m, q;
vector<int> g[maxn];
int dep[maxn];
int par[LOG+1][maxn];

int a[maxn];


void dfs(int at, int p) {
    for (int j=1; j<LOG; j++) {
	par[j][at] = par[j-1][par[j-1][at]];
    }
    for (int to: g[at]) {
	if (to == p) continue;
	dep[to]=1+dep[at];
	par[0][to] = at;
	dfs(to, at);
    }
}


int lca(int u, int v) {
    if (dep[u]<dep[v]) swap(u,v);

    int dx = dep[u]-dep[v];
    for (int j=LOG-1; j>=0; j--) {
	if (dx>>j&1) {
	    u = par[j][u];
	}
    }

    if (u==v) return u;

    for (int j=LOG-1; j>=0; j--) {
	if (par[j][u] != par[j][v]) {
	    u = par[j][u];
	    v = par[j][v];
	}
    }

    return par[0][v];
}

set<int> dp[2][maxn];


int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    cin>>n>>m>>q;

    for (int i=0; i<n-1; i++) {
	int u,v; cin>>u>>v;
	--u; --v;
	g[u].push_back(v);
	g[v].push_back(u);
    }


    dfs(0,-1);

    for (int i=0; i<m; i++) {
	cin>>a[i];
	--a[i];
    }

    for (int i=0; i<m; i++) {
	dp[0][a[i]].insert(i);
	if (i+1<m) {
	    dp[1][lca(a[i],a[i+1])].insert(i);
	}
    }

    while (q--) {
	int op;
	cin>>op;
	if (op==1) {
	    int i,v;
	    cin>>i>>v;
	    --i; --v;

	    //undo

	    dp[0][a[i]].erase(i);
	    if (i>0) {
		dp[1][lca(a[i-1],a[i])].erase(i-1);
	    }

	    if (i+1<m) {
		dp[1][lca(a[i],a[i+1])].erase(i);
	    }


	    //upd
	    a[i]=v;

	    dp[0][a[i]].insert(i);
	    if (i>0) {
		dp[1][lca(a[i-1],a[i])].insert(i-1);
	    }

	    if (i+1<m) {
		dp[1][lca(a[i],a[i+1])].insert(i);
	    }

	    
	} else {
	    int l,r,v;
	    cin>>l>>r>>v;
	    --l; --r; --v;
	    int x = -2, y = -2;
	    {
		auto iter = dp[0][v].lower_bound(l);
		if (iter!=dp[0][v].end() && *iter<=r) {
		    x = *iter;
		    y = *iter;
		}
	    }

	    {
		auto iter = dp[1][v].lower_bound(l);
		if (iter!=dp[1][v].end() && *iter<r) {
		    x = *iter;
		    y = *iter + 1;
		}
	    }

	    cout<<x+1<<" "<<y+1<<"\n";
	    
	}
    }
    
    
    return 0;
}

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