#include "bits/stdc++.h"
using namespace std;
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
#define endl '\n'
class SparseTable {
vector<vector<ii>> st;
vi log; vector<ii> raw;
int n;
void computeLog() {
log.resize(n+1, -1);
int p = 0, two_pow = 1;
while (two_pow <= n) {
log[two_pow] = p++;
two_pow *= 2;
}
int prev = 0;
for_(i, 1, n+1) {
if (log[i] != -1) prev = log[i];
else log[i] = prev;
}
}
void buildTable() {
int k = log[n]+1;
st.resize(n, vector<ii> (k));
for_(i, 0, n) st[i][0] = raw[i];
for_(p, 1, k+1) for_(i, 0, n - (1<<p) + 1)
st[i][p] = min(st[i][p-1], st[i + (1 << (p-1))][p-1]);
}
public:
void build(vector<ii> nums) {
raw = nums;
n = nums.size();
computeLog();
buildTable();
}
int mn(int l, int r) {
if (l > r) swap(l, r);
int p = log[r-l+1];
return min(st[l][p], st[r - (1<<p) + 1][p]).second;
}
};
SparseTable st;
vector<vi> adj;
vector<ii> tour;
vi tin, tout;
void dfs(int p, int d, int parent) {
tin[p] = tour.size();
tour.push_back({d, p});
for (int i: adj[p]) if (i != parent) {
dfs(i, d+1, p);
tour.push_back({d, p});
}
tin[p] = tour.size()-1;
}
int main() {
#ifdef shiven
freopen("test.in", "r", stdin);
#endif
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, m, q; cin >> n >> m >> q;
adj.resize(n); tin.resize(n); tout.resize(n);
for_(i, 0, n-1) {
int a, b; cin >> a >> b;
a -= 1; b -= 1;
adj[a].push_back(b); adj[b].push_back(a);
}
dfs(0, 0, 0);
st.build(tour);
vi nums(m);
vector<multiset<int>> pos(n);
for_(i, 0, m) {
cin >> nums[i]; nums[i]--;
pos[nums[i]].insert(i);
}
for_(i, 0, m-1) {
pos[st.mn(tin[nums[i]], tin[nums[i+1]])].insert(i);
}
// for_(i, 0, n) if (pos[i].size()) {
// cout << i << ": ";
// for (int j: pos[i]) cout << j << " " ;
// cout << endl;
// }
// cout << "....." << endl;
for_(_, 0, q) {
int t; cin >> t;
if (t == 1) {
int i, v; cin >> i >> v;
v -= 1; i -= 1;
if (i > 0) {
pos[st.mn(tin[nums[i]], tin[nums[i-1]])].erase(pos[st.mn(tin[nums[i]], tin[nums[i-1]])].find(i-1));
pos[st.mn(tin[v], tin[nums[i-1]])].insert(i);
}
if (i < m-1) {
pos[st.mn(tin[nums[i]], tin[nums[i+1]])].erase(pos[st.mn(tin[nums[i]], tin[nums[i+1]])].find(i));
pos[st.mn(tin[v], tin[nums[i+1]])].insert(i);
}
pos[nums[i]].erase(i);
nums[i] = v;
pos[nums[i]].insert(i);
} else {
int l, r, v; cin >> l >> r >> v;
v -= 1; l -= 1; r -= 1;
auto pt = pos[v].lower_bound(l);
int ansl = -2, ansr = -2;
if (pt != pos[v].end()) {
int idx = *pt;
if (nums[idx] == v) ansl = ansr = idx;
else if (idx < r) {
// cout << nums[idx] << " " << nums[idx+1] << " have lca " << v << endl;
ansl = idx; ansr = idx+1;
}
}
cout << ansl+1 << " " << ansr+1 << endl;
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
364 KB |
n=5 |
| 2 |
Runtime error |
1 ms |
620 KB |
Execution killed with signal 6 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
364 KB |
n=5 |
| 2 |
Runtime error |
1 ms |
620 KB |
Execution killed with signal 6 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
364 KB |
n=5 |
| 2 |
Runtime error |
1 ms |
620 KB |
Execution killed with signal 6 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
364 KB |
n=5 |
| 2 |
Runtime error |
1 ms |
620 KB |
Execution killed with signal 6 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
