主席树入门——询问区间第k大pos2104，询问区间<=k的元素个数hdu4417

poj2104找了个板子。。,但是各种IO还可以进行优化

/* 找区间[l,r]第k大的数 */ #include<iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; #define maxn 100005 struct Node{int lc,rc,sum;}t[maxn*25]; int n,q,a[maxn],b[maxn],m,rt[maxn],size; int build(int l,int r){ int now=++size; t[now].lc=t[now].rc=t[now].sum=0; if(l==r)return now; int mid=l+r>>1; t[now].lc=build(l,mid); t[now].rc=build(mid+1,r); return now; } int update(int last,int l,int r,int pos){//更新到pos点 int now=++size; t[now]=t[last];t[now].sum++; if(l==r)return now; int mid=l+r>>1; if(pos<=mid)t[now].lc=update(t[last].lc,l,mid,pos); else t[now].rc=update(t[last].rc,mid+1,r,pos); return now; } int query(int st,int ed,int l,int r,int k){ if(l==r)return l; int mid=l+r>>1; int sum=t[t[ed].lc].sum-t[t[st].lc].sum; if(k<=sum)return query(t[st].lc,t[ed].lc,l,mid,k); else return query(t[st].rc,t[ed].rc,mid+1,r,k-sum); } void debug(int x){ cout<<t[t[rt[6]].lc].sum-t[t[rt[5]].lc].sum; } int main(){ cin>>n>>q; for(int i=1;i<=n;i++)cin>>a[i],b[i]=a[i]; sort(b+1,b+1+n); m=unique(b+1,b+1+n)-(b+1); rt[0]=build(1,m); for(int i=1;i<=n;i++){ int pos=lower_bound(b+1,b+1+m,a[i])-b; rt[i]=update(rt[i-1],1,m,pos); } while(q--){ int l,r,k; cin>>l>>r>>k; cout<<b[query(rt[l-1],rt[r],1,m,k)]<<'\n'; } } View Code

hdu4417 用vector会莫名MLE，以后就用数组来进行离散化吧。另外，unique(a+1,a+1+n)函数对a数组去重，然后返回去重数组的下一位下标

#include<bits/stdc++.h> using namespace std; #define maxn 100005 struct Node{int lc,rc,v;}t[maxn*25]; int m,tot,a[maxn],b[maxn],n,rt[maxn]; int update(int last, int l, int r, int pos){ int now = ++ tot; t[now] = t[last]; t[now].v ++; if(l == r) return now; int mid = (l + r) >> 1; if(pos <= mid) t[now].lc = update(t[last].lc, l, mid, pos); else t[now].rc = update(t[last].rc, mid+1, r, pos); return now; } int query(int st, int ed, int L, int R, int l, int r){ if(L <= l && r <= R) return t[ed].v - t[st].v; int mid = (l + r) >> 1; int res = 0; if(L <= mid) res += query(t[st].lc, t[ed].lc, L, R, l, mid); if(R > mid) res += query(t[st].rc, t[ed].rc, L, R, mid+1, r); return res; } int build(int l,int r){ int now=++tot; t[now].lc=t[now].rc=t[now].v=0; if(l==r)return now; int mid=l+r>>1; t[now].lc=build(l,mid); t[now].rc=build(mid+1,r); return now; } int main(){ int T, Case = 0; scanf("%d", &T); int n, q; while(T --) { scanf("%d %d", &n, &q); for(int i = 1;i <= n;i ++) { scanf("%d", &a[i]); b[i] = a[i]; } sort(b+1, b+1+n); int m = unique(b+1, b+1+n) - (b+1); for(int i = 1;i <= n;i ++) a[i] = lower_bound(b+1, b+1+m, a[i]) - b; tot = 0; rt[0] = build(1, m); for(int i = 1;i <= n;i ++) rt[i] = update(rt[i-1], 1, m, a[i]); printf("Case %d:\n", ++Case); while(q --) { int l, r, H; scanf("%d %d %d", &l, &r, &H); l ++, r ++; int pos = upper_bound(b+1, b+1+m, H) - b; pos --; if(!pos) { puts("0"); continue; } else { printf("%d\n", query( rt[l-1], rt[r], 1, pos, 1, m ) ); } } } return 0; } View Code

 

转载于:https://www.cnblogs.com/zsben991126/p/10747885.html

相关资源：各显卡算力对照表！