首页 > 其他 > 详细

专题训练之主席树

时间:2018-05-22 20:15:01      阅读:25      评论:0      收藏:0      [点我收藏+]

标签:.org   creat   多少   每次   Go   spl   给定   题集   分析   

推荐几个博客:http://www.cnblogs.com/zyf0163/p/4749042.html 树状结构之主席树

https://blog.csdn.net/creatorx/article/details/75446472 最详细的讲解,让你一次学会主席树

https://blog.csdn.net/jerans/article/details/75807666 主席树题集

https://blog.csdn.net/HTT_H/article/details/47704209 主席树入门专题

 

1.(HDOJ2665)http://acm.hdu.edu.cn/showproblem.php?pid=2665

(POJ2104)http://poj.org/problem?id=2104

(POJ2761)http://poj.org/problem?id=2761

题意:求区间第K大,主席树模板题

技术分享图片
  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 #include<vector>
  5 using namespace std;
  6 const int maxn=1e5+10;
  7 const int maxm=3e6+10;
  8 int n,q,m,tot;
  9 int a[maxn],t[maxn];
 10 int T[maxn],lson[maxm],rson[maxm],c[maxm];
 11 
 12 void init_hash()
 13 {
 14     for ( int i=1;i<=n;i++ ) t[i]=a[i];
 15     sort(t+1,t+1+n);
 16     m=unique(t+1,t+1+n)-(t+1);
 17 }
 18 
 19 int build(int l,int r)
 20 {
 21     int root=tot++;
 22     c[root]=0;
 23     if ( l!=r )
 24     {
 25         int mid=(l+r)/2;
 26         lson[root]=build(l,mid);
 27         rson[root]=build(mid+1,r);
 28     }
 29     return root;
 30 }
 31 
 32 int hash_(int x)
 33 {
 34     return lower_bound(t+1,t+1+m,x)-t;
 35 }
 36 
 37 int update(int root,int pos,int val)
 38 {
 39     int rt=tot++,tmp=rt;
 40     c[rt]=c[root]+val;
 41     int l=1,r=m;
 42     while ( l<r )
 43     {
 44         int mid=(l+r)/2;
 45         if ( pos<=mid )
 46         {
 47             lson[rt]=tot++;rson[rt]=rson[root];
 48             rt=lson[rt];root=lson[root];
 49             r=mid;
 50         }
 51         else 
 52         {
 53             rson[rt]=tot++;lson[rt]=lson[root];
 54             rt=rson[rt];root=rson[root];
 55             l=mid+1;
 56         }
 57         c[rt]=c[root]+val;
 58     }
 59     return tmp;
 60 }
 61 
 62 int query(int lrt,int rrt,int k)
 63 {
 64     int l=1,r=m;
 65     while ( l<r )
 66     {
 67         int mid=(l+r)/2;
 68         if ( c[lson[rrt]]-c[lson[lrt]]>=k )
 69         {
 70             r=mid;
 71             lrt=lson[lrt];
 72             rrt=lson[rrt];
 73         }
 74         else 
 75         {
 76             l=mid+1;
 77             k-=c[lson[rrt]]-c[lson[lrt]];
 78             lrt=rson[lrt];
 79             rrt=rson[rrt];
 80         }
 81     }
 82     return l;
 83 }
 84 
 85 int main()
 86 {
 87     int Case;
 88     scanf("%d",&Case);
 89     while ( Case-- )
 90     {
 91         scanf("%d%d",&n,&q);
 92         tot=0;
 93         for ( int i=1;i<=n;i++ ) scanf("%d",&a[i]);
 94         init_hash();
 95         T[0]=build(1,m);
 96         for ( int i=1;i<=n;i++ )
 97         {
 98             int pos=hash_(a[i]);
 99             T[i]=update(T[i-1],pos,1);
100         }
101         while ( q-- )
102         {
103             int l,r,k;
104             scanf("%d%d%d",&l,&r,&k);
105             printf("%d\n",t[query(T[l-1],T[r],k)]);
106         }
107     }
108     return 0;
109 }
HDOJ2665

 

