题解 | #小黑的区间#

D.小黑的区间

这题官方是用双指针做的，也是这题的一个很标准的做法，但比赛时笔者想到了用dp做的方法，觉得很不错，所以分享一波。

首先我们知道，对于一个区间[1,2,3]来说，如果想求其中有几个完美区间，显然是[1],[2],[3],[1,2],[2,3],[1,2,3]共六个，那么如果再加入一个4呢？答案是会多出[1,2,3,4],[2,3,4],[3,4],[4],共四个，加起来十个。那对于区间[1,2]呢？显然是[1],[2],[1,2]共三个。

如果观察能力强的同学可能会发现，对于一个区间a来说，每增加一个数，如果该区间仍是完美区间，那么完美区间的总个数=原来完美区间的个数+区间长度，即有dp[i]=dp[i-1]+len;

显然，加入的数如果和上一个相同的数距离大于k，就不是完美区间，此时只要用一个桶b来装各个数的最新位置，然后利用桶把区间长度减小即可。 接下来上代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
using pii = pair<int, int>;
using i64 = int64_t;
const int N = 1e5 + 9;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const double pi = 3.1415926535;


ll dp[N], b[N];  //记得开ll，不然会WA

void solve() {
	ll n, k;
	cin >> n >> k;
	ll len = 0;
	for (ll i = 1; i <= n; i++) {
		ll x;
		cin >> x;
		if (!b[x] || i - b[x] <= k || i - 1 - len > b[x]) {  //这里第三个条件是判断当
			len++;                                           //前的区间是否已经减去上
			b[x] = i;                                        //一个x，这样就不用改区间
			dp[i] = dp[i - 1] + len;                         
		} else {
			len = len + 1 - (b[x] - (i - 1 - len));         //修改区间大小
			b[x] = i;
			dp[i] = dp[i - 1] + len;
		}
	}
	cout << dp[n];
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int _ = 1;
	//cin >> _;
	while (_--)
		solve();

	return 0;
}

好了，这篇题解就到这里。我知道可能修改区间那里有点抽象，但本蒟蒻也想不到更合适的说法qwq，这是在下第一篇题解，希望各位观看愉快，如有问题欢迎讨论~