#include <bits/stdc++.h>
#pragma GCC optimize("-O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define ll long long
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define sqr(x) (x)*(x)
#define PB push_back
#define endl "\n"
#define y1 sfsdaf
#define pll pair<ll, ll>
using namespace std;
typedef double ld;
const ll N = 2e5 + 200;
const ll LIM = 1e6 + 5;
mt19937_64 rnd(chrono::system_clock::now().time_since_epoch().count());
ll h[N],ft[N],n,d[N],m,Q,x,y,st[N];
pair<ll, ll> T[N][25];
vector<pair<ll, ll> > a;
vector<ll> v[N];
set<ll> s[N],pisos[N];
set<ll> :: iterator it;
void dfs(ll x,ll y)
{
h[x] = h[y] + 1;
T[a.size()][0] = {h[x], x};
ft[x] = a.size();
a.PB({h[x], x});
for(auto to : v[x]) if(!h[to])
{
dfs(to, x);
T[a.size()][0] = {h[x], x};
a.PB({h[x], x});
}
}
ll lca(ll a,ll b)
{
ll l,r,k;
l = ft[a];
r = ft[b];
if(l > r) swap(l, r);
k = st[r - l + 1];
return min(T[l][k], T[r - (1 << k) + 1][k]).se;
}
void ins(ll val,ll pos)
{
s[val].insert(pos);
}
void ers(ll val,ll pos)
{
s[val].erase(pos);
}
void build(ll m)
{
for(int i = 1; i <= m; i++) ins(lca(d[i], d[i + 1]), i);
}
int main()
{
// ios_base::sync_with_stdio();cin.tie(0);cout.tie(0);
cin>>n>>m>>Q;
for(int i = 1; i < n; i++)
{
cin>>x>>y;
v[x].PB(y);
v[y].PB(x);
}
dfs(1, 1);
for(int i = 1; i < N; i++)
{
st[i] = st[i - 1];
if(1 << (st[i] + 1) <= i) st[i]++;
}
for(int j = 1; j < 20; j++)
{
x = (1 << (j - 1));
for(int i = 0; i + x < a.size(); i++) T[i][j] = min(T[i][j - 1], T[i + x][j - 1]);
}
for(int i = 1; i <= m; i++) cin>>d[i];
m--;
if(m) build(m);
while(Q--)
{
ll t,pos,x,l,r,v;
cin>>t;
if(t == 1)
{
cin>>pos>>x;
if(pos <= m) ers(lca(d[pos], d[pos + 1]), pos);
if(pos - 1 > 0) ers(lca(d[pos - 1], d[pos]), pos - 1);
pisos[d[pos]].erase(pos);
d[pos] = x;
pisos[d[pos]].insert(pos);
if(pos <= m) ins(lca(d[pos], d[pos + 1]), pos);
if(pos - 1 > 0) ins(lca(d[pos - 1], d[pos]), pos - 1);
} else
{
cin>>l>>r>>v;
if(!pisos[v].empty())
{
it = lower_bound(all(pisos[v]), l);
if(it != pisos[v].end() && *it <= r)
{
cout<<*it<<" "<<*it<<endl;
continue;
}
}
if(!s[v].empty())
{
it = lower_bound(all(s[v]), l);
if(it != s[v].end() && *it + 1 <= r)
{
cout<<*it<<" "<<*it + 1<<endl;
continue;
}
}
cout<<"-1 -1"<<endl;
}
}
return 0;
}
Compilation message
treearray.cpp: In function 'int main()':
treearray.cpp:80:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i + x < a.size(); i++) T[i][j] = min(T[i][j - 1], T[i + x][j - 1]);
~~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
25464 KB |
n=5 |
| 2 |
Incorrect |
27 ms |
25468 KB |
Jury has the answer but participant has not |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
25464 KB |
n=5 |
| 2 |
Incorrect |
27 ms |
25468 KB |
Jury has the answer but participant has not |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
25464 KB |
n=5 |
| 2 |
Incorrect |
27 ms |
25468 KB |
Jury has the answer but participant has not |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
25464 KB |
n=5 |
| 2 |
Incorrect |
27 ms |
25468 KB |
Jury has the answer but participant has not |
| 3 |
Halted |
0 ms |
0 KB |
- |
