SHENXN's BLOG

Purdue University
Computer Science, Math

Xiaonan Shen's avatar Xiaonan Shen

[BZOJ1902][ZOJ2112]ZJU2112 Dynamic Rankings(树状数组 + 主席树)

终于学会了主席树,写了高贵冷艳的带修改区间第K大(虽然二逼平衡树我是用分块水的),关于不带修改的区间第K大参见我的上一篇博客[POJ2104]K-th Number(主席树),其实这个跟树状数组维护前缀和基本是一样的,只是修改时树状数组只需修改(log_2n)个节点,而现在需要修改(log_2n)棵线段树,一共(log_2^2n)个节点。这题在八中上妥妥A了,ZOJ被卡内存(内存小,数据规模还大,还有多组数据,改了半天),到现在都没卡过去,真是不开心。     Read more

Xiaonan Shen's avatar Xiaonan Shen

[POJ2104]K-th Number(主席树)

终于下定决心开始学主席树了,先找了一道不带修改的区间第K大做。关于带修改的区间第K大,参见我的下一篇博客 [BZOJ1902][ZOJ2112]ZJU2112 Dynamic Rankings(树状数组 + 主席树) 主席树其实就是一种可持久化的线段树,是函数式编程的一个很经典的应用(另外的话,我就只知道FANHQ_TREAP了)。主要思想是在对线段树的节点进行修改的时候,不改变原节点,而是新开一个节点并链到数中。     Read more