#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 = 5; set<pair<int, int>> secik; vector<vector<pair<int, 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({h[x], x})==secik.end()) { changes.push_back({x,1}); secik.insert({h[x], x}); } else { changes.push_back({x,-1}); secik.erase({h[x], x}); } if((changes.size()-1)%S == 0) { vector<pair<int, int>> reb; for(auto x : secik) reb.push_back(x); save.push_back(reb); } } void finish(int t) { vector<pair<int, 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[a,b] : save.back()) ans.push_back(a); return ans; } T = upper_bound(ztime.begin(), ztime.end(), T) - ztime.begin() - 1; if(T%S==0) { vector<int> ans; for(auto[a,b] : save[T/S]) ans.push_back(a); return ans; } vector<pair<int, int>> f = save[T/S]; vector<pair<int, 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({h[changes[i].first], changes[i].first}); } else is_off[changes[i].first] = 1; } sort(s.begin(), s.end()); vector<int> ans; int i=0,j=0; while(i<f.size() && j<s.size()) { if(is_off[f[i].second]) { ++i; continue; } if(is_off[s[j].second]) { ++j; continue; } if(f[i] < s[j]) { ans.push_back(f[i].first); ++i; } else { ans.push_back(s[j].first); ++j; } } while(i<f.size()) { if(!is_off[f[i].second]) ans.push_back(f[i].first); ++i; } while(j<s.size()) { if(!is_off[s[j].second]) ans.push_back(s[j].first); ++j; } for(int i=t1; i<=T; ++i) { is_off[changes[i].first] = 0; } return ans; } }; 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; }