利用并查集处理合并，并保存每个块对应的覆盖范围(在y轴上的)上下界；利用线段树（更新区间的范围从并查集维护的信息中得到）维护每个x.5的点对应的州数和城市数。区间修改单点查询，只要确定好x.5这些点在线段树中的对应的下标就可以了，我这里是x.5在线段树中下标为(x+1)。由于我写的是1-n的线段树写完了才发现题目说的0-n-1，只能把读进来的东西都++。具体的操作：对于road，先找两个点是否在一个块里，如果是了那就不用任何操作（画图可以看出来如果这俩是一个块里的那么他们覆盖范围之间一定已经有线了），否则先把这两个的分别的块对应的区域在线段树中减去他的影响，再将两个块合并之后，再在线段树中加上这一新块的影响。先减后加，这样就可以避免繁杂的分类讨论了。。。
第一版正经的线段树ac之后想了想感觉在这个情境下只需要保证叶子节点的信息有效就行了，推了一下感觉可以去掉maintain的操作。。。试了下果然可以，而且快了很多，在vjudge上已经是用线段树的跑的最快的了（前几名都是用的BIT emmm
wa的点：本来一气呵成写完很舒服但是没想到出了很多bug，因为一些愚蠢的bug调试了很久。。。。数据结构这块还是太弱了。
正经线段树代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const double eps = 1e-6;
const int maxn =1e6+5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
int state[maxn<<2],city[maxn<<2],lazy1[maxn<<2],lazy2[maxn<<2],miny[100005],maxy[100005],citynum[100005];
int pl,pr,as,ac;
void pushdown(int o)
{
lazy1[o<<1]+=lazy1[o],lazy1[o<<1|1]+=lazy1[o],lazy2[o<<1]+=lazy2[o],lazy2[o<<1|1]+=lazy2[o];
lazy1[o]=lazy2[o]=0;
}
void maintain(int o,int l,int r)
{
state[o]=lazy1[o]*(r-l+1);
city[o]=lazy2[o]*(r-l+1);
if(r>l)//error4 final error
state[o]=state[o<<1]+state[o<<1|1],city[o]=city[o<<1]+city[o<<1|1];
}
void update(int o,int l,int r)
{
if(pl<=l&&r<=pr)
{
lazy1[o]+=as,lazy2[o]+=ac;
}
else if(l<r)
{
int m=(l+r)>>1;
pushdown(o);
if(pl<=m)update(o<<1,l,m);else maintain(o<<1,l,m);
if(m<pr)update(o<<1|1,m+1,r);else maintain(o<<1|1,m+1,r);
}
maintain(o,l,r);
}
int qp,res1,res2;
void query(int o,int l,int r)
{
maintain(o,l,r);
if(l==qp&&l==r)
{
res1=state[o],res2=city[o];
res1=lazy1[o],res2=lazy2[o];
}
else
{
int m=(l+r)>>1;
pushdown(o);
if(qp<=m)query(o<<1,l,m);else maintain(o<<1,l,m);
if(m<qp) query(o<<1|1,m+1,r);else maintain(o<<1|1,m+1,r);
}
}
void buid(int o,int l,int r)
{
if(l==r)
{
lazy1[o]=lazy2[o]=state[o]=city[o]=0;
return ;
}
else
{
int m=(l+r)>>1;
buid(o<<1,l,m);
buid(o<<1|1,m+1,r);
state[o]=city[o]=lazy1[o]=lazy2[o]=0;
}
}
int pa[100005];
int findset(int x){return x==pa[x]?x:(pa[x]=findset(pa[x]));}
int mmy,miy;
void work(int x,int y)
{
int fx=findset(x),fy=findset(y);
if(fx!=fy)//不属于同一个块的话就三步：先减去两个各自的影响（只有当这个东西在y轴上范围超过1的时候才有影响）然后合并并查集，最后加上合并后的新块的影响
{
if(maxy[fx]>miny[fx]){pl=miny[fx]+1,pr=maxy[fx],as=-1,ac=-citynum[fx];update(1,1,mmy);}//error2 more than two points are collinear
if(maxy[fy]>miny[fy]){pl=miny[fy]+1,pr=maxy[fy],as=-1,ac=-citynum[fy];update(1,1,mmy);}//error1 fx->fy
miny[fx]=min(miny[fx],miny[fy]),maxy[fx]=max(maxy[fx],maxy[fy]),citynum[fx]+=citynum[fy];citynum[fy]=0;pa[fy]=fx;
if(maxy[fx]>miny[fx]){pl=miny[fx]+1,pr=maxy[fx],as=1,ac=citynum[fx];update(1,1,mmy);}//error3
}
}
void read(int &x)
{
x=0;char s=getchar();
while(s<'0'||s>'9'){s=getchar();}
while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
}
int main()
{
int t,n,m,a,b;char op[10];double tmp;
scanf("%d",&t);
while(t--)
{
mmy=0,miy=INF;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&a,&b);a++,b++;
citynum[i]=1,pa[i]=i,maxy[i]=miny[i]=b,mmy=max(mmy,b);//,miy=min(miy,b);
}
buid(1,1,mmy);
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
scanf("%s",op);
if(op[0]=='r')
{
scanf("%d%d",&a,&b);a++,b++;
work(a,b);
}
else
{
scanf("%lf",&tmp);
qp=(int)(tmp+1.5);
if(qp>mmy)
{
puts("0 0");continue;
}
query(1,1,mmy);
printf("%d %d\n",res1,res2);
}
}
}
return 0;
}
改过之后：（开了一点小挂因为我发现榜前dalao都开2333）
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const double eps = 1e-6;
const int maxn =1e6+5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
int state[maxn<<2],city[maxn<<2],lazy1[maxn<<2],lazy2[maxn<<2],miny[100005],maxy[100005],citynum[100005];
int pl,pr,as,ac;
void pushdown(int o)
{
lazy1[o<<1]+=lazy1[o],lazy1[o<<1|1]+=lazy1[o],lazy2[o<<1]+=lazy2[o],lazy2[o<<1|1]+=lazy2[o];
lazy1[o]=lazy2[o]=0;
}
//There is no need to use maintain/pushup
void update(int o,int l,int r)
{
if(pl<=l&&r<=pr)
lazy1[o]+=as,lazy2[o]+=ac;
else if(l<r)
{
int m=(l+r)>>1;
pushdown(o);
if(pl<=m)update(o<<1,l,m);
if(m<pr)update(o<<1|1,m+1,r);
}
}
int qp,res1,res2;
void query(int o,int l,int r)
{
if(l==qp&&l==r)
res1=lazy1[o],res2=lazy2[o];
else
{
int m=(l+r)>>1;
pushdown(o);
if(qp<=m)query(o<<1,l,m);
if(m<qp) query(o<<1|1,m+1,r);
}
}
void buid(int o,int l,int r)
{
if(l==r)
{
lazy1[o]=lazy2[o]=state[o]=city[o]=0;
return ;
}
else
{
int m=(l+r)>>1;
buid(o<<1,l,m);
buid(o<<1|1,m+1,r);
state[o]=city[o]=lazy1[o]=lazy2[o]=0;
}
}
int pa[100005];
int findset(int x){return x==pa[x]?x:(pa[x]=findset(pa[x]));}
int mmy,miy;
void work(int x,int y)
{
int fx=findset(x),fy=findset(y);
if(fx!=fy)
{
if(maxy[fx]>miny[fx]){pl=miny[fx]+1,pr=maxy[fx],as=-1,ac=-citynum[fx];update(1,1,mmy);}
if(maxy[fy]>miny[fy]){pl=miny[fy]+1,pr=maxy[fy],as=-1,ac=-citynum[fy];update(1,1,mmy);}
miny[fx]=min(miny[fx],miny[fy]),maxy[fx]=max(maxy[fx],maxy[fy]),citynum[fx]+=citynum[fy];citynum[fy]=0;pa[fy]=fx;
if(maxy[fx]>miny[fx]){pl=miny[fx]+1,pr=maxy[fx],as=1,ac=citynum[fx];update(1,1,mmy);}
}
}
void read(int &x)
{
x=0;char s=getchar();
while(s<'0'||s>'9'){s=getchar();}
while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
}
int main()
{
int t,n,m,a,b;char op[10];double tmp;
read(t);
while(t--)
{
mmy=0,miy=INF;
read(n);
for(int i=1;i<=n;i++)
{
read(a),read(b);a++,b++;
citynum[i]=1,pa[i]=i,maxy[i]=miny[i]=b,mmy=max(mmy,b);
}
buid(1,1,mmy);
read(m);
for(int i=1;i<=m;i++)
{
scanf("%s",op);
if(op[0]=='r')
{
read(a),read(b);a++,b++;
work(a,b);
}
else
{
scanf("%lf",&tmp);
qp=(int)(tmp+1.5);
if(qp>mmy)
{
puts("0 0");continue;
}
query(1,1,mmy);
printf("%d %d\n",res1,res2);
}
}
}
return 0;
}