枚举右端点 $i$, 然后左端点 $j$ 的有效范围在 $(last[b[i]] + 1, i)$ 才能保证该区间不存在和右端点 $i$ 相同的颜色,接着看左端点 $j$ 啥时候合法。很显然,左端点 $j$ 的右边没有和它一样的颜色,意味着这个 $j$ 是颜色 $b[j]$ 最后出现的位置,意味着一个合法的左端点 $j$。
于是确定右端点 $i$ 后,累加上 $(last[b[i]] + 1, i)$ 之间 $j$ 即可。
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2e5 + 10;
typedef long long i64;
int n;
int b[N], last[N];
int tr[N];
void add(int x, int v) {
for (; x <= n; x += x & -x) tr[x] += v;
}
int query(int x) {
int res = 0;
for (; x; x -= x & -x) res += tr[x];
return res;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) scanf("%d", &b[i]);
i64 ans = 0;
for (int i = 1; i <= n; i ++ ) {
int v = b[i];
if (last[v]) add(last[v], -1);
ans += query(i) - query(last[v]);
add(i, 1), last[v] = i;
}
printf("%lld\n", ans);
return 0;
}
真的强