Range Counting (EXPERT)

2 secs 1024 MB
Shirotsume's icon Shirotsume

問題文

この問題は Range Counting (BASIC) と問題設定が同じですが,NN の制約が異なります.

長さ NN の正整数列 A=(A1,A2,,AN)A = (A_1, A_2, \dots, A_N) と,22 つの整数 L,RL, R が与えられます.

1i<jN1 \leq i \lt j \leq N を満たす整数の組 (i,j)(i, j) であって,Ai+AjA_i + A_j の値が LL 以上 RR 以下であるものの個数を求めてください.

制約

  • 入力はすべて整数
  • 1N2×1051 \leq N \leq 2 \times 10^5
  • 1Ai1091 \leq A_i \leq 10^9
  • 1LR1091 \leq L \leq R \leq 10^9

入力

入力は以下の形式で標準入力から与えられる.

N L R
A_1 ... A_N

出力

答えを 11 行で出力せよ.

サンプル

入力1
4 9 13
4 5 9 2
出力1
3

すべてのペアを列挙すると,次の通りになります.

  • (A1,A2)(A_1, A_2) : A1+A2=9A_1 + A_2 = 9
  • (A1,A3)(A_1, A_3) : A1+A3=13A_1 + A_3 = 13
  • (A1,A4)(A_1, A_4) : A1+A4=6A_1 + A_4 = 6
  • (A2,A3)(A_2, A_3) : A2+A3=14A_2 + A_3 = 14
  • (A2,A4)(A_2, A_4) : A2+A4=7A_2 + A_4 = 7
  • (A3,A4)(A_3, A_4) : A3+A4=11A_3 + A_4 = 11

よって,このうち 99 以上 1313 以下のものは 33 つあるので,33 が答えです.

入力2
4 2 2
1 1 1 1
出力2
6

すべてのペアが条件を満たします.

入力3
7 6 9
3 1 4 1 5 9 2
出力3
7

提出


Go (1.21)