題目鏈接

http://acm.hdu.edu.cn/showproblem.php?pid=2665

?

代碼：

//#include<bits/stdc++.h> #include<iostream> #include<cmath> #include<algorithm> #define fi first #define se second #define INF 0x3f3f3f3f #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) #define pqueue priority_queue #define NEW(a,b) memset(a,b,sizeof(a)) #define lowbit(x) ((x)&(-x)) using namespace std; const double pi=4.0*atan(1.0); const double e=exp(1.0); const int maxn=1e5+6; typedef long long LL; typedef unsigned long long ULL; const LL mod=1e9+7; const ULL base=1e7+7; struct node{int siz,lc,rc; }a[maxn*20]; int s[maxn]; struct nub{int st,num;bool operator<(const nub &u)const{return num<u.num;} }u[maxn]; int tot=0,rt[maxn]; void Build(int d,int l,int r){a[d].siz=0;if(l==r){return ;}int m=(l+r)>>1;a[d].lc=tot++;a[d].rc=tot++;Build(a[d].lc,l,m);Build(a[d].rc,m+1,r); } void updata(int st,int d,int last,int l,int r){a[d].siz=a[last].siz+1;if(l==r){return ;}int mid=(l+r)>>1;if(st<=mid){a[d].rc=a[last].rc;a[d].lc=tot++;updata(st,a[d].lc,a[last].lc,l,mid);}else if(st>mid){a[d].lc=a[last].lc;a[d].rc=tot++;updata(st,a[d].rc,a[last].rc,mid+1,r);} } int query(int k,int last,int now,int l,int r){if(l==r){return l;}int mid=(l+r)>>1;if(k<=a[a[now].lc].siz-a[a[last].lc].siz){return query(k,a[last].lc,a[now].lc,l,mid);}else{return query(k-(a[a[now].lc].siz-a[a[last].lc].siz),a[last].rc,a[now].rc,mid+1,r);} } int b[maxn]; int main(){int n,m,t;scanf("%d",&t);while(t--){tot=0;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%d",&u[i].num);u[i].st=i;}sort(u+1,u+1+n);int cnt=1;s[cnt]=u[1].num;b[u[1].st]=1;for(int i=2;i<=n;i++){if(u[i].num!=u[i-1].num){cnt++;s[cnt]=u[i].num;}b[u[i].st]=cnt;}rt[0]=tot++;Build(rt[0],1,cnt);for(int i=1;i<=n;i++){rt[i]=tot++;updata(b[i],rt[i],rt[i-1],1,cnt);}int l,r,k;for(int i=1;i<=m;i++){scanf("%d%d%d",&l,&r,&k);printf("%d\n",s[query(k,rt[l-1],rt[r],1,cnt)]);}}system("pause");return 0; }

?

轉載于:https://www.cnblogs.com/Profish/p/9964051.html

總結

以上是生活随笔為你收集整理的HDU2665 求区间第K大 主席树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。