第k小元素学习记录
发布日期:2021-08-14 17:36:18 浏览次数:10 分类:技术文章

本文共 7739 字,大约阅读时间需要 25 分钟。

从第K元素看数据结构>> 

View Code
1 #include 
2 #include
3 #include
4 5 using namespace std; 6 7 #define ls rt<<1 8 #define rs rt<<1|1 9 #define lson l,m,ls 10 #define rson m+1,r,rs 11 #define mid (l+r)>>1 12 13 #define MAXN 200010 14 15 int sum[MAXN<<2];//记录有几个点在节点的范围内 16 int rank[MAXN],fa[MAXN];//rank表示集合的大小,fa表示根 17 int n; 18 19 void init(int n) 20 { 21 for(int i=0;i<=n;i++) 22 { 23 rank[i]=1; 24 fa[i]=i; 25 } 26 } 27 28 int find(int x) 29 { 30 if(x != fa[x]) 31 fa[x]=find(fa[x]); 32 return fa[x]; 33 } 34 35 void build(int l,int r,int rt) 36 { 37 if(l==1)//开始时每个集合的大小都为1故都在区间[1,r]内 38 sum[rt]=n; 39 else 40 sum[rt]=0; 41 if(l==r) return ; 42 int m=mid; 43 build(lson); 44 build(rson); 45 } 46 47 void update(bool flag,int val,int l,int r,int rt) 48 { 49 if(!flag)//flag见main函数 50 sum[rt]--; 51 else 52 sum[rt]++; 53 int m=mid; 54 if(l==r) return ; 55 if(val<=m) //val为集合的大小,小于m表示在左边 56 update(flag,val,lson); 57 else 58 update(flag,val,rson); 59 } 60 61 void query(int k,int l,int r,int rt) 62 { 63 if(l==r) 64 { 65 printf("%d\n",l); 66 return ; 67 } 68 int m=mid; 69 if(k <= sum[rt<<1|1]) 70 query(k,rson);////右子树有大于等于k个数,第k个数肯定在右边 71 else 72 query(k-sum[rt<<1|1],lson); 73 } 74 75 int main() 76 { 77 int m; 78 while(scanf("%d%d",&n,&m) != EOF) 79 { 80 init(n); 81 build(1,n,1); 82 while(m--) 83 { 84 int q,x,y; 85 scanf("%d",&q); 86 if(q==0) 87 { 88 scanf("%d%d",&x,&y); 89 x=find(x); 90 y=find(y); 91 if(x==y) 92 continue; 93 update(false,rank[x],1,n,1);//先把x所在集合大小去掉 94 update(false,rank[y],1,n,1); 95 update(true,rank[x]+rank[y],1,n,1);//集合合并 96 fa[y]=x; 97 rank[x]+=rank[y]; 98 } 99 else100 {101 scanf("%d",&x);//第k小102 query(x,1,n,1);103 }104 }105 }106 return 0;107 }

 

一,线段树与树状数组动态更新k小元素:

+线段树

可以与下面的树状数组相比较来理解,其实跟树状数组差不多。 

View Code
1 #include 
2 #include
3 #include
4 5 using namespace std; 6 7 #define ls rt<<1 8 #define rs rt<<1|1 9 #define lson l,m,ls 10 #define rson m+1,r,rs 11 #define mid (l+r)>>1 12 13 #define MAXN 200010 14 15 int sum[MAXN<<2];//记录有几个点在节点的范围内 16 int rank[MAXN],fa[MAXN];//rank表示集合的大小,fa表示根 17 int n; 18 19 void init(int n) 20 { 21 for(int i=0;i<=n;i++) 22 { 23 rank[i]=1; 24 fa[i]=i; 25 } 26 } 27 28 int find(int x) 29 { 30 if(x != fa[x]) 31 fa[x]=find(fa[x]); 32 return fa[x]; 33 } 34 35 void build(int l,int r,int rt) 36 { 37 if(l==1)//开始时每个集合的大小都为1故都在区间[1,r]内 38 sum[rt]=n; 39 else 40 sum[rt]=0; 41 if(l==r) return ; 42 int m=mid; 43 build(lson); 44 build(rson); 45 } 46 47 void update(bool flag,int val,int l,int r,int rt) 48 { 49 if(!flag)//flag见main函数 50 sum[rt]--; 51 else 52 sum[rt]++; 53 int m=mid; 54 if(l==r) return ; 55 if(val<=m) //val为集合的大小,小于m表示在左边 56 update(flag,val,lson); 57 else 58 update(flag,val,rson); 59 } 60 61 void query(int k,int l,int r,int rt) 62 { 63 if(l==r) 64 { 65 printf("%d\n",l); 66 return ; 67 } 68 int m=mid; 69 if(k <= sum[rt<<1|1]) 70 query(k,rson);////右子树有大于等于k个数,第k个数肯定在右边 71 else 72 query(k-sum[rt<<1|1],lson); 73 } 74 75 int main() 76 { 77 int m; 78 while(scanf("%d%d",&n,&m) != EOF) 79 { 80 init(n); 81 build(1,n,1); 82 while(m--) 83 { 84 int q,x,y; 85 scanf("%d",&q); 86 if(q==0) 87 { 88 scanf("%d%d",&x,&y); 89 x=find(x); 90 y=find(y); 91 if(x==y) 92 continue; 93 update(false,rank[x],1,n,1);//先把x所在集合大小去掉 94 update(false,rank[y],1,n,1); 95 update(true,rank[x]+rank[y],1,n,1);//集合合并 96 fa[y]=x; 97 rank[x]+=rank[y]; 98 } 99 else100 {101 scanf("%d",&x);//第k小102 query(x,1,n,1);103 }104 }105 }106 return 0;107 }

 

 

