题意：训练指南P248
分析：第一个操作可以用并查集实现，保存某集合的最小高度和最大高度以及城市个数。运用线段树成端更新来统计一个区间高度的个数，此时高度需要离散化。这题两种数据结构一起使用，联系紧密。
#include <bits/stdc++.h>
using namespace std; const int N = 1e5 + 5;
const int M = 3 * N;
const int INF = 0x3f3f3f3f;
struct Point {
int x, y;
Point() {}
Point(int x, int y) : x (x), y (y) {}
};
struct Query {
int op;
int u, v, w;
}q[2*N]; #define lson l, mid, o << 1
#define rson mid + 1, r, o << 1 | 1
int city[M<<2], num[M<<2], col[M<<2], col2[M<<2]; //Segment_Tree
void push_down(int o) {
if (col[o]) {
col[o<<1] += col[o]; col[o<<1|1] += col[o];
city[o<<1] += col[o]; city[o<<1|1] += col[o];
col[o] = 0;
}
if (col2[o]) {
col2[o<<1] += col2[o]; col2[o<<1|1] += col2[o];
num[o<<1] += col2[o]; num[o<<1|1] += col2[o];
col2[o] = 0;
}
}
void build(int l, int r, int o) {
col[o] = 0; col2[o] = 0;
if (l == r) {
city[o] = num[o] = 0;
return ;
}
int mid = l + r >> 1;
build (lson); build (rson);
}
void updata(int ql, int qr, int c1, int c2, int l, int r, int o) {
if (ql <= l && r <= qr) {
col[o] += c1; col2[o] += c2;
city[o] += c1; num[o] += c2;
return ;
}
push_down (o);
int mid = l + r >> 1;
if (ql <= mid) updata (ql, qr, c1, c2, lson);
if (qr > mid) updata (ql, qr, c1, c2, rson);
}
void query(int p, int l, int r, int o) {
if (l == r && l == p) {
printf ("%d %d\n", city[o], num[o]); return ;
}
push_down (o);
int mid = l + r >> 1;
if (p <= mid) query (p, lson);
else query (p, rson);
} int n, m, bound; int rt[N], rk[N], maxy[N], miny[N]; //DSU
void init(void) {
memset (rt, -1, sizeof (rt));
memset (rk, 0, sizeof (rk));
}
int Find(int x) {
return rt[x] == -1 ? x : rt[x] = Find (rt[x]);
}
void Union(int u, int v) {
u = Find (u); v = Find (v);
if (u == v) return ;
if (rk[u] > rk[v]) swap (u, v);
if (rk[u]) updata (miny[u], maxy[u], -1, -(rk[u] + 1), 1, bound, 1);
if (rk[v]) updata (miny[v], maxy[v], -1, -(rk[v] + 1), 1, bound, 1); maxy[v] = max (maxy[v], maxy[u]);
miny[v] = min (miny[v], miny[u]); rt[u] = v; rk[v] += rk[u] + 1;
rk[u] = 0;
updata (miny[v], maxy[v], 1, rk[v] + 1, 1, bound, 1);
} Point point[N];
vector<int> ys; void run(void) {
init (); build (1, bound, 1);
for (int i=1; i<=n; ++i) {
miny[i] = maxy[i] = point[i].y;
}
for (int i=1; i<=m; ++i) {
if (q[i].op == 0) {
Union (q[i].u, q[i].v);
}
else {
query (q[i].w, 1, bound, 1);
}
}
} int main(void) {
int T; scanf ("%d", &T);
while (T--) {
scanf ("%d", &n);
int x, y;
ys.clear ();
for (int i=1; i<=n; ++i) {
scanf ("%d%d", &x, &y); point[i] = Point (x, 2 * y);
ys.push_back (point[i].y);
}
char str[10];
int u, v; double t;
scanf ("%d", &m);
for (int i=1; i<=m; ++i) {
scanf ("%s", &str);
if (str[0] == 'r') {
scanf ("%d%d", &u, &v);
q[i].op = 0; q[i].u = u + 1, q[i].v = v + 1;
}
else if (str[0] == 'l') {
scanf ("%lf", &t);
q[i].op = 1; q[i].w = (int) (2 * t);
ys.push_back (q[i].w);
}
}
sort (ys.begin (), ys.end ());
ys.erase (unique (ys.begin (), ys.end ()), ys.end ());
bound = 200010;
for (int i=1; i<=n; ++i) {
point[i].y = lower_bound (ys.begin (), ys.end (), point[i].y) - ys.begin () + 1;
}
for (int i=1; i<=m; ++i) {
if (q[i].op == 1) {
q[i].w = lower_bound (ys.begin (), ys.end (), q[i].w) - ys.begin () + 1;
}
}
run ();
} return 0;
}