#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; #include "minerals.h" template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; int cnt = 0; bool put(int x) { int ocnt = cnt; cnt = Query(x); return cnt!=ocnt; } void cdq(vector<int> L, vector<int> R, bool l, bool r) { int n = L.size(); if(n==1) { Answer(L[0], R[0]); return; } if(n==2) { if(l) put(L[1]); else put(L[0]); if(put(R[1])) swap(R[0], R[1]); Answer(L[0], R[0]); Answer(L[1], R[1]); return; } int m = n/2; vector<int> L1, L2; for(int i=0; i<m; ++i) L1.push_back(L[i]); for(int i=m; i<n; ++i) L2.push_back(L[i]); if(l) { for(int i=m; i<n; ++i) put(L[i]); } else for(int i=0; i<m; ++i) put(L[i]); vector<int> R1, R2; for(int i=0; i<R.size(); ++i) { if(put(R[i])) R2.push_back(R[i]); else R1.push_back(R[i]); } /*cout << "\n"; for(auto x : L1) cout << x << " "; cout << "\n"; for(auto x : R1) cout << x << " "; cout << "\n"; cout << "\n"; for(auto x : L2) cout << x << " "; cout << "\n"; for(auto x : R2) cout << x << " "; cout << "\n";*/ cdq(L1, R1, 1, r^1); cdq(L2, R2, 0, r^1); } void Solve(int N) { vector<int> L; vector<int> R; for(int i=1; i<=2*N; ++i) { if(put(i)) L.push_back(i); else R.push_back(i); } cdq(L, R, 1, 1); }