分析
直线都是\(y=\overline{a.5}\)这种形式，而只查询州和城市的个数，所以很容易想到对\(y\)轴做投影，然后转化为区间修改（加减）和单点查询，可以用线段树维护。至于每个州只会合并不会分裂，大小肯定是只增不减的，所以用并查集维护很方便。
算法流程
线段树维护区间的州和城市的个数，以及它们的标记。
并查集要维护它的大小，纵坐标范围。
- road A B：如果A、B本身同属一个州就不管，因为肯定有覆盖A、B纵坐标的路连接它们两个。否则先撤销A、B所属州对线段树的贡献，然后合并两个州，最后把并集的贡献加到线段树上。
- line C:我规定线段树上\([i,i]\)节点管辖\(y\)轴上\([i,i-1]\)区间，也就是\(y=\overline{(i-1).5}\)这条直线。那么此操作相当于查询\([C+0.5,C+0.5]\)这个节点。
时间复杂度
建树复杂度\(O(n\log n)\)。单次操作无论是road A B还是line C都是\(O(\log n)\)的，而有\(m\)次操作，所以总时间复杂度为\(O(n\log n+m \log n)\)。
代码
#include<iostream>
#include<cstdio>
#define reg register
#pragma GCC optimize(3)
template<typename T>T read(T&x)
{
T data=0;
int w=1;
char ch=getchar();
while(ch!='-'&&!isdigit(ch))
ch=getchar();
if(ch=='-')
w=-1,ch=getchar();
while(isdigit(ch))
data=data*10+ch-'0',ch=getchar();
return x=data*w;
}
using namespace std;
const int MAXN=1e5+1,MAXY=1e6+1;
struct SegTree // leaf node i controls y=i->(i-1)
{
int sums,sumc;
int adds,addc;
}ST[MAXY<<2];
#define root ST[o]
#define lson ST[o<<1]
#define rson ST[o<<1|1]
inline void pushup(int o)
{
root.sums=lson.sums+rson.sums;
root.sumc=lson.sumc+rson.sumc;
}
void build(int o,int l,int r)
{
if(l==r)
{
root.sums=root.sumc=0;
root.adds=root.addc=0;
return;
}
int mid=(l+r)>>1;
build(o<<1,l,mid);
build(o<<1|1,mid+1,r);
pushup(o);
root.adds=root.addc=0;
}
inline void pushdown(int o,int l,int r)
{
int mid=(l+r)>>1;
if(root.adds)
{
lson.sums+=root.adds*(mid-l+1),
lson.adds+=root.adds;
rson.sums+=root.adds*(r-mid),
rson.adds+=root.adds;
root.adds=0;
}
if(root.addc)
{
lson.sumc+=root.addc*(mid-l+1),
lson.addc+=root.addc;
rson.sumc+=root.addc*(r-mid),
rson.addc+=root.addc;
root.addc=0;
}
}
void addrg(int o,int l,int r,int ql,int qr,int state,int city)
{
if(ql<=l&&r<=qr)
{
root.sums+=state*(r-l+1),
root.adds+=state;
root.sumc+=city*(r-l+1),
root.addc+=city;
return;
}
pushdown(o,l,r);
int mid=(l+r)>>1;
if(ql<=mid)
addrg(o<<1,l,mid,ql,qr,state,city);
if(qr>=mid+1)
addrg(o<<1|1,mid+1,r,ql,qr,state,city);
pushup(o);
}
SegTree querypt(int o,int l,int r,int q)
{
if(l==r)
return root;
pushdown(o,l,r);
int mid=(l+r)>>1;
if(q<=mid)
return querypt(o<<1,l,mid,q);
else if(q>=mid+1)
return querypt(o<<1|1,mid+1,r,q);
}
struct Point
{
int x,y;
}P[MAXN];
typedef Point Range;
int fa[MAXN],sz[MAXN];
Range rg[MAXN]; // y=x->y(x<y)
int find(int x)
{
return fa[x]==x?x:fa[x]=find(fa[x]);
}
inline void unite(int x,int y)
{
int fx=find(x),fy=find(y);
if(fx==fy) return;
if(rg[fx].x+1<=rg[fx].y)
{
addrg(1,1,1e6,rg[fx].x+1,rg[fx].y,-1,-sz[fx]);
}
if(rg[fy].x+1<=rg[fy].y)
{
addrg(1,1,1e6,rg[fy].x+1,rg[fy].y,-1,-sz[fy]);
}
sz[fy]+=sz[fx],sz[fx]=0;
fa[fx]=fy;
rg[fy].x=min(rg[fy].x,rg[fx].x),rg[fy].y=max(rg[fy].y,rg[fx].y);
if(rg[fy].x+1<=rg[fy].y)
{
addrg(1,1,1e6,rg[fy].x+1,rg[fy].y,1,sz[fy]);
}// ->segtree bomb
}
int main()
{
int T;
read(T);
while(T--)
{
build(1,1,1e6);
int n;
read(n);
for(reg int i=0;i<n;++i)
{
read(P[i].x);read(P[i].y);
fa[i]=i;
sz[i]=1;
rg[i].x=rg[i].y=P[i].y;
}
int m;
read(m);
for(reg int i=1;i<=m;++i)
{
char opt[10];
scanf("%s",opt);
if(opt[0]=='r')
{
int A,B;
read(A);read(B);
unite(A,B);
}
else if(opt[0]=='l')
{
double C;
scanf("%lf",&C);
C+=0.5;
SegTree t=querypt(1,1,1e6,C);
printf("%d %d\n",t.sums,t.sumc);
}
}
}
}
Hint
线段树大小还可以继续优化。