#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define int long long
template <class F, class _S>
bool chmin(F &u, const _S &v){
bool flag = false;
if ( u > v ){
u = v; flag |= true;
}
return flag;
}
template <class F, class _S>
bool chmax(F &u, const _S &v){
bool flag = false;
if ( u < v ){
u = v; flag |= true;
}
return flag;
}
const int N = (1<<18) +1, inf = 1e18+200;
//int mod = 998244353;
//int mod = 1000000007;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//#define rnd(l, r) uniform_int_distribution <int> (l, r)(rng)
struct segtree{
vector<multiset<int>> t;
segtree(){
t.resize(N*4);
};
void de(int ps, int val, int i = 1, int l = 1, int r = N){
t[i].erase(t[i].find(val));
if(l == r)return;
int m = (l + r)>>1;
if(ps <= m)de(ps, val, i*2, l, m);
else de(ps, val, i *2, m + 1, r);
};
void ad(int ps, int val, int i = 1, int l = 1, int r = N){
t[i].insert(val);
if(l==r)return;
int m = (l + r)>>1;
if(ps <= m)ad(ps, val, i*2, l, m);
else ad(ps, val, i *2, m + 1, r);
};
int fin(int &st, int tl, int tr, int v, int i = 1, int l = 1, int r = N){
if(l > tr || r < tl || st)return st;
if(tl <= l && r <= tr){
//cout << l << ' ' << r << '\n';
//for(auto x:t[i])cout << x << ' ';
//cout << '\n';
bool x = t[i].count(v) > 0;
if(!x)return 0;
int ans = r;
int cnt = 18;
while(l < r && cnt--){
int m = (l+r)>>1;
int ni = i*2;
if(t[ni].count(v) > 0){
r = m;i = ni;ans = r;
}
else {
l = m+1;i = i*2+1;ans = l;
}
}
st = ans;
return ans;
}
int m = (l + r) >> 1;
int x = fin(st, tl, tr, v, i*2, l, m);
int y = fin(st, l, tr, v, i*2,m+1, r);
if(x)return x;
else return y;
};
};
segtree t1, t2;
void solve(){
int n, m, q;
cin >> n >> m >> q;
vector<vector<int>> g(n+1);
for(int i = 1; i < n; i++){
int u, v;
cin >> u >> v;
g[u].pb(v);
g[v].pb(u);
}
vector<int> tin(n+1), tout(n+1);
vector<vector<int>> ln(22, vector<int> (n+1, 1));
int timer = 0;
auto dfs = [&](auto dfs, int ps, int pr) -> void{
ln[0][ps] = pr;
tin[ps] = timer++;
for(int i = 1; i < 20; i++)
ln[i][ps] = ln[i-1][ln[i-1][ps]];
for(int to:g[ps]){
if(to == pr)continue;
dfs(dfs, to, ps);
}
tout[ps] = timer++;
};
dfs(dfs, 1, 1);
auto lca = [&](int a, int b) -> int {
if(tin[b] <= tin[a] && tout[a] <= tout[b])return b;
if(tin[a] <= tin[b] && tout[b] <= tout[a])return a;
for(int i = 19; i >= 0; i--){
int na = ln[i][a];
if(tin[na] <= tin[b] && tout[b] <= tout[na])continue;
a = na;
}
return ln[0][a];
};
vector<int> a(m+1);
for(int i = 1; i <= m; i++){
cin >> a[i];
t1.ad(i, a[i]);
if(i > 1)t2.ad(i, lca(a[i], a[i-1]));
}
while(q--){
int ty;
cin >> ty;
if(ty == 1){
int ps, va;
cin >> ps >> va;
t1.de(ps, a[ps]);
if(ps > 1)t2.de(ps, lca(a[ps], a[ps-1]));
if(ps < n)t2.de(ps, lca(a[ps], a[ps+1]));
a[ps] = va;
t1.ad(ps, a[ps]);
if(ps > 1)t2.ad(ps, lca(a[ps], a[ps-1]));
if(ps < n)t2.ad(ps, lca(a[ps], a[ps+1]));
}else{
int l, r, val, st = 0;
cin >> l >> r >> val;
int x = t1.fin(st, l, r, val);
int y = t2.fin(st, l+1, r, val);
if(x)cout << x << ' ' << x << '\n';
else if(y)cout << y-1 << ' ' << y << '\n';
else cout << -1 << ' ' << -1 << '\n';
}
}
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int tt = 1;
//cin >> tt;
while(tt--){
solve();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
42 ms |
98908 KB |
n=5 |
| 2 |
Execution timed out |
4061 ms |
99164 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
42 ms |
98908 KB |
n=5 |
| 2 |
Execution timed out |
4061 ms |
99164 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
42 ms |
98908 KB |
n=5 |
| 2 |
Execution timed out |
4061 ms |
99164 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
42 ms |
98908 KB |
n=5 |
| 2 |
Execution timed out |
4061 ms |
99164 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
