BZOJ 2743 [HEOI2012] 采花

发布于 2017-10-10  125 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=2743

题意:多次查询区间有多少个数出现了两次及以上。


原题直接莫队就随便过了,然而 BZ 上加强数据,要求\(O(nlog_n)\) 做法。

\(nxt_i\) 记录 i 的下一次出现位置,于是离线后上一个树状数组,详见代码。

 


一个非常弱的准退役OIER