cartesian.cpp

#include <bits/stdc++.h>
using namespace std;
typedef int64_t ll;
template<typename T> inline void _max(T& a, T b){ a = max(a,b); }
template<typename T> inline void _min(T& a, T b){ a = min(a,b); }

const int N = 1e6+7;
int x[N], f[N], y[N], T[N][2];
int s[2], ts;
void split(int t, int k){
    if(!t) return (void)(s[0] = s[1] = 0);
    bool d = x[t] < k;
    split(T[t][d], k); T[t][d] = s[!d]; s[!d] = t;
}
int merge(int tl, int tr){
    int r;
    if(!min(tl,tr)) return max(tl, tr);
    if(y[tl] < y[tr]) T[r=tr][0] = merge(tl, T[tr][0]);
    else              T[r=tl][1] = merge(T[tl][1], tr);
    return r;
}