This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 7;
int a[N], l[N];
set <int> s[N], s1[N];
vector <int> g[N];
int p[N][20], d[N];
void dfs (int u, int pa = 0, int depth = 0) {
p[u][0] = pa;
for (int i = 1; i < 20; i++) {
p[u][i] = p[p[u][i - 1]][i - 1];
}
d[u] = depth;
for (int v : g[u]) {
if(v != pa) {
dfs(v, u, depth + 1);
}
}
}
int lca (int u, int v) {
if (d[u] > d[v]) {
swap(u, v);
}
for (int i = 19; i >= 0; i--) {
if ((d[v] - d[u]) >> i & 1) {
v = p[v][i];
}
}
if (u == v) {
return u;
}
for (int i = 19; i >= 0; i--) {
if (p[u][i] != p[v][i]) {
u = p[u][i];
v = p[v][i];
}
}
return p[u][0];
}
void solve() {
int n, m, q;
cin >> n >> m >> q;
for(int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1);
for(int i = 1; i <= m; i++) {
cin >> a[i];
s1[a[i]].insert(i);
}
auto del = [&] (int pos) {
s[l[pos]].erase(pos);
};
auto calc = [&] (int pos) {
l[pos] = lca(a[pos], a[pos + 1]);
s[l[pos]].insert(pos);
};
for (int i = 1; i < m; i++) {
calc(i);
}
while (q--) {
int x;
cin >> x;
if (x == 1) {
int i, v;
cin >> i >> v;
s1[a[i]].erase(i);
a[i] = v;
s1[a[i]].insert(i);
if (i - 1 >= 1) {
del(i - 1);
calc(i - 1);
}
if (i + 1 <= m) {
del(i);
calc(i);
}
}
else {
int l, r, v;
cin >> l >> r >> v;
auto it = s[v].lower_bound(l);
if (it != s[v].end() && *it < r) {
cout << *it << " " << *it + 1 << "\n";
}
else {
auto it = s1[v].lower_bound(l);
if (it != s1[v].end() && *it <= r) {
cout << *it << " " << *it << "\n";
}
else {
cout << -1 << " " << -1 << "\n";
}
}
}
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t = 1;
// cin >> t;
while (t--) {
solve();
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |