제출 #91997

#제출 시각아이디문제언어결과실행 시간메모리
91997popovicirobertBirthday gift (IZhO18_treearray)C++14
56 / 100
913 ms263168 KiB
#include <bits/stdc++.h> #define lsb(x) (x & (-x)) #define ll long long #define ull unsigned long long #define ld long double // 217 // 44 using namespace std; const int MAXN = (int) 2e5; const int LOG = 19; vector <int> g[MAXN + 1]; int lvl[MAXN + 1]; int rmq[2 * MAXN + 1][LOG + 1]; int first[MAXN + 1], sz; void dfs(int nod, int par) { rmq[++sz][0] = nod; first[nod] = sz; lvl[nod] = lvl[par] + 1; for(auto it : g[nod]) { if(it != par) { dfs(it, nod); rmq[++sz][0] = nod; } } } char lg[2 * MAXN + 1]; inline void prec(int n) { dfs(1, 0); for(int i = 2; i <= sz; i++) { lg[i] = lg[i >> 1] + 1; } for(int bit = 1; (1 << bit) <= sz; bit++) { for(int i = 1; i + (1 << bit) <= sz + 1; i++) { int a = rmq[i][bit - 1], b = rmq[i + (1 << (bit - 1))][bit - 1]; if(lvl[a] < lvl[b]) rmq[i][bit] = a; else rmq[i][bit] = b; } } } inline int get(int x, int y) { x = first[x], y = first[y]; if(x > y) { swap(x, y); } int bit = lg[y - x + 1]; int a = rmq[x][bit], b = rmq[y - (1 << bit) + 1][bit]; if(lvl[a] < lvl[b]) return a; return b; } int arr[MAXN + 1]; struct SegTree { vector < multiset <int> > aint; int n; SegTree(int _n) { n = _n; aint.resize(4 * n + 1); } void update(int nod, int left, int right, int pos, int val, bool type) { if(type) { aint[nod].insert(val); } else { aint[nod].erase(aint[nod].find(val)); } if(left == right) { return ; } else { int mid = (left + right) / 2; if(pos <= mid) update(2 * nod, left, mid, pos, val, type); else update(2 * nod + 1, mid + 1, right, pos, val, type); } } pair <bool, int> query(int nod, int left, int right, int l, int r, int val) { if(l <= left && right <= r) { if(left == right) { if(*aint[nod].begin() == val) { return {1, left}; } return {0, 0}; } auto it = aint[nod].find(val); pair <int, int> ans = {0, 0}; if(it != aint[nod].end()) { int mid = (left + right) / 2; if(aint[2 * nod].find(val) != aint[2 * nod].end()) { ans = query(2 * nod, left, mid, l, r, val); } else { ans = query(2 * nod + 1, mid + 1, right, l, r, val); } } return ans; } else { int mid = (left + right) / 2; pair <int, int> ans = {0, 0}; if(l <= mid) ans = query(2 * nod, left, mid, l, r, val); if(mid < r && ans.first == 0) { pair <int, int> aux = query(2 * nod + 1, mid + 1, right, l, r, val); if(aux.first == 1) { ans = aux; } } return ans; } } }; int main() { //ifstream cin("A.in"); //ofstream cout("A.out"); int i, n, m, q; ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); cin >> n >> m >> q; for(i = 1; i < n; i++) { int x, y; cin >> x >> y; g[x].push_back(y); g[y].push_back(x); } prec(n); for(i = 1; i<= m; i++) { cin >> arr[i]; } SegTree segt1(m), segt2(m); for(i = 1; i <= m; i++) { segt1.update(1, 1, m, i, arr[i], 1); if(i < m) { segt2.update(1, 1, m, i, get(arr[i], arr[i + 1]), 1); } } while(q > 0) { q--; int type; cin >> type; if(type == 1) { int pos, nod; cin >> pos >> nod; segt1.update(1, 1, m, pos, arr[pos], 0); segt1.update(1, 1, m, pos, nod, 1); if(pos > 1) { segt2.update(1, 1, m, pos - 1, get(arr[pos - 1], arr[pos]), 0); segt2.update(1, 1, m, pos - 1, get(arr[pos - 1], nod), 1); } if(pos < m) { segt2.update(1, 1, m, pos, get(arr[pos], arr[pos + 1]), 0); segt2.update(1, 1, m, pos, get(nod, arr[pos + 1]), 1); } arr[pos] = nod; } else { int l, r, nod; cin >> l >> r >> nod; pair <int, int> ans = {0, 0}; ans = segt1.query(1, 1, m, l, r, nod); if(ans.first == 0) { if(l < r) { ans = segt2.query(1, 1, m, l, r - 1, nod); } if(ans.first) { cout << ans.second << " " << ans.second + 1 << "\n"; } else { cout << -1 << " " << -1 << "\n"; } } else { cout << ans.second << " " << ans.second << "\n"; } } } //cin.close(); //cout.close(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...