【洛谷】AT_abc371_e [ABC371E] I Hate Sigma Problems 的题解

洛谷传送门

AT传送门

题解

I Hate Sigma Problems!!!

意思很简单就是求序列中每一个子区间内含有不同数字的个数之和。

暴力的话时间复杂度是 $O(n^2)$，是肯定不行的，所以要考虑别的方法。
刚开始先手模一些情况，然后发现，不同的值没有贡献的地方为当前出现的位置到上一次出现的位置中间的子序列及其子序列。

接着，就是代码实现。考虑枚举右端点。记 $v[i]$ 为 $i$ 这个数最后一次出现的位置。每次在右端加入一个数，对前面所有左端点的影响：对 $1$ 到 $v[i]$的位置没有影响，对 $v[i]+1$ 到当前位置有影响。统计答案并更新 $v[i]$。时间复杂度 $O(n)$。

代码

#include <bits/stdc++.h>
#define lowbit(x) x & (-x)
#define endl "\n"
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
namespace fastIO {inline int read() {register int x = 0, f = 1;register char c = getchar();while (c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();return x * f;}inline void write(int x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');return;}
}
using namespace fastIO;
ll n, a[200005], v[200005], ans = 0, sum;
int main() {//freopen(".in","r",stdin);//freopen(".out","w",stdout);ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin >> n;for(int i = 1; i <= n; i ++) {cin >> a[i];	}v[a[1]] = 1;for(int i = 2; i <= n; i ++) {if(v[a[i]]) sum += i - v[a[i]];else {sum += i;}ans += sum;v[a[i]] = i;}ans += n;cout << ans << endl;return 0;
}