原题链接
1 题目
1.1 题目所需求出内容
对于本题,最终要求:一个最大值
1.2 题目背景、允许、禁止与限制
背景:有一个长度为 nnn 的序列,其中有一些数字
允许:求某段区间内有多少种不同的数字
1.3 题目数据范围与猜测
1≤n,m≤106⟶O(n log n) 1 \le n,m \le 10^6 \longrightarrow O(n~log~n)1≤n,m≤106⟶O(n log n)
1.4 一句话概括题意
有一个由数字组成的序列 aaa,每次求某段下标区间中有多少不同的数字
2 题目破题推导
2.1 第一步:正向思维转逆向思维
正向思维:每次实时记录某个数字出现与否
逆向思维:对于每个位置 iii,记录 aia_iai 最后一次出现的地方为 iii 设置为 111,然后对于某个区间 [l,r][l,r][l,r],求其中有多少个 111。这样能确保每个数字都只有至多一次记录并且一定是最新更新的
2.2 第二步:分情况讨论证明逆向思维的初步思路正确,还需扩充一点细节即可
假设有个数字 aia_iai ,无非就三种情况
* 这个数字在 [l,r][l,r][l,r] 内,但最后一次出现的位置在 lll 之前?
不可能,既然最后一次出现的位置在 lll 之前,说明根本没在 [l,r][l,r][l,r] 内出现过!
* 这个数字在 [l,r][l,r][l,r] 内,但最后一次出现的位置也在 [l,r][l,r][l,r] 之间
这正是我们要统计的情况
额外地,不论在这个区间出现过几次,都只算有 111,这不正是“只统计最后一次出现的位置”的作用吗?
* 这个数字在 [l,r][l,r][l,r] 内,但最后一次出现的位置在 rrr 之后
确实有可能发生这样的情况,所以我们需要避免
因为题目给定的查询区间 [l,r][l,r][l,r] 不一定按右端点有序,但是发现它若干次询问不修改原数组,那么考虑离线处理\huge{离线处理}离线处理,即把询问区间右端点从小到大排序,这样每一次查询的一定不会出现“最后一次出现的位置在 rrr 之后的情况”
3 模型匹配
关键词:单点修改,区间求和 ⟶\longrightarrow⟶ 树状数组\huge{树状数组}树状数组
实施方案:
vis数组:visivis_ivisi 代表种类 iii 的贝壳最后一次的出现位置
tree树状数组:计算所有 vis1→nvis_{1 \rightarrow n}vis1→n 在查询区间 [i,j][i,j][i,j] 之间的(通过定义分析出)
关键点:
上方提到过的离线处理
4 最终代码(禁止抄袭,仅用于参考)