UVALive 4730 線段樹+并查集
來源：程序員人生 發布時間：2016-06-07 08:42:37 閱讀次數：3090次
點擊打開鏈接
題意：在座標上給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旅程
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
再獻上丑的可以的我的代碼
#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;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