+树状数组

二,划分树与归并树求第k小元素:

看大牛的博客上说的,划分树可以看成线段树+快排,归并树可以看成线段树+归并排序

+划分树

这里看看

都可以用划分树求。 

题意就是求不同区间第k值:

给出代码,还不是很理解:

View Code
1 #include 
2 #include
3 #include
4 #include
5 6 using namespace std; 7 8 #define ls rt<<1 9 #define rs rt<<1|1 10 #define lson l,m,ls 11 #define rson m+1,r,rs 12 13 #define MAXN 100001 14 struct Seg_Tree 15 { 16 int l,r; 17 }tt[MAXN<<2]; 18 int len; 19 int sorted[MAXN]; 20 int toLeft[20][MAXN]; 21 int val[20][MAXN]; 22 23 void build(int d,int l,int r,int rt) 24 { 25 tt[rt].l = l; 26 tt[rt].r = r; 27 if(tt[rt].l == tt[rt].r) return ; 28 int m = (l+r)>>1; 29 int lsame = m - l + 1; 30 for(int i = l ; i <= r ; i ++) 31 { 32 if(val[d][i] < sorted[m]) 33 lsame --; 34 } 35 int lpos = l; 36 int rpos = m+1; 37 int same = 0; 38 for(int i = l ; i <= r ; i ++) 39 { 40 if(i == l) 41 toLeft[d][i] = 0; 42 else 43 toLeft[d][i] = toLeft[d][i-1]; 44 if(val[d][i] < sorted[m]) 45 { 46 toLeft[d][i] ++; 47 val[d+1][lpos++] = val[d][i]; 48 } 49 else if(val[d][i] > sorted[m]) 50 val[d+1][rpos++] = val[d][i]; 51 else 52 { 53 if(same < lsame) 54 { 55 same ++; 56 toLeft[d][i] ++; 57 val[d+1][lpos++] = val[d][i]; 58 } 59 else 60 val[d+1][rpos++] = val[d][i]; 61 } 62 } 63 build(d+1,lson); 64 build(d+1,rson); 65 } 66 67 int query(int k,int d,int l,int r,int rt) 68 { 69 if(l == r) 70 return val[d][l]; 71 int s; 72 int ss; 73 if(l == tt[rt].l) 74 { 75 s = toLeft[d][r]; 76 ss = 0; 77 } 78 else 79 { 80 s = toLeft[d][r] - toLeft[d][l-1]; 81 ss = toLeft[d][l-1]; 82 } 83 if(s >= k) 84 { 85 int newl = tt[rt].l + ss; 86 int newr = tt[rt].l + ss + s - 1; 87 return query(k,d+1,newl,newr,ls); 88 } 89 else 90 { 91 int m = (tt[rt].l + tt[rt].r)>>1; 92 int bb = l - tt[rt].l - ss; 93 int b = r - l + 1 - s; 94 int newl = m + bb + 1; 95 int newr = m + bb + b; 96 return query(k-s,d+1,newl,newr,rs); 97 } 98 } 99 100 int main() 101 {102 int n , m;103 while(scanf("%d%d",&n,&m) != EOF)104 {105 for(int i=1;i<=n;i++)106 {107 scanf("%d",&val[0][i]);108 sorted[i] = val[0][i];109 }110 sort(sorted + 1 , sorted + n + 1);111 build(0,1,n,1);112 while(m --) 113 {114 int l,r,k;115 scanf("%d%d%d",&l,&r,&k);116 printf("%d\n",query(k,0,l,r,1));117 }118 }119 return 0;120 }

 

 

+归并树

++++未看

小结:线段树与树状数组可以用来求区间固定,但是动态查询第K小元素的题,划分树与归并树可以求不同区间的第K小,具体看上面题。

转载于:https://www.cnblogs.com/Missa/archive/2012/08/08/2628921.html

转载地址:https://blog.csdn.net/weixin_30731287/article/details/95559008 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:avi文件格式详解【转】
下一篇:IOS里的多线程编程详解

发表评论

最新留言

做的很好,不错不错
[***.243.131.199]2024年11月19日 02时34分31秒