codeforces Round #261(div2) D問題解決レポート_html/css_WEB-ITnose

D. パシュマクとパルミダの問題

テストごとの制限時間

3 秒

テストごとのメモリ制限

256 メガバイト

入力

標準入力

出力

標準出力

Parmida彼女は賢い女の子で、今年オリンピックに参加したいと思っています。もちろん、彼女はパートナーにも賢くなることを望んでいます（彼はそうではありませんが）！ Parmida は、Pashmak 用に次のテスト問題を用意しました。

n 個の整数 a1,?a2,?...,?an で構成されるシーケンス a があります。 f(l,?r,?x) を、l?≤?k?≤?r かつ ak?=?x となるようなインデックス k の数と表します。彼のタスクは、f(1,?i,?ai)?>?f(j となるようなインデックスのペア i,?j (1?≤?i?

Help Pashmak with the test.

入力

入力の最初の行には、整数 n (1?≤?n?≤?106) が含まれています。 2 行目には、n 個のスペースで区切られた整数 a1,?a2,?...,?an (1?≤?ai?≤?109) が含まれています。

出力

単一の整数を出力します。問題の答え。

サンプルテスト

入力

rree

出力

入力

71 2 1 1 2 2 1

出力

入力

31 1 1

出力

目大意:

は数値集合 A を出力し、f(l,r,x) は A[] の下から r までの間、x に相当する要素数と定義します。i と j 符合 f (1,i,a[i])>f(j,n,a[j])，求有多少对这样的(i,j).

解法：

我们可通过前処理として、O(n) 以内で、f(1, i, a[i]) の定数群が l[i] であると計算され、f(j, n, a[j]) の定数群が r[i] であると計算されます。

目標は次のように変換されます: 求出 l[i] > r[j] (i