原题链接
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 大拆小、小组大
2.2 正向思维转逆向思维，逆向思维转正向思维
正向思维：每次实时记录某个数字出现与否
逆向思维：对于每个位置 iii，记录 aia_iai 最后一次出现的地方为 iii 设置为 111，然后对于某个区间 [l,r][l,r][l,r]，求其中有多少个 111。这样能确保每个数字都只有至多一次记录并且一定是最新更新的。
2.3 分情况考虑
2.4 数学
2.5 以终为始、以始为终
2.6 手动推导
2.7 边界测试
3 模型匹配
> 格式为："关键词：...... ⟶\longrightarrow⟶ ......\huge{......}......"
关键词：单点修改，区间求和 ⟶\longrightarrow⟶ 树状数组\huge{树状数组}树状数组
实施方案：
vis数组：visivis_ivisi 代表种类 iii 的贝壳最后一次的出现位置
tree树状数组：计算所有 vis1→nvis_{1 \rightarrow n}vis1→n 在查询区间 [i,j][i,j][i,j] 之间的（通过定义分析出）
关键点：
因为我们要确保不会出现形如先查询 [2,4][2,4][2,4] 再查询 [1,3][1,3][1,3] 的问题（否则会导致“到当前位置 aia_iai 最后一次出现”计算错误）。因此离线处理，排序 rrr 右端点，能时刻保证状态合法
4 最终代码（禁止抄袭，仅用于参考）
