Problem
自然数 a
1、 a
2、 ...、 a
n の配列があります。その一部の部分配列 a
l、 a
l + 1、 ...、 a
r、を考えてみましょう。ここで、1<≤ l ≤ r ≤ n、および各自然数 s は、この部分配列内の数値 s の出現数を K
s で示します。部分配列の基数を、すべての個別の整数 s の積 Ks·Ks·s の合計と呼びましょう。配列内の異なる数値の数は有限であるため、合計には有限数の非ゼロ項のみが含まれます。
指定された t 個の部分配列のそれぞれのカーディナリティを計算する必要があります。
入力
最初の行には、2 つの整数 n と t (1&hl; n, t ≤ 200000) が含まれています。それぞれ配列の長さとリクエストの数。
2 行目には n 個の自然数 ai (1≤ ai ≤ 106) — が含まれています。配列要素。
次の t 行には、2 つの正の整数 l と r (1<<<l<≤ r ≤ n) が含まれます。対応する部分配列の左端と右端のインデックス
インプリント
t 行を出力します。i 行目には唯一の自然数が含まれます。 i 番目のクエリ部分配列のカーディナリティ。
例:
<本体>
| 入力 |
出力 |
3 2
1 2 1
1 2
1 3
| 3
6 |
8 3
1 1 2 2 1 3 1 1
27
16
27号
| 20
20
20 |