程序员人生 网站导航

UVALive 4730 线段树+并查集

栏目：php教程时间：2016-06-07 08:42:37

点击打开链接

题意：在座标上给n个点，r的操作是将两个点连起来，l的操作是问你y=u的这条线连接的集合块数和这些集合内的点的个数

思路：很麻烦的1道题，在网上看了题意和做法后，开始了1下午的调bug进程，做法很好懂，我开了两个线段树，1个保护点代表的直线的集合个数，另外一个则是途经集合内的点的个数，然后集合的判断直接用并查集就好了，这是两个核心，然后就是自己瞎写的了，代码丑的可以而且好像除本人他人看着可能要骂人了，有兴趣研究的可以留言我来解答，那难的部份其实就是并查集合并时该怎样将这两个要保护的值弄进线段树中，而且这题我用的离散化处理的，好像可以不用，但感觉空间上有点过意不去，所以代码看着真是丑，然后说说合并的操作，先是集合的个数，令左侧上下限分别为L1,R1,右侧上限是L2，R2，下面都是这样，然后L1到R1的集合个数全部减1，也就是区间更新，然后R1到R2也是1样，然后全部大区间+1，现在看若左侧区间个数是1，右侧也是1，那末合并后还是1，第2个线段树的操作与这个相似，统计1下就能够了，注意细节，这里献上9野聚聚的样例，也是这个样例终结了我1下午的找BUG旅程

  1. 3  
  2. 11 
  3. 1 7  
  4. 5 7  
  5. 8 6  
  6. 3 5  
  7. 5 5  
  8. 2 3  
  9. 10 3  
  10. 7 2  
  11. 4 1  
  12. 11 1  
  13. 4 6 
  14. 21 
  15. road 0 1  
  16. road 3 5  
  17. line 6.5  
  18. road 4 2  
  19. road 3 8  
  20. road 4 7  
  21. road 6 9  
  22. road 4 1  
  23. road 2 7  
  24. line 4.5  
  25. line 6.5  
  26. line 3.5 
  27. line 2.5 
  28. line 5.5 
  29. road 10 0 
  30. line 5.5 
  31. line 6.5 
  32. road 0 3 
  33. line 1.5 
  34. line 6.5 
  35. line 2.5 
  36.  
  37. ans: 
  38. 0 0  
  39. 2 8  
  40. 1 5  
  41. 2 8 
  42. 3 10 
  43. 1 5 
  44. 1 6 
  45. 1 6 
  46. 2 11 
  47. 1 9 
  48. 2 11
