【51nod1175】【區間中的第k大的數】【可持久化線段樹】

2019-11-06 08:50:28

字體：大中小

來源：轉載

供稿：網友

題目大意

一個長度為N的整數序列，編號0 - N - 1。進行Q次查詢，查詢編號i至j的所有數中，第K大的數是多少。

例如: 1 7 6 3 1。i = 1, j = 3，k = 2，對應的數為7 6 3，第2大的數為6。

解題思路

從左到右加點建可持久化線段樹，維護前綴權值線段樹，詢問時利用右減左得出當前區間的權值線段樹，按size大小判斷往哪個方向走，即可得出答案。

code

#include<cmath>#include<cstdio>#include<cstring>#include<algorithm>#define LF double#define LL long long#define Min(a,b) ((a<b)?a:b)#define Max(a,b) ((a>b)?a:b)#define Fo(i,j,k) for(int i=j;i<=k;i++)#define Fd(i,j,k) for(int i=j;i>=k;i--)using namespace std;int const Mxn=1e5,Mxa=1e9;int N,M,Pon,Size[Mxn*30+9],Son[Mxn*30+9][2];void Oper(int PRe,int Now,int L,int R,int V){ int Mid=(L+R)>>1; if(L==R){Size[Now]=Size[Pre]+1;return;} if(V<=Mid){ Son[Now][1]=Son[Pre][1]; Son[Now][0]=++Pon; Oper(Son[Pre][0],Son[Now][0],L,Mid,V); }else{ Son[Now][0]=Son[Pre][0]; Son[Now][1]=++Pon; Oper(Son[Pre][1],Son[Now][1],Mid+1,R,V); } Size[Now]=Size[Son[Now][0]]+Size[Son[Now][1]];}int Qury(int Pre,int Now,int L,int R,int V){ int Mid=(L+R)>>1,Tmp=Size[Son[Now][0]]-Size[Son[Pre][0]]; if(L==R)return L; if(Tmp>=V)return Qury(Son[Pre][0],Son[Now][0],L,Mid,V); else return Qury(Son[Pre][1],Son[Now][1],Mid+1,R,V-Tmp);}int main(){ freopen("d.in","r",stdin); freopen("d.out","w",stdout); scanf("%d",&N);Pon=N;int A; Fo(i,1,N){ scanf("%d",&A); Oper(i-1,i,1,Mxa,A); } int L,R,K; scanf("%d",&M); Fo(cas,1,M){ scanf("%d%d%d",&L,&R,&K);L++;R++; printf("%d/n",Qury(L-1,R,1,Mxa,(R-L+1)-K+1)); } return 0;}

上一篇：線程并行與并發的區別

下一篇：O'Stolz 定理及其應用