@(学习笔记)[可持久化线段树]
问题概述
给定一个序列(a_1 ... a_n), 多次在线询问, 求(i in [L, R])中不同(a_i)的个数.
解法
首先考虑离线的解法. 我们把(R)从小到大排序, 用一个序列cnt[i]来维护从第(1)到第(R)位的所有权值中, 是否有权值最后一次出现的位置在第(i)位.
比如说对一个序列(A = {1, 2, 3, 2, 3 }), 当(R = 4)时, (cnt = { 1, 0, 1, 1, 0 }). 对于一个询问((L, R)), 我们查询(sum_{i = L}^R cnt[i])即可.
至于在线的做法, 把这个序列用可持久化线段树维护即可.
参考SPOJ COT2:
http://www.spoj.com/problems/COT2/
没有写代码.