#include<bits/stdc++.h>
using namespace std ;
#define ll long long
#define maxn 200009
#define fi first
#define se second
#define pb push_back
#define left id<<1
#define right id<<1|1
#define re exit(0);
#define _lower(x) lower_bound(v.begin(),v.end(),x)-v.begin()+1
const int mod = 1e9+7 ;
const int INF = 1e9 ;
const int LOG = 18 ;
typedef vector<int> vi ;
typedef pair<int,int> pii ;
typedef vector<ll> vl ;
typedef vector<pii> vii ;
void add ( int &a , int b )
{
a += b ;
if ( a < 0 ) a += mod ;
if ( a >= mod ) a -= mod ;
}
template < typename T > void chkmin ( T &a , T b ) { if ( a > b ) a = b ; }
template < typename T > void chkmax ( T &a , T b ) { if ( a < b ) a = b ; }
void rf ()
{
freopen ("bai1.inp","r",stdin) ;
// freopen ("bai1.out","w",stdout) ;
}
int _pow ( int a , int n )
{
if ( n == 0 ) return 1 ;
int res = _pow (a,n/2) ;
if ( n % 2 ) return 1ll*res*res%mod*a%mod ;
else return 1ll*res*res%mod ;
}
int n , m , nq ;
vi adjList [maxn] ;
int a [maxn] ;
int tin [maxn] , tout [maxn] , timeDfs , ver [maxn] ;
int par [maxn][20] , dep [maxn] ;
void dfs ( int u = 1 )
{
tin [u] = ++ timeDfs ;
ver [timeDfs] = u ;
for ( auto v : adjList [u] )
{
if ( v == par [u][0] ) continue ;
par [v][0] = u , dep [v] = dep [u] + 1 ;
for ( int i = 1 ; i <= LOG ; i ++ ) par [v][i] = par[par[v][i-1]][i-1] ;
dfs (v) ;
}
tout [u] = timeDfs ;
}
int lca ( int u , int v )
{
if ( dep[u]<dep[v] ) swap (u,v) ;
int h = dep[u]-dep[v] ;
for ( int i = LOG ; i >= 0 ; i -- ) if ( h >> i & 1 ) u = par[u][i] ;
if ( u == v ) return u ;
for ( int i = LOG ; i >= 0 ; i -- ) if ( par[u][i] != par[v][i] ) u = par [u][i] , v = par [v][i] ;
return par [u][0] ;
}
vi T [maxn*4] ;
vi merge ( vi u , vi v )
{
vi res ;
int j = 0 ;
for ( auto x : u )
{
while ( j<v.size() && v[j]<=x ) res.pb(v[j++]) ;
res.pb(x) ;
}
while ( j < v.size() ) res.pb(v[j++]) ;
return res ;
}
void update ( int id , int l , int r , int pos , int v )
{
if ( l > pos || r < pos ) return ;
if ( l == r )
{
T [id].clear () ;
T [id].pb (v) ;
return ;
}
int mid = (l+r)/2 ;
update (left,l,mid,pos,v) ; update (right,mid+1,r,pos,v) ;
T [id] = merge (T[left],T[right]) ;
}
pii get ( int id , int l , int r , int u , int v , int low , int high )
{
if ( l > v || r < u ) return {n+1,0} ;
if ( u <= l && r <= v )
{
pii ans = {n+1,0} ;
if ( low <= T[id].back() ) ans.fi = *lower_bound(T[id].begin(),T[id].end(),low) ;
if ( high >= T[id][0] ) ans.se = *--upper_bound(T[id].begin(),T[id].end(),high) ;
return ans ;
}
int mid = (l+r)/2 ;
pii L = get (left,l,mid,u,v,low,high) ;
pii R = get (right,mid+1,r,u,v,low,high) ;
return {min(L.fi,R.fi),max(L.se,R.se)} ;
}
set <int> SET [maxn] ;
int main ()
{
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0) ;
// rf () ;
cin >> n >> m >> nq ;
for ( int i = 1 ; i < n ; i ++ )
{
int u , v ; cin >> u >> v ;
adjList [u] . pb (v) ;
adjList [v] . pb (u) ;
}
dfs () ;
for ( int i = 1 ; i <= m ; i ++ )
{
cin >> a [i] ;
SET[a[i]].insert(i) ;
update (1,1,m,i,tin[a[i]]) ;
}
while ( nq -- )
{
int op ; cin >> op ;
if ( op == 1 )
{
int pos , v ; cin >> pos >> v ;
SET[a[pos]].erase(pos) ;
a [pos] = v ;
SET[a[pos]].insert(pos) ;
update (1,1,m,pos,tin[v]) ;
}
else
{
int l , r , v ; cin >> l >> r >> v ;
// pii got = get (1,1,m,l,r,tin[v],tout[v]) ;
// int A = ver [got.fi] , B = ver [got.se] ;
// if ( A > 0 && B < n+1 && lca (A,B) == v )
// {
// r = *SET [B].lower_bound(l) ;
// l = *SET [A].lower_bound(l) ;
// if ( l > r ) swap (l,r) ;
// cout << l << " " << r << "\n" ;
// }
// else cout << - 1 << " " << - 1 << "\n" ;
int best_Min = INF , best_Max = 0 ;
int res_l , res_r , A = 0 , B = 0 ;
for ( int i = l ; i <= r ; i ++ )
{
if ( tin [a[i]] >= tin [v] )
{
if ( tin[a[i]] < best_Min )
{
best_Min = tin[a[i]] ;
A = a [i] ;
res_l = i ;
}
}
if ( tin [a[i]] <= tout [v] )
{
if ( tin [a[i]] > best_Max )
{
best_Max = tin [a[i]] ;
B = a[i] ;
res_r = i ;
}
}
}
if ( A && B && lca (A,B) == v )
{
if ( res_l > res_r ) swap (res_l,res_r) ;
cout << res_l << " " << res_r << "\n" ;
}
else cout << - 1 << " " << - 1 << "\n" ;
}
}
}
// range , error , check speical , ...
// find key , find key
//'-std=c++11' stay hard
// there is no tomorrow
Compilation message
treearray.cpp: In function 'vi merge(vi, vi)':
treearray.cpp:82:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
82 | while ( j<v.size() && v[j]<=x ) res.pb(v[j++]) ;
| ~^~~~~~~~~
treearray.cpp:85:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | while ( j < v.size() ) res.pb(v[j++]) ;
| ~~^~~~~~~~~~
treearray.cpp: In function 'void rf()':
treearray.cpp:34:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
34 | freopen ("bai1.inp","r",stdin) ;
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
treearray.cpp: In function 'int main()':
treearray.cpp:190:5: warning: 'res_r' may be used uninitialized in this function [-Wmaybe-uninitialized]
190 | if ( res_l > res_r ) swap (res_l,res_r) ;
| ^~
treearray.cpp:190:5: warning: 'res_l' may be used uninitialized in this function [-Wmaybe-uninitialized]
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
36444 KB |
n=5 |
| 2 |
Incorrect |
8 ms |
36540 KB |
Wrong range. |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
36444 KB |
n=5 |
| 2 |
Incorrect |
8 ms |
36540 KB |
Wrong range. |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
36444 KB |
n=5 |
| 2 |
Incorrect |
8 ms |
36540 KB |
Wrong range. |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
36444 KB |
n=5 |
| 2 |
Incorrect |
8 ms |
36540 KB |
Wrong range. |
| 3 |
Halted |
0 ms |
0 KB |
- |
