ABC 371
Table of Contents
E - I Hate Sigma Problems
https://atcoder.jp/contests/abc371/tasks/abc371_e
sample 2 の $f(i,j)$ の値を表にまとめると以下のようになる.
| A_i \ A_j | 5 | 4 | 2 | 2 | 3 | 2 | 4 | 4 | 1 |
|---|---|---|---|---|---|---|---|---|---|
| 5 | 1 | 2 | 3 | 3 | 4 | 4 | 4 | 4 | 5 |
| 4 | 1 | 2 | 2 | 3 | 3 | 3 | 3 | 4 | |
| 2 | 1 | 1 | 2 | 2 | 3 | 3 | 4 | ||
| 2 | 1 | 2 | 2 | 3 | 3 | 4 | |||
| 3 | 1 | 2 | 3 | 3 | 4 | ||||
| 2 | 1 | 2 | 2 | 3 | |||||
| 4 | 1 | 1 | 2 | ||||||
| 4 | 1 | 2 | |||||||
| 1 | 1 |
この表より各行の和の値は以下のように遷移することが推察される。
$i$ 行目の和を $S_i$ とすると
\begin{equation}
S_{i+1} = \left\{
\begin{aligned}
&S_i - (N-i+1) ~~~\text{ if } A_i \notin \{A_{i+1}, \cdots, A_{n} \} \nonumber \\
&S_i - (j - i) \nonumber
\end{aligned}
\right.
\end{equation}
where $j$ is minimum integer s.t $ivoid solve() {
int n;
cin >> n;
vector<int> a(n);
rep(i, n) cin >> a[i];
set<int> memo;
vector<deque<int>> deq(n + 1);
ll sum = 0;
rep(i, n) {
int x = a[i];
memo.insert(x);
sum += memo.size();
deq[x].push_back(i);
}
ll ans = sum;
rep2(i, 1, n) {
int x = a[i - 1];
if (deq[x].size() == 1) {
sum = sum - (n - i + 1);
ans += sum;
deq[x].pop_front();
} else {
ll d = deq[x][1] - deq[x][0];
deq[x].pop_front();
sum -= d;
ans += sum;
}
}
cout << ans << endl;
}