제출 #492388

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
492388		hohohaha	Birthday gift (IZhO18_treearray)	C++14	100 / 100	960 ms	130116 KiB

treearray

// #pragma GCC optimize("Ofast")
// #pragma GCC targt("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
// #pragma GCC optimize("unroll-loops")

#include "bits/stdc++.h"

// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/trie_policy.hpp>
// #include <ext/rope>

using namespace std;
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;

#define li long long
#define ld long double
#define ii pair<int, int>
#define vi vector<int> 
#define vvi vector<vi>


#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define eb emplace_back
#define em emplace
#define ob pop_back
#define om pop
#define of pop_front

#define fr front
#define bc back

#define fori(i, a, b) for(int i = (int) (a); i <= (int) (b); ++i)
#define ford(i, a, b) for(int i = (int) (a); i >= (int) (b); --i)

#define all(x) begin(x), end(x)
#define sz(x) ((int)(x).size())
#define bitc __builtin_popcountll

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rand rng
#define endl '\n'
#define sp ' '

#define fastio() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

void solve();

signed main() {
// freopen("output.out","w",stdout);
   fastio();
   
   int tc = 1;
   
//   cin >> tc; 
   
   fori(test, 1, tc) {
      solve();
   }
   return 0;
}

const ld pi = 4 * atan(1.0), eps = 1e-9;

#define int long long
const int maxn = 200000 + 5, mod = 924844033; 

const int inf = LLONG_MAX / 2; 

int n; 

int m; 

int q; 

int arr[maxn], L[maxn]; 

set<int> poses[maxn], mns[maxn]; 

vi g[maxn]; 

int tin[maxn], inptr; 

int lca[maxn << 1][21]; 

int higher(int i, int j) { 
	return tin[i] < tin[j]? i: j; 
}

int getlca(int i, int j) {  
	int ll = tin[i], rr = tin[j];
	if(ll > rr) swap(ll, rr);
	
	int bit = log2(rr - ll + 1); 
	
	int rel = lca[ll][bit], rer = lca[rr - (1 << bit) + 1][bit]; 
	
	return higher(rel, rer); 
}

void dfs(int i, int p){ 
	++inptr; 
	tin[i] = inptr; 
	
	lca[inptr][0] = i; 
	
	for(int j: g[i]) { 
		if(j - p) { 
			dfs(j, i); 
			
			++inptr; 
			lca[inptr][0] = i; 
		}
	}
}

void solve() {
	cin>> n >> m >> q; 
	fori(i,1,n - 1) { 
		int u, v; cin >> u >> v; 
		g[u].eb(v);
		g[v].eb(u); 
	}
	
	dfs(1, 1); 
	fori(bit, 1, 20) {
		fori(i, 1, inptr - (1 << bit) + 1) { 
			lca[i][bit] = higher(lca[i][bit - 1], lca[i + (1 << bit - 1)][bit - 1]); 
			assert(lca[i][bit] ); 
		}
	}
	
	fori(i, 1, m) {
		cin >> arr[i]; 
		poses[arr[i]].em(i);
		if(i > 1) { 
			L[i - 1] = getlca(arr[i - 1], arr[i]); 
			mns[L[i - 1]].em(i - 1); 
		}
	}
	
	fori(i, 1, q) { 
		int tp; cin>> tp; 
		if(tp == 1) { 
			int x, y; cin>> x >> y; 
			if(x > 1) {
				mns[L[x - 1]].erase(x - 1); 
			}
			if(x < m) mns[L[x]].erase(x); 
			
			poses[arr[x]].erase(x); 
			
			arr[x] = y; 
			
			poses[arr[x]].em(x); 
			
			if(x > 1) {
				L[x - 1] = getlca(arr[x - 1], arr[x]); 
				mns[L[x - 1]].em(x - 1); 
			}
			if(x < m) {
				L[x] = getlca(arr[x], arr[x + 1]); 
				mns[L[x]].em(x); 
			}
		}
		else { 
			int l, r, y; cin >> l >> r >> y; 
			auto it = poses[y].lower_bound(l); 
			if(it != end(poses[y]) and *it <= r) { 
				cout << *it << sp << *it << endl; 
				assert(arr[*it] == y); 
			}
			
			else { 
				auto it = mns[y].lower_bound(l); 
				if(it != end(mns[y]) and *it < r) { 
					cout << *it << sp << *it + 1 << endl; 
					assert(getlca(arr[*it], arr[*it + 1]) == y); 
				}
				else { 
					cout << -1 << sp << -1 << endl;  	
				}
			}
		}
	}
}

컴파일 시 표준 에러 (stderr) 메시지

treearray.cpp: In function 'void solve()':
treearray.cpp:131:60: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  131 |    lca[i][bit] = higher(lca[i][bit - 1], lca[i + (1 << bit - 1)][bit - 1]);
      |                                                        ~~~~^~~

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