2.(HDOJ4417)http://acm.hdu.edu.cn/showproblem.php?pid=4417

题意:求给定区间<=k的数有多少

分析:在模板上将query部分修改一下即可,对于区间[L,R]来说,只需要将第R颗线段树上的[0,k]区间内的值减去第L-1颗线段树上对应区间即可。离线在线都行,离线做法需要将每次访问的k也添加进入hash数组,而对于在线来说转化后的数转化前相对于给定的k来说只能变小不能变大即可

注意:题目给的区间范围从0开始,要将其转化成从1开始

技术分享图片
  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 #include<vector>
  5 using namespace std;
  6 const int maxn=1e5+10;
  7 const int maxm=3e6+10;
  8 int n,q,m,tot;
  9 int a[maxn],t[maxn];
 10 int T[maxn],lson[maxm],rson[maxm],c[maxm];
 11 
 12 void init_hash()
 13 {
 14     for ( int i=1;i<=n;i++ ) t[i]=a[i];
 15     sort(t+1,t+1+n);
 16     m=unique(t+1,t+1+n)-(t+1);
 17 }
 18 
 19 int build(int l,int r)
 20 {
 21     int root=tot++;
 22     c[root]=0;
 23     if ( l!=r )
 24     {
 25         int mid=(l+r)/2;
 26         lson[root]=build(l,mid);
 27         rson[root]=build(mid+1,r);
 28     }
 29     return root;
 30 }
 31 
 32 int hash_(int x)
 33 {
 34     return lower_bound(t+1,t+1+m,x)-t;
 35 }
 36 
 37 int update(int root,int pos,int val)
 38 {
 39     int rt=tot++,tmp=rt;
 40     c[rt]=c[root]+val;
 41     int l=1,r=m;
 42     while ( l<r )
 43     {
 44         int mid=(l+r)/2;
 45         if ( pos<=mid )
 46         {
 47             lson[rt]=tot++;rson[rt]=rson[root];
 48             rt=lson[rt];root=lson[root];
 49             r=mid;
 50         }
 51         else 
 52         {
 53             rson[rt]=tot++;lson[rt]=lson[root];
 54             rt=rson[rt];root=rson[root];
 55             l=mid+1;
 56         }
 57         c[rt]=c[root]+val;
 58     }
 59     return tmp;
 60 }
 61 
 62 int query(int lrt,int rrt,int k)
 63 {
 64     int ret=0;
 65     int l=1,r=m;
 66     while ( l<r )
 67     {
 68         int mid=(l+r)/2;
 69         if ( k<=mid )
 70         {
 71             r=mid;
 72             lrt=lson[lrt];
 73             rrt=lson[rrt];
 74         }
 75         else 
 76         {
 77             ret+=c[lson[rrt]]-c[lson[lrt]];
 78             l=mid+1;
 79             lrt=rson[lrt];
 80             rrt=rson[rrt];
 81         }
 82     }
 83     ret+=c[rrt]-c[lrt];
 84     return ret;
 85 }
 86 
 87 int main()
 88 {
 89     int Case,h;
 90     scanf("%d",&Case);
 91     for ( h=1;h<=Case;h++ )
 92     {
 93         scanf("%d%d",&n,&q);
 94         tot=0;
 95         for ( int i=1;i<=n;i++ ) 
 96         {
 97             scanf("%d",&a[i]);
 98             a[i]++;
 99         }
100         init_hash();
101         T[0]=build(1,m);
102         for ( int i=1;i<=n;i++ )
103         {
104             int pos=hash_(a[i]);
105             T[i]=update(T[i-1],pos,1);
106         }
107         printf("Case %d:\n",h);
108         while ( q-- )
109         {
110             int l,r,k,p;
111             scanf("%d%d%d",&l,&r,&k);
112             l++,r++,k++;
113             p=hash_(k);
114             if ( t[p]>k ) p--;
115             if ( p==0 ) printf("0\n");
116             else printf("%d\n",query(T[l-1],T[r],p));
117         }
118     }
119     return 0;
120 }
HDOJ4417(在线)
技术分享图片
  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 #include<vector>
  5 using namespace std;
  6 const int maxn=1e5+10;
  7 const int maxm=3e6+10;
  8 int n,q,m,tot;
  9 int a[maxn],t[maxn*2],l[maxn],r[maxn],val[maxn];
 10 int T[maxn],lson[maxm],rson[maxm],c[maxm];
 11 
 12 void init_hash()
 13 {
 14     for ( int i=1;i<=n;i++ ) t[i]=a[i];
 15     for ( int i=1;i<=q;i++ ) t[i+n]=val[i];
 16     sort(t+1,t+1+n+q);
 17     m=unique(t+1,t+1+n+q)-(t+1);
 18 }
 19 
 20 int build(int l,int r)
 21 {
 22     int root=tot++;
 23     c[root]=0;
 24     if ( l!=r )
 25     {
 26         int mid=(l+r)/2;
 27         lson[root]=build(l,mid);
 28         rson[root]=build(mid+1,r);
 29     }
 30     return root;
 31 }
 32 
 33 int hash_(int x)
 34 {
 35     return lower_bound(t+1,t+1+m,x)-t;
 36 }
 37 
 38 int update(int root,int pos,int val)
 39 {
 40     int rt=tot++,tmp=rt;
 41     c[rt]=c[root]+val;
 42     int l=1,r=m;
 43     while ( l<r )
 44     {
 45         int mid=(l+r)/2;
 46         if ( pos<=mid )
 47         {
 48             lson[rt]=tot++;rson[rt]=rson[root];
 49             rt=lson[rt];root=lson[root];
 50             r=mid;
 51         }
 52         else 
 53         {
 54             rson[rt]=tot++;lson[rt]=lson[root];
 55             rt=rson[rt];root=rson[root];
 56             l=mid+1;
 57         }
 58         c[rt]=c[root]+val;
 59     }
 60     return tmp;
 61 }
 62 
 63 int query(int lrt,int rrt,int k)
 64 {
 65     int ret=0;
 66     int l=1,r=m;
 67     while ( l<r )
 68     {
 69         int mid=(l+r)/2;
 70         if ( k<=mid )
 71         {
 72             r=mid;
 73             lrt=lson[lrt];
 74             rrt=lson[rrt];
 75         }
 76         else 
 77         {
 78             ret+=c[lson[rrt]]-c[lson[lrt]];
 79             l=mid+1;
 80             lrt=rson[lrt];
 81             rrt=rson[rrt];
 82         }
 83     }
 84     ret+=c[rrt]-c[lrt];
 85     return ret;
 86 }
 87 
 88 int main()
 89 {
 90     int Case,h;
 91     scanf("%d",&Case);
 92     for ( h=1;h<=Case;h++ )
 93     {
 94         scanf("%d%d",&n,&q);
 95         tot=0;
 96         for ( int i=1;i<=n;i++ ) 
 97         {
 98             scanf("%d",&a[i]);
 99             a[i]++;
100         }
101         for ( int i=1;i<=q;i++ ) {
102             scanf("%d%d%d",&l[i],&r[i],&val[i]);
103             l[i]++,r[i]++,val[i]++;
104         }
105         init_hash();
106         T[0]=build(1,m);
107         for ( int i=1;i<=n;i++ )
108         {
109             int pos=hash_(a[i]);
110             T[i]=update(T[i-1],pos,1);
111         }
112         printf("Case %d:\n",h);
113         for ( int i=1;i<=q;i++ )
114         {
115             int L,R,k;
116             L=l[i],R=r[i],k=val[i];
117             k=hash_(k);
118             printf("%d\n",query(T[L-1],T[R],k));
119         }
120     }
121     return 0;
122 }
HDOJ4417(离线)

 

专题训练之主席树

标签:.org   creat   多少   每次   Go   spl   给定   题集   分析   

原文:https://www.cnblogs.com/HDUjackyan/p/9069311.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号