题意
有一个大小为 \(n ,(n \leq 3e5)\) 的序列，序列中的每一个数 \(a_i\) 满足\(1 \leq a_i \leq n\)，
现定义 good subarray：对于一段区间\(a_l, a_{l+1}, \dots, a_r\)，满足区间内无重复元素并且 \(\max\{a_l, a_{l+1}, \dots, a_r\} - (r-l+1) \leq k\)。
求序列a中的 good subarray的数量。
思路
rmq + 分治的套路题。
针对最大值，可通过rmq预处理，待需要时可通过\(O(log)\)的复杂度查询区间最大值的位置。
对于每个位置，可通过dp (瞎搞)，求出与其无重复元素的左右两端。
接下来就可以通过对最大值分治。
分治过程中对于区间 \([l, r]\) 可通过rmq查询 快速得到最大值的位置 \(p\) ，在\(p-l、 r-p\) 两段中选择一个较小的暴力枚举合法区间数量。
通过分治，每个点的期望遍历次数为\(log\) 次，整体代码期望复杂度为\(O(nlog)\) 。
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 3e5+10;
ll ans;
int a[maxn], st[maxn][30];
int vis[maxn], _l[maxn], _r[maxn];
int T, n, k;
int query(int l, int r) {
int len = r-l+1, d=0;
while((1<<d+1)<=len) ++d; int p=1<<d;
if(a[st[l][d]]>a[st[r-p+1][d]]) return st[l][d];
return st[r-p+1][d];
}
void solve(int l, int r) {
if(l > r) return;
int p = query(l, r);
solve(l, p-1); solve(p+1,r);
int len = a[p]-k;
if(p-l < r-p) {
for (int i=p; i>=l; --i) {
int L = max(p, i+len-1);
int R = min(r, _r[i]);
if(R>=L) ans += R-L+1;
}
} else {
for (int i=p; i<=r; ++i) {
int L = max(_l[i], l);
int R = min(i-len+1, p);
if(R>=L) ans += R-L+1;
}
}
}
int main() {
scanf("%d", &T);
while(T--) {
scanf("%d%d", &n, &k);
for (int i=1; i<=n; ++i)
scanf("%d", a+i), st[i][0]=i;
for (int j=1; j<=20; ++j) {
int p = 1<<j-1, l=1<<j;
for (int i=1; i+l-1<=n; ++i) {
if(a[st[i][j-1]] > a[st[i+p][j-1]]) st[i][j] = st[i][j-1];
else st[i][j] = st[i+p][j-1];
}
}
for (int i=1; i<=n; ++i) vis[i]=n+1;
for (int i=n; i>=1; --i) {
_r[i]=vis[a[i]]-1;
vis[a[i]]=i;
}
for (int i=n-1; i>=1; --i) _r[i] = min(_r[i], _r[i+1]);
for (int i=1; i<=n; ++i) vis[i]=0;
for (int i=1; i<=n; ++i) {
_l[i]=vis[a[i]]+1;
vis[a[i]]=i;
}
for (int i=2; i<=n; ++i) _l[i] = max(_l[i-1], _l[i]);
ans = 0;
solve(1, n);
printf("%lld\n", ans);
}
return 0;
}
/*
2
5 3
2 3 2 2 5
10 4
1 5 4 3 6 2 10 8 4 5
*/总结
刚开始忽略掉了区间中无重复值这个条件，满脑子都是单调栈+瞎搞，等看到这个条件时已经神志不清了，再做题时，需要读好题目中的要求，头脑清醒的分析抽象题目、理清思路与其时间空间以及手敲的复杂度之后再上机，避免既浪费时间，又影响心态。