目录
区间价值
J-区间价值_牛客竞赛动态规划专题班习题课 (nowcoder.com)
时间限制:C/C++ 2秒,其他语言4秒
空间限制:C/C++ 262144K,其他语言524288K
64bit IO Format: %lld
题目描述
对于一个数组a,定义其价值是其中不同的数的个数,比如对于数组[3,2,2,3,1],价值就是3。对于一个给定的长度len,求出所有长度为lenlenlen的子区间的价值之和是对于吉吉国王来说很重要,现在吉吉国王会告诉你他想知道的长度lenlenlen,你需要告诉吉吉国王答案。
比如数组[3,2,2,3,1],长度为2的子区间有[3,2],[2,2],[2,3],[3,1],那么价值分别是2,1,2,2,因此这个数组长度为2的价值和就是7。
输入描述:
第一行一个n表示数组的长度。
第二行n个数,第iii个数表示ai。
第三行一个q表示询问的次数。
接下来q行,每行一个整数表示查询的长度。
输出描述:
输出q行,第i行表示第i个询问的答案。
示例1
输入
5 3 2 4 3 1 4 1 2 3 4
输出
5 8 9 7
备注:
1≤n≤1e6
思路:
这道题容易想到的是暴力解法(区间dp)但这肯定是会爆时间的。
现在设dp[i] 表示区间为i时的价值和。
那怎么从dp[i-1] 转移到 dp[i]
假如 当前区间为3, 数组为 32441
324 -> 3244 贡献不变
244 -> 2441 贡献加1
441 -> null 贡献-2
这里可以看出从dp[i-1] 到 dp[i] 会损伤掉后面 i-1个数的贡献值,并且前几个区间有s[i]的贡献增加。
前几个区间中那些区间是会提供贡献,或者说那些数在区间变大时可以提供贡献,这是可以预处理出来的,因为可以观察发现只有两个相同数的相隔距离大于等于i时,他们才会在长度为i的区间中提供一个贡献。(这里需要用一个后缀和统计)
代码:
import java.util.Scanner;
/**
* @ProjectName: study3
* @FileName: Ex7
* @author:HWJ
* @Data: 2023/12/5 19:53
*/
public class Main {
static int maxN = (int) 1e6 + 5;
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n = input.nextInt();
int[] arr = new int[maxN];
int[] last = new int[maxN];
long[] s = new long[maxN];
int[] diff = new int[maxN];
int[] cnt = new int[maxN];
for (int i = 1; i <= n; i++) {
arr[i] = input.nextInt();
s[i - last[arr[i]]]++;
last[arr[i]] = i;
}
for(int i = n; i > 0; i--){
s[i] = s[i] + s[i + 1];
}
int tot = 0;
for(int i = n; i > 0; i--){
if (++cnt[arr[i]] == 1) tot++;
diff[n - i + 1] = tot;
}
long[] ans = new long[n + 1];
ans[1] = n;
for(int i = 2; i <= n; i++){
ans[i] = ans[i - 1] + s[i] - diff[i - 1];
}
int q = input.nextInt();
for (int i = 0; i < q; i++) {
int a = input.nextInt();
System.out.println(ans[a]);
}
}
}