主席树的各类模板（区间第k大数【动，静】，区间不同数的个数，

发布时间：2020-12-14 04:20:53 所属栏目：大数据来源：网络整理

导读：取板粗 ? 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大，主席树模板题 #includecstdio #include cstring #include algorithm us

取板粗

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大，主席树模板题

#include<cstdio> #include<cstring> #include<algorithm>
using namespace std; typedef long long ll; const int maxn=1e5+10; const int maxm=3e6+10; int tot,n,q,m; int a[maxn],t[maxn]; int c[maxm],lson[maxm],rson[maxm]; int T[maxn]; void init_hash() { for ( int i=1;i<=n;i++ ) t[i]=a[i]; sort(t+1,t+1+n); m=unique(t+1,t+1+n)-(t+1); } int hash_(int x) { return lower_bound(t+1,t+1+m,x)-t; } void build(int &root,int l,int r) { root=++tot; if ( l==r ) return; int mid=(l+r)/2; build(lson[root],l,mid); build(rson[root],mid+1,r); } void update(int root,int &rt,int p,int val,int r) { rt=++tot; lson[rt]=lson[root],rson[rt]=rson[root]; c[rt]=c[root]+val; if ( l==r ) return; int mid=(l+r)/2; if ( p<=mid ) update(lson[rt],lson[rt],p,val,mid); else update(rson[rt],rson[rt],mid+1,r); } int query(int rt_,int rt,int r,int k) { if ( l==r ) return l; int mid=(l+r)/2; int sum=c[lson[rt_]]-c[lson[rt]]; if ( sum>=k ) return query(lson[rt_],mid,k); else return query(rson[rt_],mid+1,r,k-sum); } int main() { int Case; scanf("%d",&Case); while ( Case-- ) { scanf("%d%d",&n,&q); tot=0; for ( int i=1;i<=n;i++ ) scanf("%d",&a[i]); init_hash(); build(T[0],1,m); for ( int i=1;i<=n;i++ ) { int pos=hash_(a[i]); update(T[i-1],T[i],pos,1,m); } while ( q-- ) { int l,k; scanf("%d%d%d",&l,&r,&k); printf("%dn",t[query(T[r],T[l-1],m,k)]); } } return 0; }

View Code

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开始

#include<cstdio> #include<cstring> #include<algorithm> #include<vector>
using namespace std; const int maxn=1e5+10; const int maxm=3e6+10; int n,tot; int a[maxn],t[maxn]; int T[maxn],rson[maxm],c[maxm]; void init_hash() { for ( int i=1;i<=n;i++ ) t[i]=a[i]; sort(t+1,t+1+n)-(t+1); } int build(int l,int r) { int root=tot++; c[root]=0; if ( l!=r ) { int mid=(l+r)/2; lson[root]=build(l,mid); rson[root]=build(mid+1,r); } return root; } int hash_(int x) { return lower_bound(t+1,x)-t; } int update(int root,int pos,int val) { int rt=tot++,tmp=rt; c[rt]=c[root]+val; int l=1,r=m; while ( l<r ) { int mid=(l+r)/2; if ( pos<=mid ) { lson[rt]=tot++;rson[rt]=rson[root]; rt=lson[rt];root=lson[root]; r=mid; } else { rson[rt]=tot++;lson[rt]=lson[root]; rt=rson[rt];root=rson[root]; l=mid+1; } c[rt]=c[root]+val; } return tmp; } int query(int lrt,int rrt,int k) { int ret=0; int l=1,r=m; while ( l<r ) { int mid=(l+r)/2; if ( k<=mid ) { r=mid; lrt=lson[lrt]; rrt=lson[rrt]; } else { ret+=c[lson[rrt]]-c[lson[lrt]]; l=mid+1; lrt=rson[lrt]; rrt=rson[rrt]; } } ret+=c[rrt]-c[lrt]; return ret; } int main() { int Case,h; scanf("%d",&Case); for ( h=1;h<=Case;h++ ) { scanf("%d%d",&q); tot=0; for ( int i=1;i<=n;i++ ) { scanf("%d",&a[i]); a[i]++; } init_hash(); T[0]=build(1,m); for ( int i=1;i<=n;i++ ) { int pos=hash_(a[i]); T[i]=update(T[i-1],1); } printf("Case %d:n",h); while ( q-- ) { int l,k,p; scanf("%d%d%d",&k); l++,r++,k++; p=hash_(k); if ( t[p]>k ) p--; if ( p==0 ) printf("0n"); else printf("%dn",query(T[l-1],T[r],p)); } } return 0; } HDOJ4417（在线）

在线

