题目链接

【题意】

平面上有n个城市，初始时城市之间没有任何双向道路相连，你的任务是依次执行以下指令

road A B 在城市A,B之间建立一条双向道路，保证这条道路不和其它道路在非端点处相交

line C 询问一条y=C的水平线和多少个州相交，以及这些州一共包含多少个城市，在任意时刻，每一组连通的城市形成一个州，保证C的小数部分为0.5

【输入格式】

多组输入，第一行为数据组数T. 每组数据第一行为一个整数n（1<=n<=1e5）代表城市数量，以下n行每行两个整数x,y（0 <= x,y <= 1e6）城市编号为0~n-1. 下一行为指令总数m（1<=m<=200000）以下m行每行一条指令，其中A,B为不同的整数且0<=A< B< N， C是小数部分保证为0.5的实数，且0 < C <1000000. 不会有两条道路连接相同的城市，每组数据至少有一条line指令

【输出格式】

对于每条line指令，输出y=C穿过的州的数目以及这些州包含的城市总数

【思路】

把每个城市抽象成点，题目中的州其实就是一个连通块，我们可以用并查集来维护一个连通块的信息，我们需要维护一个连通块中城市的数目，还有就是纵坐标的最大值和最小值以便进行合并。而合并操作又可以借助于线段树来完成，首先可以将坐标统一乘以2使得坐标值均为整数，之后对y轴上的每一个点抽象成线段树的一个叶子结点，线段树叶子结点维护2个信息，即这一点的坐标穿过的州的数量和对应城市的数量（非叶结点这两个值是无意义的）合并两个连通块的过程其实是把原来的两个连通块删掉，加入合并后的新连通块。比如在合并两个连通块A和B的时候，首先把A,B原来各自的区间对应的州的数量减1，城市数量减去自己的城市数量，然后在合并后的新的区间中使得州的数量加1，城市数量加上A,B城市的总数量.可以用lazy标记维护区间和来实现区间更新，最后单点查询即可因为只有叶子结点的信息有意义.

#include
    
     #define node tree[id]#define lson tree[id<<1]#define rson tree[id<<1|1]using namespace std;const int maxn=1000005;const int maxm=2000050;struct Tree{    int left,right;    int num,city;    int lazy1,lazy2;};int n,m;int par[maxn];int maxy[maxn],miny[maxn],cnt[maxn];int x[maxn],y[maxn];Tree tree[maxm<<2];void init(){    for(int i=0;i<=n;++i) par[i]=i;    memset(maxy,0,sizeof(maxy));    memset(miny,0,sizeof(miny));    memset(cnt,0,sizeof(cnt));}int find(int x){ return x==par[x]?x:par[x]=find(par[x]); }void pushup(int id){    node.num=lson.num+rson.num;    node.city=lson.city+rson.city;}void pushdown(int id){    if(node.lazy1 && node.left!=node.right){        lson.lazy1+=node.lazy1;        lson.num+=(lson.right-lson.left+1)*node.lazy1;        rson.lazy1+=node.lazy1;        rson.num+=(rson.right-rson.left+1)*node.lazy1;        node.lazy1=0;    }    if(node.lazy2 && node.left!=node.right){        lson.lazy2+=node.lazy2;        lson.city+=(lson.right-lson.left+1)*node.lazy2;        rson.lazy2+=node.lazy2;        rson.city+=(rson.right-rson.left+1)*node.lazy2;        node.lazy2=0;    }}void build(int id,int le,int ri){    node.left=le;    node.right=ri;    node.num=node.city=0;    node.lazy1=node.lazy2=0;    if(le==ri) return;    int mid=(le+ri)>>1;    build(id<<1,le,mid);    build(id<<1|1,mid+1,ri);}void update(int id,int le,int ri,int a,int b){    if(node.left==le && node.right==ri){        node.lazy1+=a;        node.num+=(node.right-node.left+1)*a;        node.lazy2+=b;        node.city+=(node.right-node.left+1)*b;        return;    }    pushdown(id);    int mid=(node.left+node.right)>>1;    if(ri<=mid) update(id<<1,le,ri,a,b);    else if(le>mid) update(id<<1|1,le,ri,a,b);    else{        update(id<<1,le,mid,a,b);        update(id<<1|1,mid+1,ri,a,b);    }    pushup(id);}int query(int id,int pos){    if(node.left==node.right) return id;    pushdown(id);    int mid=(node.left+node.right)>>1;    if(pos<=mid) return query(id<<1,pos);    else return query(id<<1|1,pos);}int main(){    //freopen("in.txt","r",stdin);    //freopen("out2.txt","w",stdout);    int T;    scanf("%d",&T);    while(T--){        scanf("%d",&n);        init();        int maxr=0;        for(int i=0;i
     
      maxr) puts("0 0");                else{                    int id=query(1,p);                    printf("%d %d\n",node.num,node.city);                }            }        }    }    return 0;}