//order_of_key(k): Number of items strictly smaller than k .
//find_by_order(k): K-th element in a set (counting from zero).
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define file(s) if(fopen(s".in","r")) freopen(s".in","r",stdin);freopen(s".out","w",stdout)
#define all(x) (x).begin(), (x).end()
#define len(x) (int)x.size()
#define tm (tl + tr >> 1)
#define ls v << 1, tl, tm
#define rs v << 1 | 1, tm + 1, tr
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define elif else if
#define F first
#define S second
#define int long long
using namespace std;
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef unsigned long long ull;
typedef long long ll;
typedef double db;
typedef long double ld;
const int MOD = 1e9 + 7;
const int N = 2e5 + 7;
const int P = 911;
const ll INF = 1e18;
int rnd() {
int x = rand() << 15;
return x ^ rand();
}
int tin[N], tout[N], up[N][19], t[N << 2], a[N], temp, m;
vector <int> g[N];
void dfs(int v, int pr) {
tin[v] = ++temp;
up[v][0] = pr;
for (int i = 1; i <= 18; i++) {
up[v][i] = up[up[v][i - 1]][i - 1];
}
for (int u: g[v]) if (u != pr) {
dfs(u, v);
}
tout[v] = temp;
}
bool upper(int v, int u) {
return tin[v] <= tin[u] && tout[v] >= tout[u];
}
int lca(int v, int u) {
if (v && (!u || upper(v, u))) return v;
if (u && (!v || upper(u, v))) return u;
for (int i = 18; i >= 0; i--) {
if (!up[v][i]) continue;
if (!upper(up[v][i], u)) v = up[v][i];
}
return up[v][0];
}
void build(int v = 1, int tl = 1, int tr = m) {
if (tl == tr) {
t[v] = a[tl];
return;
}
build(ls);
build(rs);
t[v] = lca(t[v << 1], t[v << 1 | 1]);
}
void upd(int pos, int val, int v = 1, int tl = 1, int tr = m) {
if (pos == tl && tr == pos) {
a[tl] = val;
t[v] = val;
return;
}
if (pos <= tm) upd(pos, val, ls);
else upd(pos, val, rs);
t[v] = lca(t[v << 1], t[v << 1 | 1]);
}
int get(int l, int r, int v = 1, int tl = 1, int tr = m) {
if (l <= tl && tr <= r) return t[v];
elif (r < tl || tr < l) return 0;
return lca(get(l, r, ls), get(l, r, rs));
}
void GazizMadi() {
int n, q;
cin >> n >> m >> q;
for (int i = 1, v, u; i < n; i++) {
cin >> v >> u;
g[v].pb(u);
g[u].pb(v);
}
dfs(1, 0);
for (int i = 1; i <= m; i++) {
cin >> a[i];
}
build();
while (q--) {
int ty;
cin >> ty;
if (ty == 1) {
int pos, val;
cin >> pos >> val;
upd(pos, val);
} else {
int l, r, v, ans1 = -1, ans2 = -1;
cin >> l >> r >> v;
for (int i = l; i <= r; i++) {
if (a[i] == v) {
ans1 = i;
ans2 = i;
break;
}
if (lca(a[i], v) != v) continue;
int now = get(i, r);
if (now == v) {
ans1 = i;
ans2 = r;
break;
}
if (upper(v, now)) break;
int ll = i, rr = r;
while (ll <= rr) {
int mm = ll + rr >> 1;
int cc = get(i, mm);
if (cc == v) {
ans1 = i;
ans2 = mm;
break;
}
if (lca(cc, v) != v) rr = mm - 1;
else ll = mm + 1;
}
if (ll <= r && lca(i, ll) == v) {
ans1 = i;
ans2 = ll;
}
if (ans1 && ans2) break;
}
cout << ans1 << ' ' << ans2 << '\n';
}
}
}
const bool Cases = 0;
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
srand(time(0));
int TT = 1;
if (Cases) cin >> TT;
for (int i = 1; i <= TT; i++) {
//cout << "Case " << i << ": ";
GazizMadi();
}
}
Compilation message
treearray.cpp: In function 'void build(long long int, long long int, long long int)':
treearray.cpp:13:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
13 | #define tm (tl + tr >> 1)
| ~~~^~~~
treearray.cpp:14:24: note: in expansion of macro 'tm'
14 | #define ls v << 1, tl, tm
| ^~
treearray.cpp:78:8: note: in expansion of macro 'ls'
78 | build(ls);
| ^~
treearray.cpp:13:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
13 | #define tm (tl + tr >> 1)
| ~~~^~~~
treearray.cpp:15:24: note: in expansion of macro 'tm'
15 | #define rs v << 1 | 1, tm + 1, tr
| ^~
treearray.cpp:79:8: note: in expansion of macro 'rs'
79 | build(rs);
| ^~
treearray.cpp: In function 'void upd(long long int, long long int, long long int, long long int, long long int)':
treearray.cpp:13:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
13 | #define tm (tl + tr >> 1)
| ~~~^~~~
treearray.cpp:89:13: note: in expansion of macro 'tm'
89 | if (pos <= tm) upd(pos, val, ls);
| ^~
treearray.cpp:13:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
13 | #define tm (tl + tr >> 1)
| ~~~^~~~
treearray.cpp:14:24: note: in expansion of macro 'tm'
14 | #define ls v << 1, tl, tm
| ^~
treearray.cpp:89:31: note: in expansion of macro 'ls'
89 | if (pos <= tm) upd(pos, val, ls);
| ^~
treearray.cpp:13:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
13 | #define tm (tl + tr >> 1)
| ~~~^~~~
treearray.cpp:15:24: note: in expansion of macro 'tm'
15 | #define rs v << 1 | 1, tm + 1, tr
| ^~
treearray.cpp:90:21: note: in expansion of macro 'rs'
90 | else upd(pos, val, rs);
| ^~
treearray.cpp: In function 'long long int get(long long int, long long int, long long int, long long int, long long int)':
treearray.cpp:13:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
13 | #define tm (tl + tr >> 1)
| ~~~^~~~
treearray.cpp:14:24: note: in expansion of macro 'tm'
14 | #define ls v << 1, tl, tm
| ^~
treearray.cpp:97:23: note: in expansion of macro 'ls'
97 | return lca(get(l, r, ls), get(l, r, rs));
| ^~
treearray.cpp:13:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
13 | #define tm (tl + tr >> 1)
| ~~~^~~~
treearray.cpp:15:24: note: in expansion of macro 'tm'
15 | #define rs v << 1 | 1, tm + 1, tr
| ^~
treearray.cpp:97:38: note: in expansion of macro 'rs'
97 | return lca(get(l, r, ls), get(l, r, rs));
| ^~
treearray.cpp: In function 'void GazizMadi()':
treearray.cpp:139:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
139 | int mm = ll + rr >> 1;
| ~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
12888 KB |
n=5 |
| 2 |
Incorrect |
2 ms |
12892 KB |
Jury has the answer but participant has not |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
12888 KB |
n=5 |
| 2 |
Incorrect |
2 ms |
12892 KB |
Jury has the answer but participant has not |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
12888 KB |
n=5 |
| 2 |
Incorrect |
2 ms |
12892 KB |
Jury has the answer but participant has not |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
12888 KB |
n=5 |
| 2 |
Incorrect |
2 ms |
12892 KB |
Jury has the answer but participant has not |
| 3 |
Halted |
0 ms |
0 KB |
- |
