제출 #368237

#제출 시각아이디문제언어결과실행 시간메모리
368237nicolaalexandraBirthday gift (IZhO18_treearray)C++14
0 / 100
18 ms23916 KiB
#include <bits/stdc++.h> #define DIM 200010 using namespace std; vector <int> L[DIM]; pair <int,int> rmq[20][DIM*3]; set <int> s[DIM],s2[DIM]; int E[DIM*3],p[DIM*3],first[DIM],level[DIM],v[DIM]; int n,m,i,j,x,y,pos,val,q,k,tip,l,r; void dfs (int nod, int tata){ level[nod] = 1 + level[tata]; E[++k] = nod; first[nod] = k; for (auto vecin : L[nod]) if (vecin != tata){ dfs (vecin,nod); E[++k] = nod; } } int get_lca (int x, int y){ int posx = first[x], posy = first[y]; if (posx > posy) swap (posx,posy); int nr = p[posy-posx+1]; pair <int,int> sol = min (rmq[nr][posx],rmq[nr][posy-(1<<nr)+1]); return E[sol.second]; } int main (){ //ifstream cin ("date.in"); //ofstream cout ("date.out"); cin>>n>>m>>q; for (i=1;i<n;i++){ cin>>x>>y; L[x].push_back(y); L[y].push_back(x); } dfs (1,0); for (i=1;i<=k;i++) rmq[0][i] = make_pair(level[E[i]],i); for (i=1;(1<<i)<=k;i++) for (j=1;j<=k;j++){ rmq[i][j] = rmq[i-1][j]; if (j + (1<<(i-1)) <= k && rmq[i-1][j + (1<<(i-1))].first < rmq[i][j].first) rmq[i][j] = rmq[i-1][j + (1<<(i-1))]; } for (i=2;i<=k;i++) p[i] = p[i/2] + 1; for (i=1;i<=m;i++){ cin>>v[i]; s2[v[i]].insert(i); } for (i=1;i<m;i++){ int lca = get_lca (v[i],v[i+1]); s[lca].insert(i); } for (;q--;){ cin>>tip; if (tip == 1){ cin>>pos>>val; if (pos > 1){ int lca = get_lca (v[pos-1],v[pos]); s[lca].erase(pos-1); } if (pos < m){ int lca = get_lca (v[pos],v[pos+1]); s[lca].erase(pos); } s2[v[pos]].erase(pos); v[pos] = val; s2[v[pos]].insert(pos); if (pos > 1){ int lca = get_lca (v[pos-1],v[pos]); s[lca].insert(pos-1); } if (pos < m){ int lca = get_lca (v[pos],v[pos+1]); s[lca].insert(pos); } } else { cin>>l>>r>>val; set <int> :: iterator it = s2[val].lower_bound(l); if (it != s2[val].end() && *it < r){ cout<<(*it)<<" "<<(*it)<<"\n"; continue; } it = s[val].lower_bound(l); pos = *it; if (it == s[val].end() || *it >= r) cout<<"-1 -1\n"; else cout<<(*it)<<" "<<(*it)+1<<"\n"; } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...