#include<cstdio> #include<cstring> #include<algorithm> #include<vector>
using namespace std; const int maxn=1e5+10; const int maxm=3e6+10; int n,tot; int a[maxn],t[maxn*2],l[maxn],r[maxn],val[maxn]; int T[maxn],c[maxm]; void init_hash() { for ( int i=1;i<=n;i++ ) t[i]=a[i]; for ( int i=1;i<=q;i++ ) t[i+n]=val[i]; sort(t+1,t+1+n+q); m=unique(t+1,t+1+n+q)-(t+1); } int build(int l,&a[i]); a[i]++; } for ( int i=1;i<=q;i++ ) { scanf("%d%d%d",&l[i],&r[i],&val[i]); l[i]++,r[i]++,val[i]++; } init_hash(); T[0]=build(1,h); for ( int i=1;i<=q;i++ ) { int L,R,k; L=l[i],R=r[i],k=val[i]; k=hash_(k); printf("%dn",query(T[L-1],T[R],k)); } } return 0; } HDOJ4417（离线）

离线

3.(SPOJ3267)http://www.spoj.com/problems/DQUERY/

题意：给出一个长度为n 的数列

$分析：利用map记录每个数的位置，主席树建新树的时候，如果当前元素出现过，那么把这个元素上次出现的位置减一，然后当前位置加一，如果没出现过就是普通的建树操作。$

对于查询[l,r]我们只需要取出第r棵树，然后输出这棵树[l,r]之间的和，因为是按从1到n的顺序插入的，所以每次只需要求>=l的个数即可

#include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<map>
using namespace std; const int maxn=3e4+10; const int maxm=3e6+10; int n,tot; int a[maxn]; int T[maxn],c[maxm]; int build(int l,r); } return root; } int update(int root,r=n; while ( l<r ) { int mid=(l+r)/2; if ( pos<=mid ) { lson[rt]=tot++;rson[rt]=rson[root]; rt=lson[rt];root=lson[root]; r=mid; } else { rson[rt]=tot++;lson[rt]=lson[root]; rt=rson[rt];root=rson[root]; l=mid+1; } c[rt]=c[root]+val; } return tmp; } int query(int rt,int lpos) { int ret=0; int l=1,r=n; while ( lpos>l ) { int mid=(l+r)/2; if ( lpos<=mid ) { r=mid; ret+=c[rson[rt]]; rt=lson[rt]; } else { rt=rson[rt]; l=mid+1; } } return ret+c[rt]; } int main() { int Case; while ( scanf("%d",&n)!=EOF ) { tot=0; for ( int i=1;i<=n;i++ ) scanf("%d",&a[i]); T[0]=build(1,n); map<int,int>mp; for ( int i=1;i<=n;i++ ) { if ( mp.find(a[i])!=mp.end() ) { int tmp=update(T[i-1],mp[a[i]],-1); T[i]=update(tmp,i,1); } else T[i]=update(T[i-1],1); mp[a[i]]=i; } scanf("%d",&q); while ( q-- ) { int l,r; scanf("%d%d",&r); printf("%dn",query(T[r],l)); } } return 0; } SPOJ3267

View Code

4.（ZOJ2112）http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2112

题意：给定一串序列，有两种操作，一种是求区间[l,r]第k大，另外一种是将a[i]=t

带修改的主席树

