[HDU2665]Kth number (主席树)

发布于 2018-01-26  5 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[HDU2665]Kth number (主席树)

Description

Give you a sequence and ask you the kth big number of a inteval.

Http

HDU

Tag

主席树

题目大意

求区间第\(K\)大

解决思路

主席树练手题。
相当于建立出\(n\)棵权值线段树,第\(i\)棵权值线段树保存的是前\(i\)个点的信息,那么类似与前缀和的思想,求\([l,r]\)的线段树就用第\(r\)棵线段树减去第\(l\)棵线段树,在这课作差得到的线段树上查询即可。而主席树就是利用已知信息节约空间。

代码

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[HDU2665]Kth number (主席树)


HNCJ OIer 一枚