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

[BZOJ1012][JSOI2008]最大数(树状数组)

树状数组水了一题感觉不熟练就又水了一题。这题主要就是要把整个数列倒过来插,这样就可以把求后L项的最大数转化为求数列前L项的最大数。在树状数组中,维护一个数列大小size,每次插入就插入到第m - size的位置上,每次查询就查询前m - size + l项的最大值(前导零对答案不影响)。     Read more

Xiaonan Shen's avatar Xiaonan Shen

[BZOJ2743][HEOI2012]采花(离线 + 树状数组)

打算开始学主席树了,然后发现好久没写树状数组,就找了道题练练手,谁知今天脑残不宜写题,WA了半天又T了半天。。     Read more