#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
typedef pair<int, int> ii;
struct SegmentTree {
int a[N];
set<ii> it[4 * N];
void build(int i, int l, int r) {
for (int j = l; j <= r; ++j) it[i].insert(ii(a[j], j));
if (l == r) return;
int mid = (l + r) >> 1;
build(i << 1, l, mid), build(i << 1 | 1, mid + 1, r);
}
void init(int n, int a[]) {
for (int i = 1; i <= n; ++i) this -> a[i] = a[i];
build(1, 1, n);
}
void upd(int i, int l, int r, ii x, bool type) {
if (type == 0) it[i].insert(x);
if (type == 1) it[i].erase(x);
if (l == r) return;
int mid = (l + r) >> 1;
if (mid >= x.second) upd(i << 1, l, mid, x, type);
else upd(i << 1 | 1, mid + 1, r, x, type);
}
int find(int i, int l, int r, int L, int R, int x) {
if (l > L || L > r) return 0;
if (L <= l && r <= R) {
auto j = it[i].lower_bound(ii(x, 0));
if (j != it[i].end() && j -> first == x) return j -> second;
return 0;
}
int mid = (l + r) >> 1;
return max(find(i << 1, l, mid, L, R, x), find(i << 1 | 1, mid + 1, r, L, R, x));
}
} IT1, IT2;
int n, m, q;
int a[N];
int b[N];
int high[N];
int p[20][N];
vector<int> G[N];
int lca(int u, int v) {
if (high[u] > high[v]) swap(u, v);
for (int i = 18; i >= 0; --i) {
if (high[p[i][v]] >= high[u]) v = p[i][v];
}
for (int i = 18; i >= 0; --i) {
if (p[i][v] != p[i][u]) v = p[i][v], u = p[i][u];
}
return (u == v) ? u : p[0][u];
}
void dfs(int u) {
for (auto v : G[u]) {
if (p[0][u] == v) continue;
p[0][v] = u, high[v] = high[u] + 1, dfs(v);
}
}
int main() {
ios::sync_with_stdio(false);
cin >> n >> m >> q;
for (int i = 1; i < n; ++i) {
int u, v; cin >> u >> v;
G[u].push_back(v), G[v].push_back(u);
}
p[0][1] = 1, dfs(1);
for (int i = 1; i <= 18; ++i) {
for (int j = 1; j <= n; ++j) {
p[i][j] = p[i - 1][p[i - 1][j]];
}
}
for (int i = 1; i <= m; ++i) cin >> a[i];
IT1.init(m, a);
for (int i = 1; i < m; ++i) b[i] = lca(a[i], a[i + 1]);
IT2.init(m - 1, b);
while (q--) {
int type; cin >> type;
if (type == 1) {
int pos, v; cin >> pos >> v;
IT1.upd(1, 1, m, ii(a[pos], pos), 1);
IT1.upd(1, 1, m, ii(v, pos), 0);
IT2.upd(1, 1, m - 1, ii(lca(a[pos - 1], a[pos]), pos - 1), 1);
IT2.upd(1, 1, m - 1, ii(lca(a[pos], a[pos + 1]), pos), 1);
IT2.upd(1, 1, m - 1, ii(lca(a[pos - 1], v), pos - 1), 0);
IT2.upd(1, 1, m - 1, ii(lca(v, a[pos + 1]), pos), 0);
a[pos] = v;
}
else {
int l, r, v; cin >> l >> r >> v;
int res = 0;
res = IT1.find(1, 1, m, l, r, v);
if (!res) {
res = IT2.find(1, 1, m - 1, l, r - 1, v);
if (res) {
cout << res << ' ' << res + 1 << '\n'; continue;
}
}
else {
cout << res << ' ' << res << '\n'; continue;
}
cout << "-1 -1\n";
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
68 ms |
80336 KB |
n=5 |
| 2 |
Incorrect |
69 ms |
80356 KB |
Jury has the answer but participant has not |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
68 ms |
80336 KB |
n=5 |
| 2 |
Incorrect |
69 ms |
80356 KB |
Jury has the answer but participant has not |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
68 ms |
80336 KB |
n=5 |
| 2 |
Incorrect |
69 ms |
80356 KB |
Jury has the answer but participant has not |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
68 ms |
80336 KB |
n=5 |
| 2 |
Incorrect |
69 ms |
80356 KB |
Jury has the answer but participant has not |
| 3 |
Halted |
0 ms |
0 KB |
- |
