【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 定理及其应用

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注