今回の問題は、 ABC200-C の類題です。解けなかった方にとって、この問題が手掛かりになるかもしれません。

\(A_i \neq A_j\) となるような整数組をどう数えればよいでしょうか？
この問題では、 \(N \le 3 \times 10^5\) なので、愚直にループを回して数えていくようでは間に合いません。なので、効率的な解法を考える必要があります。

方針は色々と考えられますが、そのうちの \(2\) つを紹介します。

方針1

整数組 \((i,j)\) (\(1 \le i < j \le N\)) は \(\frac{N \times (N-1)}{2}\) 個存在しますが、それらから \(A_i=A_j\) となるものを引き去ることを考えます。

• まず、数列をソートする。
  
• その後、整数が連続して何個存在するか数える。
  • 例えば、ソート後の数列 \(A'=(2,2,3,4,4,4)\) なら、 \(2\) が \(2\) つ、 \(3\) が \(1\) つ、 \(4\) が \(3\) つ存在します。
• 最後に、全ての数列 \(A'\) に含まれる整数 \(p\) について、 \(p\) が \(q\) 個含まれるなら、答えから \(\frac{q \times (q-1)}{2}\) を減算する。 これは、 \(A_i=A_j=p\) となる整数組 \((i,j)\) (\(i < j\)) の個数である。
  • この式は、 \(q=0,1\) の場合でも成立することに注意してください。

例えば、 \(A'=(2,2,3,4,4,4)\) なら、 \(\frac{6 \times 5}{2} - \frac{2 \times 1}{2} - \frac{3 \times 2}{2} = 11\) となります。

方針2

• まず、全ての \(i\) (\(1 \le i \le N\)) について、以下の値 \(X\) を足し合わせる。
  • 数列 \(A\) に \(A_i\) と等しい項が \(k\) 個含まれるならば、 \(X=N-k\)
• その後、足し合わせた値を \(2\) で割って、出力する。
  • そのままの値では、条件を満たす全ての整数組 \((i,j)\) について、同じ組を丁度 \(2\) 回数えることになってしまいます。

例えば、\(A=(2,2,3,4,4,4)\) なら、 \(\{(6-2)+(6-2)+(6-1)+(6-3)+(6-3)+(6-3)\} / 2 = 11\) となります。

「数列 \(A\) に \(A_i\) と等しい項がいくつ含まれるか？」の部分では、方針1のように数列をソートして求めても、(C++における) map などのデータ構造を使ってバケットソートの要領で数えてもよいです。(今回の問題では、 \(A_i \le 10^9\) という制約であることに注意する必要があります。)

計算量は、用いるデータ構造にも依存しますが、 \(O(N)\) や \(O(N \log N)\) となり、この問題を解くのには十分高速です。

なお、今回の問題では、答えの最大値が \(32\)bit 整数型に収まらないことに注意してください。(\(64\)bit 符号付き整数型には収まります。)

C++による実装例(res1に方針1による解、res2に方針2による解を格納します):

#include<bits/stdc++.h>

using namespace std;

int main(){
  long long n;
  cin >> n;
  vector<int> a(n);
  for(auto &nx : a){cin >> nx;}
  long long res1=(n*(n-1)/2),res2=0;
  
  map<int,long long> mp;
  for(int i=0;i<n;i++){mp[a[i]]++;}
  for(int i=0;i<n;i++){res2+=(n-mp[a[i]]);}
  res2/=2;
  
  sort(a.begin(),a.end());
  a.push_back(-1);
  long long cnt=1;
  for(int i=0;i<n;i++){
    if(a[i]!=a[i+1]){
      res1-=((cnt*(cnt-1))/2);
      cnt=1;
    }
    else{cnt++;}
  }
  assert(res1==res2);
  cout << res1 << '\n';
  //cout << res2 << '\n';
}