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