#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> typedef long long ll; using namespace __gnu_pbds; using namespace std; template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; int M = 200'000; vector<int> h(M); int n, d; vector<int> is_off(M); void init(int N, int D, int H[]) { n=N,d=D; for(int i=0; i<n; ++i) h[i] = H[i]; } struct Neigh { int S = 10; set<int> secik; vector<vector<int>> save; vector<pair<int, int>> changes; vector<int> ztime; int ft; void init() { save.push_back({}); ztime.push_back(0); changes.push_back({0,0}); } void update(int x, int t) { ztime.push_back(t); if(secik.find(x)==secik.end()) { changes.push_back({x,1}); secik.insert(x); } else { changes.push_back({x,-1}); secik.erase(x); } if((changes.size()-1)%S == 0) { vector<int> reb; for(auto x : secik) reb.push_back(x); save.push_back(reb); } } void finish(int t) { ft = t; vector<int> reb; for(auto x : secik) reb.push_back(x); save.push_back(reb); } vector<int> getvec(int T) { if(T==ft) { vector<int> ans; for(auto x : save.back()) ans.push_back(h[x]); return ans; } T = upper_bound(ztime.begin(), ztime.end(), T) - ztime.begin() - 1; if(T%S==0) { vector<int> ans; for(auto x : save[T/S]) ans.push_back(h[x]); return ans; } vector<int> f = save[T/S]; vector<int> s; int t1 = T/S + 1; for(int i=t1; i<=T; ++i) { if(changes[i].second==1) { is_off[changes[i].first] = 0; s.push_back(changes[i].first); } else is_off[changes[i].first] = 1; } sort(s.begin(), s.end(), [&](int i, int j) { return h[i] < h[j]; }); vector<int> ans; int i=0,j=0; while(i<f.size() && j<s.size()) { if(h[f[i]] < h[s[j]]) { ans.push_back(f[i]); ++i; } else { ans.push_back(s[j]); ++j; } } while(i<f.size()) { ans.push_back(f[i]); ++i; } while(j<s.size()) { ans.push_back(s[j]); ++j; } vector<int> nans; for(auto x : ans) if(!is_off[x]) nans.push_back(h[x]); for(int i=t1; i<=T; ++i) { is_off[changes[i].first] = 0; } return nans; } }; vector<Neigh> sasiad(M); void curseChanges(int U, int A[], int B[]) { for(int i=0; i<n; ++i) sasiad[i].init(); for(int t=0; t<U; ++t) { sasiad[A[t]].update(B[t],t+1); sasiad[B[t]].update(A[t],t+1); } for(int i=0; i<n; ++i) sasiad[i].finish(U); } int question(int X, int Y, int V) { vector<int> v1 = sasiad[X].getvec(V); // for(auto x : v1) cout << x << " "; cout << "\n"; // cout << "end\n"; exit(0); vector<int> v2 = sasiad[Y].getvec(V); // for(auto x : v2) cout << x << " "; cout << "\n"; if(v1.size()==0 || v2.size()==0) return 1e9; int idx = 0; int best = 1e9; for(auto x : v1) { while(idx < v2.size()-1 && v2[idx+1] < x) idx++; best = min(best, abs(x - v2[idx])); if(idx < v2.size() - 1) best = min(best, abs(x - v2[idx+1])); } return best; }