319E - Ping-Pong - CodeForces Solution

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#define lson p << 1
#define rson p << 1 | 1
using namespace std;
const int N = 1e5 + 5;

int n, tot, lsh[N << 1];

int fa[N], ml[N], mr[N];
int find(int u) {return fa[u] == u ? u : fa[u] = find(fa[u]);}

struct quest {
	int op, x, y;
} a[N];

vector<int> vec[N << 3];
void update(int p, int L, int R, int x, int d) {
	if (!vec[p].empty()) {
		for (auto i : vec[p]) {
			int fx = find(i);
			fa[fx] = d, ml[d] = min(ml[d], ml[fx]), mr[d] = max(mr[d], mr[fx]);
		}
		vec[p].clear(), vec[p].push_back(d);
	}
	if (L == R) return;
	int mid = L + R >> 1;
	if (x <= mid) update(lson, L, mid, x, d);
	else update(rson, mid + 1, R, x, d);
}
void ins(int p, int L, int R, int l, int r, int d) {
	if (l <= L && r >= R) return vec[p].push_back(d), void();
	int mid = L + R >> 1;
	if (l <= mid) ins(lson, L, mid, l, r, d);
	if (r > mid) ins(rson, mid + 1, R, l, r, d);
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d %d %d", &a[i].op, &a[i].x, &a[i].y);
		if (a[i].op & 1) lsh[++tot] = a[i].x, lsh[++tot] = a[i].y;
	}
	sort(lsh + 1, lsh + 1 + tot);
	for (int i = 1, j = 0; i <= n; i++) {
		int op = a[i].op, x = a[i].x, y = a[i].y;
		if (op & 1) {
			x = lower_bound(lsh + 1, lsh + 1 + tot, x) - lsh;
			y = lower_bound(lsh + 1, lsh + 1 + tot, y) - lsh;
			j++, fa[j] = j, ml[j] = x, mr[j] = y;
			update(1, 1, tot, x, j), update(1, 1, tot, y, j);
			if (x + 1 <= y - 1) ins(1, 1, tot, x + 1, y - 1, j);
		}
		else {
			int fx = find(x), fy = find(y);
			if (fx == fy) {puts("YES"); continue;}
			if (ml[fx] > ml[fy] && ml[fx] < mr[fy] || mr[fx] > ml[fy] && mr[fx] < mr[fy]) puts("YES");
			else puts("NO");
		}
	}
	return 0;
}