#include <bits/stdc++.h>
using namespace std;
const int mxN = 2e5+2, LOG = 20;
vector<int> g[mxN];
multiset<int> st[4*mxN];
int up[LOG][mxN], dep[mxN], _m;
void build(const vector<int> &v, int i = 1, int l2 = 0, int r2 = _m - 1) {
if (l2 == r2) {
st[i].insert(v[l2]);
return;
}
int m2 = (l2 + r2)/2;
build(v, 2*i, l2, m2);
build(v, 2*i+1, m2+1, r2);
for (auto u : st[2*i]) {
st[i].insert(u);
}
for (auto u : st[2*i+1]) {
st[i].insert(u);
}
}
void update(int l, int x, int y, int i = 1, int l2 = 0, int r2 = _m - 1) {
st[i].erase(st[i].find(y));
st[i].insert(x);
if (l2 == r2) return;
int m2 = (l2 + r2)/2;
if (l <= m2) {
update(l, x, y, 2*i, l2, m2);
}
else {
update(l, x, y, 2*i+1, m2+1, r2);
}
}
bool wtf = 1;
int query(int l, int r, int u, int i = 1, int l2 = 0, int r2 = _m - 1) {
if (l <= l2 && r2 <= r) {
if (st[i].find(u) != st[i].end()) {
while (l2 != r2) {
int m2 = (l2 + r2)/2;
if (st[2*i].find(u) != st[2*i].end()) {
r2 = m2;
i = 2*i;
}
else {
l2 = m2+1;
i = 2*i+1;
}
}
wtf = 0;
return l2;
}
return -1;
}
int m2 = (l2 + r2)/2;
if (l <= m2) {
int x = query(l, r, u, 2*i, l2, m2);
if (x != -1) return x;
}
if (m2 + 1 <= r) {
int x = query(l, r, u, 2*i+1, m2+1, r2);
if (x != -1) return x;
}
return -1;
}
void dfs(int s, int e) {
for (auto u : g[s]) {
if (u == e) continue;
up[0][u] = s, dep[u] = dep[s] + 1;
dfs(u, s);
}
}
int jump(int s, int k) {
for (int i = 0; i < LOG; ++i) {
if ((1 << i) & k) {
s = up[i][s];
}
}
return s;
}
int lca(int u, int v) {
if (dep[u] < dep[v]) swap(u, v);
u = jump(u, dep[u] - dep[v]);
for (int i = LOG-1; i >= 0; --i) {
if (up[i][u] != up[i][v]) {
u = up[i][u], v = up[i][v];
}
}
return up[0][u];
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, m, q;
cin >> n >> m >> q; _m = m-1;
for (int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v;
u--, v--;
g[u].push_back(v), g[v].push_back(u);
}
dfs(0, -1);
for (int i = 1; i < LOG; ++i) {
for (int j = 0; j < n; ++j) {
up[i][j] = up[i-1][up[i-1][j]];
}
}
int a[m];
multiset<int> ms[n];
vector<int> val(m-1);
for (int i = 0; i < n; ++i) ms[i].insert(1e9);
for (int i = 0; i < m; ++i) {
cin >> a[i];
a[i]--;
if (i) {
val[i-1] = lca(a[i-1], a[i]);
}
ms[a[i]].insert(i);
}
build(val);
while (q--) {
int t;
cin >> t;
if (t == 1) {
int l, u;
cin >> l >> u;
l--, u--;
if (l != m-1) {
int x = lca(u, a[l+1]);
update(l, lca(u, a[l+1]), val[l]);
val[l] = x;
}
if (l) {
int x = lca(u, a[l-1]);
update(l-1, x, val[l-1]);
val[l-1] = x;
}
ms[a[l]].erase(ms[a[l]].find(l));
ms[u].insert(l);
a[l] = u;
}
if (t == 2) {
int l, r, v;
cin >> l >> r >> v;
l--, r--, v--;
if (l == r) {
if (a[l] == v) {
cout << l+1 << ' ' << l+1 << '\n';
}
else {
cout << -1 << ' ' << -1 << '\n';
}
continue;
}
if (*ms[v].lower_bound(l) <= r) {
cout << *ms[v].lower_bound(l)+1 << ' ' << *ms[v].lower_bound(l)+1 << '\n';
}
else {
int x = query(l, r-1, v);
if (x != -1) {
cout << x+1 << ' ' << x+2 << '\n';
}
else {
cout << -1 << ' ' << -1 << '\n';
}
}
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
58972 KB |
n=5 |
| 2 |
Incorrect |
11 ms |
58968 KB |
Wrong range. |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
58972 KB |
n=5 |
| 2 |
Incorrect |
11 ms |
58968 KB |
Wrong range. |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
58972 KB |
n=5 |
| 2 |
Incorrect |
11 ms |
58968 KB |
Wrong range. |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
58972 KB |
n=5 |
| 2 |
Incorrect |
11 ms |
58968 KB |
Wrong range. |
| 3 |
Halted |
0 ms |
0 KB |
- |
