[BZOJ3489]A simple rmq problem(KDT)

发布于 2018-05-28  357 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ3489]A simple rmq problem(KDT)

Description

因为是OJ上的题,就简单点好了。给出一个长度为n的序列,给出M个询问:在[l,r]之间找到一个在这个区间里只出现过一次的数,并且要求找的这个数尽可能大。如果找不到这样的数,则直接输出0。我会采取一些措施强制在线。

Tag

KDT

解决思路

考虑对每一个位置上的数求出它前面第一个与它一样的记为\(Last[i]\),后面第一个与它一样的记为\(Next[i]\),那么对于询问\([l,r]\),要求满足\(l \le i \le r \quad Last[i] < l \quad Next[i] > r \),这个位置上的数就作为权值,那么题目就转化为一个求三维空间中一定区域的点中最大的点权,用\(KDT\)优化\(O(n^2)\)的朴素查询。

代码

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ3489]A simple rmq problem(KDT)


HNCJ OIer