#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 2e5 + 5;
const int M = 20;
int n, m, q;
int nums[N], vals[N], lvl[N];
int jump[N][M];
set <int> positions[N], positions1[N];
vector <int> paths[N];
int jumpUp(int pos, int len) {
for (int i = 0; (1<<i)<=len; i++)
if (len & (1<<i))
pos = jump[pos][i];
return pos;
}
int LCA(int a, int b) {
if (lvl[a] > lvl[b]) swap(a, b);
int dif = lvl[b] - lvl[a];
b = jumpUp(b, dif);
for (int i = M-1; i >= 0 && a != b; i--) {
if (jump[a][i] != jump[b][i]) {
a = jump[a][i];
b = jump[b][i];
}
}
if (a != b) a = jump[a][0];
return a;
}
void dfs(int pos, int par, int curLvl) {
lvl[pos] = curLvl;
jump[pos][0] = par;
for (auto& el : paths[pos]) {
if (el == par) continue;
dfs(el, pos, curLvl+1);
}
}
void init() {
dfs(1, 1, 0);
for (int i = 1; i <= n; i++)
for (int j = 1; j < M; j++) {
int x = jump[i][j-1];
jump[i][j] = jump[x][j-1];
}
}
void update(int pos) {
if (pos > 1) { // left
int x = LCA(nums[pos], nums[pos-1]);
int y = vals[pos-1];
vals[pos-1] = x;
if (y > 0) positions[y].erase(pos-1);
positions[x].insert(pos-1);
}
if (pos + 1 <= m) { // right
int x = LCA(nums[pos], nums[pos+1]);
int y = vals[pos];
vals[pos] = x;
if (y > 0) positions[y].erase(pos);
positions[x].insert(pos);
}
}
signed main () {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
cin >> n >> m >> q;
for (int i = 1; i < n; i++) {
int a, b; cin >> a >> b;
paths[a].pb(b);
paths[b].pb(a);
}
for (int i = 1; i <= m; i++) cin >> nums[i];
init();
memset(vals, -1, sizeof(vals));
for (int i = 1; i <= m; i++) {
positions1[nums[i]].insert(i);
update(i);
}
// for (int i = 1; i < m; i++) cout << vals[i] << " \n"[i==m-1];
for (int i = 0; i < q; i++) {
int a, b, c;
cin >> a;
if (a == 2) {
cin >> a >> b >> c; // query from l to r, find V
set <int>& cur = positions[c];
set <int>& cur1 = positions1[c];
auto it = cur.lower_bound(a);
auto it1 = cur1.lower_bound(a);
int x, y;
if (it == cur.end() || *it > b) x = y = -1;
else {
x = *it;
y = x+1;
}
// if (x == -1) cout << *it1 << '\n';
// cout << a << ',' << b << ' ';
// cout << c << ": ";
// for (auto el : cur1) cout <<el << ' '; cout << "\n";
if (x == -1 && it1 != cur1.end() && *it1 <= b) {
x = y = *it1;
}
cout << x << ' ' << y << '\n';
} else {
// cout << "UPDATE\n";
cin >> a >> b; // update
positions1[nums[a]].erase(a);
nums[a] = b;
positions1[nums[a]].insert(a);
update(a);
}
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
12 ms |
24516 KB |
n=5 |
| 2 |
Correct |
11 ms |
24564 KB |
n=100 |
| 3 |
Correct |
12 ms |
24572 KB |
n=100 |
| 4 |
Correct |
13 ms |
24548 KB |
n=100 |
| 5 |
Correct |
11 ms |
24568 KB |
n=100 |
| 6 |
Correct |
11 ms |
24564 KB |
n=100 |
| 7 |
Correct |
12 ms |
24548 KB |
n=100 |
| 8 |
Correct |
14 ms |
24568 KB |
n=100 |
| 9 |
Correct |
12 ms |
24564 KB |
n=100 |
| 10 |
Correct |
12 ms |
24576 KB |
n=100 |
| 11 |
Correct |
12 ms |
24524 KB |
n=100 |
| 12 |
Incorrect |
12 ms |
24596 KB |
Wrong output format. |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
12 ms |
24516 KB |
n=5 |
| 2 |
Correct |
11 ms |
24564 KB |
n=100 |
| 3 |
Correct |
12 ms |
24572 KB |
n=100 |
| 4 |
Correct |
13 ms |
24548 KB |
n=100 |
| 5 |
Correct |
11 ms |
24568 KB |
n=100 |
| 6 |
Correct |
11 ms |
24564 KB |
n=100 |
| 7 |
Correct |
12 ms |
24548 KB |
n=100 |
| 8 |
Correct |
14 ms |
24568 KB |
n=100 |
| 9 |
Correct |
12 ms |
24564 KB |
n=100 |
| 10 |
Correct |
12 ms |
24576 KB |
n=100 |
| 11 |
Correct |
12 ms |
24524 KB |
n=100 |
| 12 |
Incorrect |
12 ms |
24596 KB |
Wrong output format. |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
12 ms |
24516 KB |
n=5 |
| 2 |
Correct |
11 ms |
24564 KB |
n=100 |
| 3 |
Correct |
12 ms |
24572 KB |
n=100 |
| 4 |
Correct |
13 ms |
24548 KB |
n=100 |
| 5 |
Correct |
11 ms |
24568 KB |
n=100 |
| 6 |
Correct |
11 ms |
24564 KB |
n=100 |
| 7 |
Correct |
12 ms |
24548 KB |
n=100 |
| 8 |
Correct |
14 ms |
24568 KB |
n=100 |
| 9 |
Correct |
12 ms |
24564 KB |
n=100 |
| 10 |
Correct |
12 ms |
24576 KB |
n=100 |
| 11 |
Correct |
12 ms |
24524 KB |
n=100 |
| 12 |
Incorrect |
12 ms |
24596 KB |
Wrong output format. |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
12 ms |
24516 KB |
n=5 |
| 2 |
Correct |
11 ms |
24564 KB |
n=100 |
| 3 |
Correct |
12 ms |
24572 KB |
n=100 |
| 4 |
Correct |
13 ms |
24548 KB |
n=100 |
| 5 |
Correct |
11 ms |
24568 KB |
n=100 |
| 6 |
Correct |
11 ms |
24564 KB |
n=100 |
| 7 |
Correct |
12 ms |
24548 KB |
n=100 |
| 8 |
Correct |
14 ms |
24568 KB |
n=100 |
| 9 |
Correct |
12 ms |
24564 KB |
n=100 |
| 10 |
Correct |
12 ms |
24576 KB |
n=100 |
| 11 |
Correct |
12 ms |
24524 KB |
n=100 |
| 12 |
Incorrect |
12 ms |
24596 KB |
Wrong output format. |
| 13 |
Halted |
0 ms |
0 KB |
- |
