#include <bits/stdc++.h> using namespace std; #define pb push_back #define emb emplace_back #define fr first #define sc second #define all(x) x.begin(),x.end() #define sp << " " << typedef pair<int,int> ii; struct Node{ int l,r; Node(){l=r=0;} Node(int ll,int rr){l=ll;r=rr;} }; int sz=0; vector<Node> tree; vector<vector<int>> t,v; vector<int> h,ind; vector<ii> trust; int newNode(int l=0,int r=0){ tree.emb(l,r); return sz++; } inline int update(int node,int l,int r,int qx){ if(l==r){ if(node) return 0; node=newNode(); return node; } int mid=(l+r)/2; if(qx<=mid){ int newL=update(tree[node].l,l,mid,qx); if(!newL && !tree[node].r) return 0; else return newNode(newL,tree[node].r); } else{ int newR=update(tree[node].r,mid+1,r,qx); if(!tree[node].l && !newR) return 0; else return newNode(tree[node].l,newR); } } inline void query(int node1,int node2,int l,int r){ if(!node1 && !node2) return; if(l==r){ if(node1) trust.pb({h[l],1}); if(node2) trust.pb({h[l],2}); return; } int mid=(l+r)/2; query(tree[node1].l,tree[node2].l,l,mid); query(tree[node1].r,tree[node2].r,mid+1,r); } int n; void init(int N, int D, int H[]){ newNode(); n=N; vector<ii> zort; h.assign(n,0); ind.assign(n,0); for(int i=0;i<n;i++){ h[i]=H[i]; zort.emb(h[i],i); } sort(all(h)); sort(all(zort)); for(int i=0;i<n;i++) ind[zort[i].sc]=i; t.assign(n,vector<int>(1,0)); v.assign(n,vector<int>(1,0)); } void curseChanges(int U, int A[], int B[]){ for(int i=1;i<=U;i++){ int x=A[i-1],y=B[i-1]; x=ind[x];y=ind[y]; t[x].pb(i);t[y].pb(i); v[x].pb(update(v[x].back(),0,n-1,y)); v[y].pb(update(v[y].back(),0,n-1,x)); } } int question(int x, int y, int T) { x=ind[x];y=ind[y]; int itl=upper_bound(all(t[x]),T)-t[x].begin()-1; int itr=upper_bound(all(t[y]),T)-t[y].begin()-1; trust.clear(); query(v[x][itl],v[y][itr],0,n-1); int ans=1e9; for(int i=1;i<(int)trust.size();i++){ if(trust[i].sc!=trust[i-1].sc) ans=min(ans,trust[i].fr-trust[i-1].fr); } return ans; }