Submission #1094800

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094800		Nurislam	Birthday gift (IZhO18_treearray)	C++17	0 / 100	4061 ms	99164 KiB

treearray

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define int long long


template <class F, class _S>
bool chmin(F &u, const _S &v){
	bool flag = false;
	if ( u > v ){
		u = v; flag |= true;
	}
	return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
	bool flag = false;
	if ( u < v ){
		u = v; flag |= true;
	}
	return flag;
}

const int N = (1<<18) +1, inf = 1e18+200;
//int mod = 998244353;
//int mod = 1000000007;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//#define rnd(l, r) uniform_int_distribution <int> (l, r)(rng)

struct segtree{
	vector<multiset<int>> t;
	segtree(){
		t.resize(N*4);
	};
	void de(int ps, int val, int i = 1, int l = 1, int r = N){
		t[i].erase(t[i].find(val));
		if(l == r)return;
		int m = (l + r)>>1;
		if(ps <= m)de(ps, val, i*2, l, m);
		else de(ps, val, i *2, m + 1, r);
	};
	void ad(int ps, int val, int i = 1, int l = 1, int r = N){
		t[i].insert(val);
		if(l==r)return;
		int m = (l + r)>>1;
		if(ps <= m)ad(ps, val, i*2, l, m);
		else ad(ps, val, i *2, m + 1, r);
	};
	int fin(int &st, int tl, int tr, int v, int i = 1, int l = 1, int r = N){
		if(l > tr || r < tl || st)return st;
		if(tl <= l && r <= tr){
			//cout << l << ' ' << r << '\n';
			//for(auto x:t[i])cout << x << ' ';
			//cout << '\n';
			bool x = t[i].count(v) > 0;
			if(!x)return 0;
			int ans = r;
			int cnt = 18;
			while(l < r && cnt--){
				int m = (l+r)>>1;
				int ni = i*2;
				if(t[ni].count(v) > 0){
					r = m;i = ni;ans = r;
				}
				else {
					l = m+1;i = i*2+1;ans = l;
				}
			}
			st = ans;
			return ans;
		}
		int m = (l + r) >> 1;
		int x = fin(st, tl, tr, v, i*2, l, m);
		int y = fin(st, l, tr, v, i*2,m+1, r);
		if(x)return x;
		else return y;
	};
};
segtree t1, t2;
void solve(){
	
	int n, m, q;
	cin >> n >> m >> q;
	vector<vector<int>> g(n+1);
	for(int i = 1; i < n; i++){
		int u, v;
		cin >> u >> v;
		g[u].pb(v);
		g[v].pb(u);
	}
	vector<int> tin(n+1), tout(n+1);
	vector<vector<int>> ln(22, vector<int> (n+1, 1));
	int timer = 0;
	auto dfs = [&](auto dfs, int ps, int pr) -> void{
		ln[0][ps] = pr;
		tin[ps] = timer++;
		for(int i = 1; i < 20; i++)
			ln[i][ps] = ln[i-1][ln[i-1][ps]];
			
			
		for(int to:g[ps]){
			if(to == pr)continue;
			dfs(dfs, to, ps);
		}	
			
		tout[ps] = timer++;
	};
	dfs(dfs, 1, 1);
	auto lca = [&](int a, int b) -> int {
		if(tin[b] <= tin[a] && tout[a] <= tout[b])return b;
		if(tin[a] <= tin[b] && tout[b] <= tout[a])return a;
		for(int i = 19; i >= 0; i--){
			int na = ln[i][a];
			if(tin[na] <= tin[b] && tout[b] <= tout[na])continue;
			a = na;
		}
		return ln[0][a];
	};
	
	
	vector<int> a(m+1);
	for(int i = 1; i <= m; i++){
		cin >> a[i];
		t1.ad(i, a[i]);
		if(i > 1)t2.ad(i, lca(a[i], a[i-1]));
	}
	
	while(q--){
		int ty;
		cin >> ty;
		if(ty == 1){
			int ps, va;
			cin >> ps >> va;
			t1.de(ps, a[ps]);
			if(ps > 1)t2.de(ps, lca(a[ps], a[ps-1]));
			if(ps < n)t2.de(ps, lca(a[ps], a[ps+1]));
			
			a[ps] = va;
			t1.ad(ps, a[ps]);
			if(ps > 1)t2.ad(ps, lca(a[ps], a[ps-1]));
			if(ps < n)t2.ad(ps, lca(a[ps], a[ps+1]));
		}else{
			int l, r,  val, st = 0;
			cin >> l >> r >> val;
			
			int x = t1.fin(st, l, r, val);
			int y = t2.fin(st, l+1, r, val);
			if(x)cout << x << ' ' << x << '\n';
			else if(y)cout << y-1 << ' ' << y << '\n';
			else cout << -1 << ' ' << -1 << '\n';
			
		}
	}
	
}

 
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int tt = 1;
	//cin >> tt;
	while(tt--){
		solve();
	}
}
 

 
 
 

 
 
 

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