再献上丑的可以的我的代码
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <iostream> #include <algorithm> using namespace std; typedef long long ll; typedef unsigned long long ull; const int inf=0x3f3f3f3f; const ll INF=0x3f3f3f3f3f3f3f3fll; const int maxn=100010; int f[maxn*2],r[maxn*2],L[maxn*2],R[maxn*2],t[maxn*4],num2[maxn*8],num1[maxn*8],Q[maxn*2][2],Lazy1[maxn*8],Lazy2[maxn*8]; int len; double pos1[maxn*2]; char ch[200010][10]; int find1(int x){ if(x!=f[x]) f[x]=find1(f[x]); return f[x]; } void pushdown_1(int node){ if(Lazy1[node]){ Lazy1[node<<1]+=Lazy1[node]; Lazy1[node<<1|1]+=Lazy1[node]; num1[node<<1]+=Lazy1[node]; num1[node<<1|1]+=Lazy1[node]; Lazy1[node]=0; } } void pushdown_2(int node){ if(Lazy2[node]){ Lazy2[node<<1]+=Lazy2[node]; Lazy2[node<<1|1]+=Lazy2[node]; num2[node<<1]+=Lazy2[node]; num2[node<<1|1]+=Lazy2[node]; Lazy2[node]=0; } } void buildtree(int le,int ri,int node){ num2[node]=num1[node]=Lazy1[node]=Lazy2[node]=0; if(le==ri) return ; int t=(le+ri)>>1; buildtree(le,t,node<<1); buildtree(t+1,ri,node<<1|1); } void update_1(int l,int r,int x,int le,int ri,int node){ if(l<=le&&ri<=r){ Lazy1[node]+=x; num1[node]+=x; return ; } pushdown_1(node); int t=(le+ri)>>1; if(l<=t) update_1(l,r,x,le,t,node<<1); if(r>t) update_1(l,r,x,t+1,ri,node<<1|1); } void update_2(int l,int r,int x,int le,int ri,int node){ if(l<=le&&ri<=r){ Lazy2[node]+=x; num2[node]+=x; return ; } pushdown_2(node); int t=(le+ri)>>1; if(l<=t) update_2(l,r,x,le,t,node<<1); if(r>t) update_2(l,r,x,t+1,ri,node<<1|1); } int query_1(int pos,int le,int ri,int node){ if(le==ri) return num1[node]; pushdown_1(node); int t=(le+ri)>>1; int ans; if(pos<=t) ans=query_1(pos,le,t,node<<1); else ans=query_1(pos,t+1,ri,node<<1|1); return ans; } int query_2(int pos,int le,int ri,int node){ if(le==ri) return num2[node]; pushdown_2(node); int t=(le+ri)>>1; int ans; if(pos<=t) ans=query_2(pos,le,t,node<<1); else ans=query_2(pos,t+1,ri,node<<1|1); return ans; } void unite(int a,int b){ int aa=find1(a); int bb=find1(b); if(aa==bb) return ; if(L[aa]>=L[bb]&&R[aa]<=R[bb]){ int l1=lower_bound(t,t+len,L[aa])-t+1; int r1=lower_bound(t,t+len,R[aa])-t+1; int l2=lower_bound(t,t+len,L[bb])-t+1; int r2=lower_bound(t,t+len,R[bb])-t+1; update_1(l1,r1,⑴,1,len,1); update_1(l2,r2,⑴,1,len,1); update_1(l2,r2,1,1,len,1); update_2(l1,r1,-r[aa],1,len,1); update_2(l2,r2,-r[bb],1,len,1); update_2(l2,r2,r[aa]+r[bb],1,len,1); }else if(L[aa]>=L[bb]&&R[aa]>R[bb]){ int l1=lower_bound(t,t+len,L[aa])-t+1; int r1=lower_bound(t,t+len,R[aa])-t+1; int l2=lower_bound(t,t+len,L[bb])-t+1; int r2=lower_bound(t,t+len,R[bb])-t+1; update_1(l1,r1,⑴,1,len,1); update_1(l2,r2,⑴,1,len,1); update_1(l2,r1,1,1,len,1); update_2(l1,r1,-r[aa],1,len,1); update_2(l2,r2,-r[bb],1,len,1); update_2(l2,r1,r[aa]+r[bb],1,len,1); }else if(L[aa]<L[bb]&&R[aa]<=R[bb]){ int l1=lower_bound(t,t+len,L[aa])-t+1; int r1=lower_bound(t,t+len,R[aa])-t+1; int l2=lower_bound(t,t+len,L[bb])-t+1; int r2=lower_bound(t,t+len,R[bb])-t+1; update_1(l1,r1,⑴,1,len,1); update_1(l2,r2,⑴,1,len,1); update_1(l1,r2,1,1,len,1); update_2(l1,r1,-r[aa],1,len,1); update_2(l2,r2,-r[bb],1,len,1); update_2(l1,r2,r[aa]+r[bb],1,len,1); }else if(L[aa]<L[bb]&&R[aa]>R[bb]){ int l1=lower_bound(t,t+len,L[aa])-t+1; int r1=lower_bound(t,t+len,R[aa])-t+1; int l2=lower_bound(t,t+len,L[bb])-t+1; int r2=lower_bound(t,t+len,R[bb])-t+1; update_1(l1,r1,⑴,1,len,1); update_1(l2,r2,⑴,1,len,1); update_1(l1,r1,1,1,len,1); update_2(l1,r1,-r[aa],1,len,1); update_2(l2,r2,-r[bb],1,len,1); update_2(l1,r1,r[aa]+r[bb],1,len,1); } f[aa]=bb;r[bb]+=r[aa];L[bb]=min(L[bb],L[aa]);R[bb]=max(R[bb],R[aa]); } struct edge{ int x,y; }id[maxn]; int main(){ int T,n,m,u,v; scanf("%d",&T); while(T--){ scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d%d",&id[i].x,&id[i].y); int k=0; for(int i=0;i<n;i++){ id[i].y*=2; f[i]=i;r[i]=1;t[k++]=id[i].y;L[i]=id[i].y;R[i]=id[i].y; } scanf("%d",&m); for(int i=0;i<m;i++){ scanf("%s",ch[i]); if(ch[i][0]=='r') scanf("%d%d",&Q[i][0],&Q[i][1]); else if(ch[i][0]=='l'){ scanf("%lf",&pos1[i]); Q[i][0]=(int)2*pos1[i]; t[k++]=Q[i][0]; } } sort(t,t+k); len=unique(t,t+k)-t; buildtree(1,len,1); for(int i=0;i<m;i++){ if(ch[i][0]=='r') unite(Q[i][0],Q[i][1]); else if(ch[i][0]=='l'){ int ll=lower_bound(t,t+len,Q[i][0])-t+1; int ans1=query_1(ll,1,len,1); int ans2=query_2(ll,1,len,1); printf("%d %d\n",ans1,ans2); } } } return 0; }

------分隔线----------------------------

上一篇 单调栈/单调队列/RMQ

下一篇 RHRL7.0安装RAC11.2.0.4----修改主机名

------分隔线----------------------------

最新技术推荐

1Java并发编程的艺术(六)——线程间的通信 2Java并发编程的艺术(三)——volatile 3Node核心模块之Events 4myeclipse源码相关操作 5springMVC源码分析--RequestParamMethodArgumentResolver参数解析器（三） 6Java基本数据类型总结 7java结合testng，利用XML做数据源的数据驱动示例