D-小黑的区间

现在定义dp[i]表示以i位置结尾的完美区间个数，不难发现，以i位置结尾的区间可以是i位置的一个数，也可以是i-1位置到i位置两个数，也可以时i-2到i位置三个数，直到这个区间内有两个相等的数，它们之间不存在与它们相等的值且它们之间的距离大于k。假设我们已经知道了第一个发生冲突的位置j，那么dp[i] = i - j

那么现在要求的就是第一个发生冲突的位置。当然可以一个一个枚举，然后直接超时...所以现在问题就是如何快速找出从后往前数第一个发生冲突的位置

假设在计算dp[i]时我们已经知道了和i - 1位置第一个发生冲突的位置j1，现在我们再计算和i位置的值第一个发生冲突的位置，设和i位置的值发生冲突的位置为j2，(注意j1是和i-1位置冲突的位置，即从j1 + 1到i - 1都不存在冲突的两个数，而j2是和i位置的值发生冲突的位置，即从后往前找的第一个与上一个和i位置相同的值距离大于k的位置)，此时与i位置冲突的位置应该是max(j1, j2)。

我的方法是记录每个位置值与它相同的前一个位置，如果没有那么就默认为0，这样就可以轻松找出冲突的位置，如果不冲突，那么dp[i]就等于i - 0，i左边所有的位置都可以作为左区间。

代码如下:

#include<iostream>
#include<unordered_map>
#include<algorithm>
using namespace std;

int arr[100005];
int pre[100005];
long long dp[100005];
long long ans = 0;
unordered_map<int, int> m;
int n, k;

int findx(int ind) {
	int wind = pre[ind];
	while(wind > 0 && ind - wind <= k) {
		ind = wind;
		wind = pre[wind];
	}
	return wind;
}

int main() {
	scanf("%d%d", &n, &k);
	for(int i = 1; i <= n; i++) {
		scanf("%d", &arr[i]);
		if(m.find(arr[i]) == m.end()) {
			pre[i] = 0;
		} else {
			pre[i] = m[arr[i]];
		}
		m[arr[i]] = i;
	}
	int wrongind = 0;
	for(int i = 1; i <= n; i++) {
		wrongind = max(wrongind, findx(i));
		dp[i] = i - wrongind;
		ans += dp[i];
	}
	printf("%lld", ans);
	return 0;
}