POJ 2104 K-th Number

2019-11-06 06:27:56

字體：大中小

來源：轉載

供稿：網友

題目描述

給你一個不同整數組成的數組a[1…n]，你必須回答一系列Q(i,j,k)的問題：在區間[i,j]中的第k大值。例如：數組a={1,5,2,6,3,7,4}，詢問 Q(2, 5, 3)，在區間[2,5]中有{5,2,6,3},第三小值是5，我們應該回答這個詢問為5。

輸入描述

第一行包含兩個整數n和m (1 <= n <= 100 000, 1 <= m <= 5 000)，表示n個數，m次詢問。第二行包含n個不同的整數，絕對值不超過10^9。以下m行，每行一個詢問包含三個整數i,j,k (1 <= i <= j <= n, 1 <= k <= j - i + 1)，表示詢問Q(i,j,k)。

輸出描述

對于每個詢問輸出一行，一個整數表示詢問的結果。

樣例輸入

7 31 5 2 6 3 7 42 5 34 4 11 7 3

樣例輸出

563

這題就是一道很裸的主席模板題，注意加上離散化就好了。

#include <cstdio>#include <iostream>#include <cstdlib>#include <algorithm>using namespace std ;const int maxn=100001;int a[maxn],into[maxn],b[maxn];struct Node{ int ls,rs; int cnt;}tr[maxn*20];int cur,rt[maxn];int n,m,ln;void init(){ cur=0; cin >>n >>m; int i; for (i=1;i<=n;i++){ scanf ("%d",&a[i]); b[i]=a[i]; }}inline void push_up(int o){ tr[o].cnt=tr[tr[o].ls].cnt+tr[tr[o].rs].cnt;}int build(int l,int r){//構造模板樹 int k=cur++; if (l==r) { tr[k].cnt=0; return k; } int mid=(l+r)>>1; tr[k].ls=build(l,mid); tr[k].rs=build(mid+1,r); push_up(k); return k;}int update(int o,int l,int r,int pos,int val){//更新 int k=cur++; tr[k]=tr[o]; if (l==pos&&r==pos){ tr[k].cnt+=val; return k; } int mid=(l+r)>>1; if (pos<=mid) tr[k].ls=update(tr[o].ls,l,mid,pos,val); else tr[k].rs=update(tr[o].rs,mid+1,r,pos,val); push_up(k); return k;}int query(int l,int r,int o,int v,int kth){//查找第k小 if (l==r) return l; int mid=(l+r)>>1; int res=tr[tr[v].ls].cnt-tr[tr[o].ls].cnt; if (kth<=res) return query(l,mid,tr[o].ls,tr[v].ls,kth); else return query(mid+1,r,tr[o].rs,tr[v].rs,kth-res);}int cmp (const void *a,const void *b){ return *(int *) a > *(int *)b ? 1 : -1;}int binary_search (int x){//二分查找 int s=1,t=ln,mid; while (s<t) { mid=(s+t)>>1; if (b[mid] >= x) t=mid; else s=mid+1; } return t;}void findit (){//離散化 ln=(unique (b+1,b+n+1))-(b+1); int i; for (i=1;i<=n;i++){ into[i]=binary_search (a[i]); }}int main (){ init (); qsort (b+1,n,sizeof(b[1]),cmp); findit (); int i,j,k,l; build (1,ln); for (i=1;i<=n;i++){ rt[i]=update (rt[i-1],1,ln,into[i],1); } for (i=1;i<=m;i++){ scanf ("%d %d %d",&j,&k,&l); PRintf ("%d/n",b[query (1,ln,rt[j-1],rt[k],l)]); } return 0;}

上一篇：創建和銷毀對象

下一篇：CCF201412(1)