数え上げの順序を変える． \(a_{l} \neq a_{r}\) かつ \(l < r\) となる \(l,r \in N\) に対して，これを含む連続した区間を数える． それは， \(min(l+1, N-r)\) と一致する． minを外すために，大小で場合分けすることと， \(l,r\) のうち \(l\) を全探索して \(r\) を定数をみなすとよい．
数えるべきは， \(r \in N\) かつ \(a_{l} \neq a_{r}\) かつ \(l < r \leq N-l-1\) となる \(r\) の個数． \(\neq\) は調べづらいので， \(=\) の個数を数えて全体から引く 方針にする． これは， \(cnt_{x} := \) (i \(in N\) であって， \(a_{i} = x\)となるもの全体 ) を用意して binary search で求まる．
実装
大小の場合分けは， \(a\) を反転させればコードを使いまわせて安全． ただし， \(l+1 = N-r\) の場合だけ重複して数えているので， それは引く．
注意：区間が空になるときは0を足すことになる． 区間 \([x,y)\) だからといって \(f(y) - f(x)\) の形にしてしまうと， 空の区間で失敗するので if 文で分ける．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n, m ;
cin >> n;
vll a(n); rep(i,n) { cin >> a[i]; a[i]--; }
ll ans = 0;
rep(l,n){
ll nl = n - l -1;
if(l > nl) continue; // empty segment
if(a[nl] != a[l]) ans -= l+1;
}
rep(_,2){
vvll pos(n);
rep(i,n){
pos[a[i]].push_back(i);
}
rep(l,n){
ll nl = n-l-1;
if(l > nl) continue; // empty segment
ans += (nl - l)*(l+1);
auto it0 = lower_bound(all(pos[a[l]]), l+1);
auto it1 = lower_bound(all(pos[a[l]]), nl+1);
ans -= (it1 - it0)*(l+1);
}
reverse(all(a));
}
cout << ans << endl;
return 0;
}
