思路与做法
关键观察
对固定的右端点 r，设每个值在前缀 [1,r] 内的最后一次出现位置为 lastr[v]。
那么一个值 v 会出现在 [l,r] 中，当且仅当 lastr[v]≥l。
因此
P3572.第3题-钟阵净余谐振能量
题目内容
钟师在远古祭坛铺设了 n 口钟阵，每口钟的编号记录在数组 {a1,a2,...,an} 中;
对任意区间 [l,r] ，记钟面编号差 △面=ar−al ，并令 g(l,r) 表示区间内不同钟声的种类数;
于是区间的净余谐振能量定义为
△净余=(ar−al)−g(l,r)
请你在所有 1≤l≤r≤n 的区间中，求得最大的 △净余。
输入描述
第一行输入一个整数 n(1≤n≤2×105) ，钟阵长度;
第二行输入 n 个整数 a1,a2,...,an(1≤ai≤n) 表示每口钟的编号。
输出描述
输出一个整数，表示所有区间中最大净余谐振能量。
样例1
输入
5
1 3 1 5 3
输出
2
说明
选择区间 [3,4] ：
样例2
输入
5
1 2 3 4 5
输出
-1
