Submission #1264657

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264657		shiori_chan	Birthday gift (IZhO18_treearray)	C++17	100 / 100	822 ms	152488 KiB

treearray

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define eb emplace_back
#define pu push
#define ins insert
#define fi first
#define se second
#define all(a) a.begin(),a.end()
#define bruh ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fu(x,a,b) for (auto x=a;x<=b;x++)
#define fd(x,a,b) for (auto x=a;x>=b;x--)
#define int ll

using namespace std;

typedef pair<int, int> ii;
const int N = 5e5+5;
const int M = 20;
const int B = 750;
const int mod = 1e9+7;
const int inf = 1e18;
using cd = complex<double>;
const long double PI = acos(-1);
int power(int a,int b) {ll x = 1;if (a >= mod) a%=mod; while (b) {if (b & 1) x = x*a % mod;a = a*a % mod;b>>=1;}return x;} 

int n,m,q;
vector<int> adj[N];
vector<int> euler;
int tin[N], tout[N];
int h[N], a[N];
multiset<ii> s[N];

int spt[M][2000005], lg[2000005];

void buildspt() 
{
	lg[1] = 0;
	for (int i = 2; i < N; i++) lg[i] = lg[i/2] + 1;
	for (int i = 0; i < euler.size(); i++) spt[0][i] = euler[i];
	for (int i = 1; i < M; i++) 
	{
		for (int j = 0; j+(1<<i)-1 < euler.size(); j++) spt[i][j] = (h[spt[i-1][j]] < h[spt[i-1][j+(1<<(i-1))]] ? spt[i-1][j] : spt[i-1][j+(1<<(i-1))]);
	}
}

int lca(int u, int v) 
{
	if (tin[u] > tin[v]) swap(u,v);
	int l = tin[u], r = tin[v];
	int i = lg[r-l+1];
	return (h[spt[i][l]] < h[spt[i][r-(1<<i)+1]] ? spt[i][l] : spt[i][r-(1<<i)+1]);
}

void dfs(int u, int p) 
{
	tin[u] = euler.size();
	euler.pb(u);
	for (auto v : adj[u]) 
	{
		if (v == p) continue;
		h[v] = h[u] + 1;
		dfs(v, u);
		euler.pb(u);
	}
	tout[u] = euler.size()-1;
}

void solve()
{
	cin>>n>>m>>q;
	for (int i = 1; i < n; i++) 
	{
		int u,v; cin>>u>>v;
		adj[u].pb(v); adj[v].pb(u);
	}
	dfs(1, 0);
	buildspt();
	for (int i = 1; i <= m; i++) cin>>a[i], s[a[i]].insert({i, i});
	for (int i = 1; i < m; i++) 
	{
		s[lca(a[i], a[i+1])].insert({i, i+1});
		// cout<<lca(a[i], a[i+1])<<" ";
	}
	// cout<<endl;
	while (q--) 
	{
		int type;
		cin>>type;
		if (type == 1) 
		{
			int i, v;
			cin>>i>>v;
			if (i > 1) s[lca(a[i-1], a[i])].erase({i-1, i});
			if (i < m) s[lca(a[i], a[i+1])].erase({i, i+1});
			s[a[i]].erase({i, i});
			a[i] = v;
			if (i > 1) s[lca(a[i-1], a[i])].insert({i-1, i});
			if (i < m) s[lca(a[i], a[i+1])].insert({i, i+1});
			s[a[i]].insert({i, i});
		} else 
		{
			int l,r,v;
			cin>>l>>r>>v;
			auto it = s[v].lower_bound({l, 0});
			if (it == s[v].end()) 
			{
				cout<<"-1 -1"<<endl;
				continue;
			}
			ii pos = *it;
			if (pos.se <= r) cout<<pos.fi<<" "<<pos.se<<endl;
			else cout<<"-1 -1"<<endl;
		}
	}
}

/*	
Go through the mistakes you usually make and revise your code, for god's sake...
*/

signed main()
{
	//freopen("input.inp","r",stdin);
	//freopen("output.inp","w",stdout);
	int t = 1;
	// cin>>t;
	while (t--)
	{
		solve();
		cout<<"\n";
	}
}

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