LA 4730 Kingdom 线段树+并查集

超、凢脫俗 2022-01-22 23:19 176阅读 0赞

## 题意：有T组測试数据。每组数据的N表示有N个城市，接下来的N行里每行给出每一个城市的坐标(0<=x,y<=1000000)，然后有M(1<M<200000)个操作，操作有两类，（1）"road A B"，表示将城市A和城市B通过一条道路连接，假设A和B原来属于不同的城市群。经过这个操作。A和B就在一个城市群里了。保证每条道路不会和其它道路相交（除了端点A和B）。（2）"line C"。表示查询当穿过y=C的直线，有多少个城市群、这几个城市群一共同拥有多少个城市。 ##

## 思路：线段树加并查集，可以把每个城市的x坐标忽略，把纵坐标看做线段树的区间，一个点就相当于更新区间\[y,y\]，一条线就相当于更新区间\[y1,y2\]，每次查询y=C相当于查点C，那么这题转化成区间更新，求点的线段树问题，如果有多个点连接成一个图，那么只要这个图包含最大的纵坐标和最小的纵坐标当成区间去更新即可，那么这个图有多少个城市呢，就需要用并查集算法来记录。如果连接A,B，那么用并查集路径压缩找到A,B的根节点，如果同根，不需要更新，不同根，从线段树中删除这两个点的信息，然后把这两个点的根节点相连并更新新的根节点的节点数以及区间的范围，然后再把新的根节点插入线段树即可。这样是为了防止重复更新出错，画个草图就明白了。 ##

## 参考博客：[https://blog.csdn.net/ccsu\_cat/article/details/80861228][https_blog.csdn.net_ccsu_cat_article_details_80861228] ##

## 代码： ##

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int maxn=1e5+5;
    struct node
    {
    	int y1,y2,sum,to;
    }a[maxn];
    int sum1[maxn*60],sum2[maxn*60],ans1,ans2;
    
    void build(int l,int r,int o)
    {
    	if(l==r)
    	{
    		sum1[o]=sum2[o]=0;
    		return;
    	}
    	int m=(l+r)/2;
    	build(l,m,o*2);
    	build(m+1,r,o*2+1);
    	sum1[o]=sum2[o]=0;
    }
    void update(int l,int r,int o,int k,int flag)
    {
    	if(l>=a[k].y1&&r<=a[k].y2)
    	{
    		if(flag==1)///flag=1插入，否则删除
    		{
    			sum1[o]++;///更新线段覆盖的y坐标区间 方便统计洲的数量
    			sum2[o]+=a[k].sum;///并查集记录集合大小
    		}
    		else
    		{
    			sum1[o]--;
    			sum2[o]-=a[k].sum;
    		}
    		return;
    	}
    	int m=(l+r)/2;
    	if(a[k].y1<=m)
    	update(l,m,o*2,k,flag);
    	if(a[k].y2>m)
    	update(m+1,r,o*2+1,k,flag);
    }
    ///并查集压缩路径
    int find(int x){
    	if(a[x].to!=x)
    	a[x].to=find(a[x].to);
    	return a[x].to;
    }
    void query(int l,int r,int o,int C)
    {
    	ans1+=sum1[o];/// 记录洲的数量
    	ans2+=sum2[o];/// 记录每个洲的点的数量
    	if(l==r) return;
    	int m=(l+r)/2;
    	if(C<=m) query(l,m,o*2,C);
    	else query(m+1,r,o*2+1,C);
    }
    int main()
    {
    	int T;
    	scanf("%d",&T);
    	while(T--)
    	{
    		int i,n,l=2e6,r=0;
    		float t1,t2;
    		scanf("%d",&n);
    		for(i=0;i<n;i++)
    		{
    			scanf("%f%f",&t1,&t2);
    			a[i].y1=a[i].y2=t2*2;///y坐标转换为整数
    			a[i].sum=1;
    			a[i].to=i;
    			l=min(a[i].y2,l);
    			r=max(a[i].y2,r);
    		}
    		build(l,r,1);
    		for(i=0;i<n;i++)
    		update(l,r,1,i,1);
    		int q,A,B,C;
    		char s[10];
    		scanf("%d",&q);
    		while(q--)
    		{
    			scanf("%s",s);
    			if(s[0]=='r')
    			{
    				scanf("%d%d",&A,&B);
    				A=find(A);
    				B=find(B);
    				if(A==B)
    				continue;
    				update(l,r,1,A,2);
    				update(l,r,1,B,2);
    				a[B].sum+=a[A].sum;///合并并查集
    				a[B].y2=max(a[B].y2,a[A].y2); ///y2表示线段y坐标的最大值
    				a[B].y1=min(a[B].y1,a[A].y1); ///y1表示线段y坐标的最小值
    				a[A].to=B;///合并并查集
    				update(l,r,1,B,1);
    			}
    			else
    			{
    				scanf("%f",&t1);
    				C=t1*2;
    				if(C<l||C>r)
    				{
    					printf("0 0\n");
    					continue;
    				}
    				ans1=ans2=0;
    				query(l,r,1,C);
    				printf("%d %d\n",ans1,ans2);
    			}
    		}
    	}
    	return 0;
    }

[https_blog.csdn.net_ccsu_cat_article_details_80861228]: https://blog.csdn.net/ccsu_cat/article/details/80861228