K-th Number(主席树)

2017年10月15日680

2:K-th Number

  1. 对问题的分析设计过程

    题目要求找区间第k大,是一道典型的可持久化权值线段树的例题。

  2. 程序中用到的数据机构和算法

    本程序使用可持久化权值线段树实现,在权值的离散化上直接使用动态申请权值线段树节点来解决该问题。可持久化权值线段树(又称主席树)的详细实现方法可自行百度或参考代码。

  3. 程序的运行情况

    该程序提交了一次即通过。0E0D469A-5839-4D00-A632-9AB4B92CAD25

  4. 在实习过程中得到的经验和体会

    可持久化权值线段树在维护某些区间信息上有很大的作用,是一种非常好的思路。

Code:

 

%d 博主赞过: