本文主要是介绍主席数基础模板，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
不带修改主席树
#include<bits/stdc++.h>
#define il inline
#define pb push_back
#define fi first
#define se second
#define ms(_data,v) memset(_data,v,sizeof(_data))
#define sc(n) scanf("%d",&n)
#define SC(n,m) scanf("%d %d",&n,&m)
#define SZ(a) int((a).size())
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define drep(i,a,b) for(int i=a;i>=b;--i)
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f;
const double PI=acos(-1.0);
const double eps=1e-9;
const int maxn=1e5+5;
int a[maxn],b[maxn],rt[maxn*20],ls[maxn*20],rs[maxn*20],sum[maxn*20];
int n,m,tot;
void build(int &rt,int l,int r){rt=++tot;sum[rt]=0;if(l==r) return;int mid=(l+r)>>1;build(ls[rt],l,mid);build(rs[rt],mid+1,r);
}
void update(int &rt,int l,int r,int last,int p){rt=++tot;ls[rt]=ls[last],rs[rt]=rs[last];sum[rt]=sum[last]+1;if(l==r) return;int mid=(l+r)>>1;if(p<=mid) update(ls[rt],l,mid,ls[last],p);else update(rs[rt],mid+1,r,rs[last],p);
}
int query(int ss,int ee,int l,int r,int k){if(l==r) return l;int mid=(l+r)>>1;int cnt=sum[ls[ee]]-sum[ls[ss]];if(k<=cnt) return query(ls[ss],ls[ee],l,mid,k);else return query(rs[ss],rs[ee],mid+1,r,k-cnt);
}
int main(){SC(n,m);rep(i,1,n) sc(a[i]),b[i]=a[i];sort(b+1,b+n+1);int sz=unique(b+1,b+n+1)-(b+1);build(rt[0],1,sz);rep(i,1,n){a[i]=lower_bound(b+1,b+sz+1,a[i])-b; update(rt[i],1,sz,rt[i-1],a[i]); } int l,r,k;rep(i,1,m){sc(l),sc(r),sc(k);int id=query(rt[l-1],rt[r],1,sz,k);printf("%d\n",b[id]);} return 0;
}带修改的主席数
#include<bits/stdc++.h>
#define il inline
#define pb push_back
#define sc(n) scanf("%d",&n)
#define SC(n,m) scanf("%d %d",&n,&m)
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define ms(_data,v) memset(_data,v,sizeof(_data))
#define SZ(a) int((a).size())
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f;
const int maxn=1e5+5;
const int maxm=maxn*150;
int n,m,tot,cnt,sz,a[maxn],b[maxn*5];
int root[maxn],ls[maxm],rs[maxm],dat[maxm];
int totL,totR;
int L[maxn],R[maxn];
template <typename _Tp> il void read(_Tp&x) {char ch;bool flag=0;x=0;while(ch=getchar(),!isdigit(ch)) if(ch=='-')flag=1;while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();if(flag) x=-x;
}
il void insert(int &now, int l, int r, int x, int val){if(!now) now=++tot;dat[now]+=val;if(l==r) return;int mid=(l+r)>>1;if(x<=mid) insert(ls[now],l,mid,x,val);else insert(rs[now],mid+1,r,x,val);
}
il int ask(int l, int r, int k){if(l==r) return l;int sum=0;for(int i=1; i<=totL; i++) sum-=dat[ls[L[i]]];for(int i=1; i<=totR; i++) sum+=dat[ls[R[i]]];int mid=(l+r)>>1;if(sum>=k){for(int i=1; i<=totL; i++) L[i]=ls[L[i]];for(int i=1; i<=totR; i++) R[i]=ls[R[i]];return ask(l,mid,k);}else{for(int i=1; i<=totL; i++) L[i]=rs[L[i]];for(int i=1; i<=totR; i++) R[i]=rs[R[i]];return ask(mid+1,r,k-sum);}
}
il int lowbit(int x){return x&-x;}
il void update(int x,int C){int t=a[x],tt=C;a[x]=C;for(int j=x; j<=n; j+=lowbit(j)){insert(root[j],1,sz,t,-1);insert(root[j],1,sz,tt,1);}
}
il int query(int l,int r,int t){ //返回下标 totL=totR=0,l--;for(int j=l; j; j-=lowbit(j)) L[++totL]=root[j];for(int j=r; j; j-=lowbit(j)) R[++totR]=root[j];int id=ask(1,sz,t);return id;
}
struct node{int op,l,r,k;
}q[maxn];
int main(){read(n),read(m);tot=0,cnt=0;rep(i,1,n) sc(a[i]),b[++cnt]=a[i];char op;int l,r,k;rep(i,1,m){op=getchar();while(!(op=='Q' || op=='C')) op=getchar();if(op=='Q'){read(l),read(r),read(k);q[i]=node{1,l,r,k};}else{read(l),read(r);b[++cnt]=r;q[i]=node{0,l,r,0};}}sort(b+1,b+cnt+1);sz=unique(b+1,b+cnt+1)-(b+1);rep(i,1,n){a[i]=lower_bound(b+1,b+sz+1,a[i])-(b);for(int j=i;j<=n;j+=lowbit(j)){insert(root[j],1,sz,a[i],1);}}rep(i,1,m){if(q[i].op){ //queryint id=query(q[i].l,q[i].r,q[i].k);printf("%d\n",b[id]);}else{ // modifyint x=q[i].l,now=lower_bound(b+1,b+sz+1,q[i].r)-b;update(x,now);}}return 0;
}
这篇关于主席数基础模板的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
