题目描述
平面有 \(n\) 个城市，初始时城市之间没有任何双向道路连接。你的任务是依次执行以下任务：
road A B:在城市 \(A\) 和城市 \(B\) 之间连接一条双向道路，保证这条道路不和其他道路在非端点处相交。
line C：询问一条 \(y=C\) 的水平线和多少个州相交，以及这些州一共包含几个城市。在任意时刻，每一组连接的城市形成一个州。在本指令中，\(C\) 的小数部分保证为 \(0.5\)。
输入格式
输入第一行为数据组 \(T\)。
每组数据第一行为一个整数 \(n\)。
以下 \(n\) 行每行两个整数 \(x,y\),即各城市坐标。城市编号为 \(0\sim n-1\)。
下一行为指令总数 \(m\) 。
以下 \(m\) 行每行一条指令，其中 \(A,B\) 为不同的整数，且 \(0\le A,B<n\) ；\(C\) 是小数部分保证为 \(0.5\) 的实数，且 \(0<C<1000000\)。不会有两条道路连接一对相同的城市。
每组数据至少有一条line指令。
输出格式
对于每条line指令，输出 \(y=C\) 穿过的州的数目和这些州包含的城市总数
样例输入
3
10
1 7
5 7
8 6
3 5
5 5
2 3
10 3
7 2
4 1
11 1
11
road 0 1
road 3 5
line 6.5
road 4 2
road 3 8
road 4 7
road 6 9
road 4 1
road 2 7
line 4.5
line 6.5
1
100 100
1
line 100.5
2
10 10
20 20
2
road 0 1
line 15.5
样例输出
0 0
2 8
1 5
0 0
1 2
提示
\(1\le n\le 100000\)
\(0\le x,y\le 1000000\)
\(1\le m\le 200000\)
分析题目，由于询问的直线与 x 轴平行，所以答案实际上与每个点的 x 坐标无关，仅与 y 有关。
那么问题便从坐标系上变到了 y 轴上，也就变成了区间问题。
区间问题比较好的维护方式就是线段树，接着开始分析这属于线段树的哪一类问题。
询问的时候，因为我们把问题转换到了坐标轴上，所以询问从直线变成了点，那这肯定是单点查询，但是这个点不在整点上，很难考虑，不难想到转换一下坐标轴。
一开始，线段树维护的应该是有多少个州包含坐标 \(p\)，而现在则转换成有多少个州包含区间 \([p-1,p)\)。
接着看如何处理连接两个城市。
首先我们知道，连接两个城市 \(A\) 和 \(B\) 实际上和连接与 \(A\) 和 \(B\) 分别同州的城市是等价的。
那么便可以考虑给每个州设立一个代表，每次要连接两个城市，就连接两个城市同州的代表。
这很明显就是并查集。
现在问题便是如何将连接城市呈现在线段树上，当连接两个城市时，可以先把两个城市的所在州在线段树上的区间删去，变成一个大洲以后再把这个大洲在线段树上的区间恢复回去就可以了，而这些操作都是区间修改。
区间修改，单点查询，这个用树状数组就够了。
那么代码也很容易写出来了。
（最后说一句，由于输出不仅要输出州个数，还要输出城市个数，所以需要两个树状数组）
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,mxy;
const int N=1e5+5,MX=1e6+5;;
int low[N],high[N],siz[N];
struct DSU{
int fa[N];
void init(){
for(int i=0;i<n;i++) fa[i]=i;
return ;
}
int find(int x){
if(fa[x]==x) return x;
fa[x]=find(fa[x]);
return fa[x];
}
void merge(int x,int y){
int fx=find(x),fy=find(y);
if(fx!=fy) fa[fx]=fy;
}
}city;
struct BIT{
int tree[MX];
int lowbit(int x){
return x&-x;
}
void init(){
for(int i=1;i<=mxy;i++) tree[i]=0;
return ;
}
void add(int key,int x){
while(key<=mxy+1){
tree[key]+=x;
key+=lowbit(key);
}
return ;
}
int ask(int key){
int ans=0;
while(key>0){
ans+=tree[key];
key-=lowbit(key);
}
return ans;
}
};
BIT cnt,sum;
void change(int key){
cnt.add(low[key]+1,-1);
cnt.add(high[key]+1,1);
sum.add(low[key]+1,-siz[key]);
sum.add(high[key]+1,siz[key]);
return ;
}
signed main()
{
int t;scanf("%lld",&t);
while(t--){
scanf("%lld",&n);
mxy=0;
city.init();
for(int i=0;i<n;i++){
int x,y;
scanf("%lld%lld",&x,&y);
mxy=max(mxy,y);
low[i]=high[i]=y;
siz[i]=1;
}
cnt.init();
sum.init();
scanf("%lld",&m);
while(m--){
char s[100];
scanf("%s",s);
if(s[0]=='r'){
int a,b;
scanf("%lld%lld",&a,&b);
int fa=city.find(a),fb=city.find(b);
if(fa==fb) continue;
change(fa);
change(fb);
city.merge(fa,fb);
low[fa]=low[fb]=min(low[fa],low[fb]);
high[fa]=high[fb]=max(high[fa],high[fb]);
siz[fa]=siz[fb]=siz[fa]+siz[fb];
cnt.add(low[fa]+1,1);
cnt.add(high[fa]+1,-1);
sum.add(low[fa]+1,siz[fa]);
sum.add(high[fa]+1,-siz[fa]);
}
else{
double x;scanf("%lf",&x);
int a=(int)x+1;
printf("%lld %lld\n",cnt.ask(a),sum.ask(a));
}
}
}
return 0;
}