#include<cstdio> #include<cstring> #include<algorithm> #include<vector>
using namespace std; const int maxn=60010; const int maxm=2500010; int n,c[maxm]; int S[maxn]; struct Query{ int kind; int l,k; }query[10010]; void init_hash(int k) { sort(t+1,t+k+1); m=unique(t+1,t+k+1)-(t+1); } int hash_(int x) { return lower_bound(t+1,t+m+1,x)-t; } int build(int l,r=m; while ( l<r ) { int mid=(l+r)/2; if ( pos<=mid ) { lson[rt]=tot++;rson[rt]=rson[root]; rt=lson[rt];root=lson[root]; r=mid; } else { rson[rt]=tot++;lson[rt]=lson[root]; rt=rson[rt];root=rson[root]; l=mid+1; } c[rt]=c[root]+val; } return tmp; } int lowbit(int x) { return x&(-x); } int used[maxn]; void add(int x,int val) { while ( x<=n ) { S[x]=update(S[x],val); x+=lowbit(x); } } int sum(int x) { int ret=0; while ( x>0 ) { ret+=c[lson[used[x]]]; x-=lowbit(x); } return ret; } int Q(int left,int right,int k) { int lrt=T[left]; int rrt=T[right]; int l=1,r=m; for ( int i=left;i>0;i-=lowbit(i)) used[i]=S[i]; for ( int i=right;i>0;i-=lowbit(i)) used[i]=S[i]; while ( l<r ) { int mid=(l+r)/2; int tmp=sum(right)-sum(left)+c[lson[rrt]]-c[lson[lrt]]; if ( tmp>=k ) { r=mid; for ( int i=left;i>0;i-=lowbit(i)) used[i]=lson[used[i]]; for ( int i=right;i>0;i-=lowbit(i)) used[i]=lson[used[i]]; lrt=lson[lrt]; rrt=lson[rrt]; } else { l=mid+1; k-=tmp; for ( int i=left;i>0;i-=lowbit(i)) used[i]=rson[used[i]]; for ( int i=right;i>0;i-=lowbit(i)) used[i]=rson[used[i]]; lrt=rson[lrt]; rrt=rson[rrt]; } } return l; } int main() { int Case; scanf("%d",&q); tot=0; m=0; for ( int i=1;i<=n;i++ ) { scanf("%d",&a[i]); t[++m]=a[i]; } char op[10]; for ( int i=0;i<q;i++ ) { scanf("%s",op); if ( op[0]==‘Q‘ ) { query[i].kind=0; scanf("%d%d%d",&query[i].l,&query[i].r,&query[i].k); } else { query[i].kind=1; scanf("%d%d",&query[i].r); t[++m]=query[i].r; } } init_hash(m); T[0]=build(1,1); } for ( int i=1;i<=n;i++ ) S[i]=T[0]; for ( int i=0;i<q;i++ ) { if ( query[i].kind==0 ) printf("%dn",t[Q(query[i].l-1,query[i].r,query[i].k)]); else { add(query[i].l,hash_(a[query[i].l]),-1); add(query[i].l,hash_(query[i].r),1); a[query[i].l]=query[i].r; } } } return 0; } ZOJ2112

View Code

5.（HDOJ4348）http://acm.hdu.edu.cn/showproblem.php?pid=4348

题意：给出一段长度为n的序列，有4种操作。初始时，时间戳=0

a.C l r d [l,r]区间内的数+d，时间戳++

b.Q l r 求当前时间戳下[l,r]区间的和

c.H l r t 求时间戳=t下[l,r]区间的和

d.B t? 时间戳=t

分析：推荐两个讲解较为详细的博客https://blog.csdn.net/glqac/article/details/45103859

https://blog.csdn.net/kirito16/article/details/47266801

#include<cstdio> #include<cstring> #include<algorithm> #include<vector>
using namespace std; typedef long long ll; const int maxn=1e5+10; const int maxm=3e6+10; int n,rson[maxm]; ll sum[maxm],add[maxm]; int build(int l,int r) { int root=tot++; add[root]=0; if ( l!=r ) { int mid=(l+r)/2; lson[root]=build(l,r); } else { scanf("%lld",&sum[root]); return root; } sum[root]=sum[lson[root]]+sum[rson[root]]; return root; } void pushup(int rt,int len) { sum[rt]=sum[lson[rt]]+sum[rson[rt]]+add[lson[rt]]*(len-len/2)+add[rson[rt]]*(len/2); } int A,B; ll val; int update(int root,int r) { int rt=tot++; add[rt]=add[root]; if ( A<=l && r<=B ) { sum[rt]=sum[root]; add[rt]=add[root]+val; lson[rt]=lson[root]; rson[rt]=rson[root]; return rt; } int mid=(l+r)/2; if ( A<=mid ) lson[rt]=update(lson[root],mid); else lson[rt]=lson[root]; if ( B>mid ) rson[rt]=update(rson[root],r); else rson[rt]=rson[root]; pushup(rt,r-l+1); return rt; } ll query(int root,int r,ll add_) { if ( A<=l && r<=B ) return sum[root]+(add_+add[root])*(r-l+1); ll ans=0; int mid=(l+r)/2; if ( A<=mid ) ans+=query(lson[root],add[root]+add_); if ( B>mid ) ans+=query(rson[root],add[root]+add_); return ans; } int main() { char op[5]; int now,Case=0; while ( scanf("%d%d",&q)!=EOF ) { if ( Case!=0 ) printf("n"); Case++; tot=0; T[0]=build(1,n); now=0; while ( q-- ) { ll ans; int k; scanf("%s",op); if ( op[0]==‘C‘ ) { scanf("%d%d%lld",&A,&B,&val); T[now+1]=update(T[now],n); now++; } else if ( op[0]==‘Q‘ ) { scanf("%d%d",&B); ans=query(T[now],0); printf("%lldn",ans); } else if ( op[0]==‘H‘ ) { scanf("%d%d%d",&k); ans=query(T[k],ans); } else if ( op[0]==‘B‘ ) { scanf("%d",&k); now=k; tot=T[now+1]; } } } return 0; } HDOJ4348

View Code

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!