Pilləkən Qaydaları#4073

Pilləkən Qaydaları (Həll təhlili)

Pilləkənlər üzərində yazılmış ədədlər tam ədədlərdir və $0$ -dan $1 0^{6}$ 10^6-ya kimi (daxil olmaqla) aralıqdadır. $1 0^{6} + 1$ 10^6 + 1 uzunluğunda sıfırlarla doldurulmuş $a$ massivində Fenwick ağacını quracağıq (massivin indeksləri $0$ -dan $1 0^{6}$ 10^6-ya kimi dəyişir).

Hər dəfə dedektiv dəyəri $v a l u e$ olan bir pilləkəndən keçəndə, $a_{v a l u e}$ a_{value}-ı $v a l u e$ qədər artıracağıq. Həmin vaxt gündəlikdə o, məbləğini yazacaq:

a_{0} + a_{1} + a_{2} + ... + a_{v a l u e - 1}

a_0 + a_1 + a_2 + ... + a_{value - 1}

Giriş verilənlərinin məhdudiyyətlərini nəzərə alaraq, bütün hesablamaları $64$ bitlik tam ədəd tipində yerinə yetirmək lazımdır.

Məsələnin nümunəsi

Verilmiş nümunəni istifadə edərək dedektivin yazılarını simulyasiya edək. Massivin indeksləşdirilməsi $0$ -dan başlayır. Dedektiv tərəfindən yazılmış ədədlər oxların altında yerləşdirilib.

Dedektivin gündəliyində yazılmış ədədlərin cəmi bərabərdir:

0 + 1 + 1 + 9 + 4 = 15

0 + 1 + 1 + 9 + 4 = 15

Alqoritmin realizasiyası

Qoy massivin maksimal ölçüsü $M A X$ olsun. Fenwick ağacını yaradaq.

#define MAX 1000001
vector<long long> Fenwick;

Summa0_i funksiyası $a_{0} + a_{1} + ... + a_{i}$ a_0 + a_1 + ... + a_i cəm məbləğini hesablayır.

long long Summma0_i(int i)
{
  long long result = 0;
  for (; i >= 0; i = (i & (i + 1)) - 1)
    result += Fenwick[i];
  return result;
}

C++

IncElement funksiyası elementi artırır: $a_{i} = a_{i} + d e l t a$ a_i = a_i + delta.

void IncElement(int i, int delta)
{
  for (; i < MAX; i = (i | (i+1)))
    Fenwick[i] += delta;
}

Proqramın əsas hissəsi. Giriş verilənlərini oxuyuruq.

scanf("%d",&tests);
while (tests--)
{
  scanf("%d",&n);

$F e n w i c k$ Fenwick massivini sıfırlarla doldururuq.

  Fenwick.assign(MAX,0);

Dedektivin gündəliyində yazılmış olan nəticəni $s u m$ dəyişənində hesablayacağıq.

  sum = 0;

Pilləkənlər üzərində yazılmış ədədləri ardıcıl emal edirik.

  for (i = 0; i < n; i++)
  {

Hər pilləkən üzərinə yazılmış $v a l u e$ dəyəri üçün, $a_{v a l u e}$ a_{value}-ı $v a l u e$ -a artırırıq, həmçinin $v a l u e$ -dan kiçik olan daha əvvəl görülmüş bütün ədədlərin cəmini hesablayırıq. Bu cəm $a_{0} + a_{1} + a_{2} + ... + a_{v a l u e - 1}$ a_0 + a_1 + a_2 + ... + a_{value - 1}-ə bərabərdir.

    scanf("%d",&value);
    IncElement(value, value);
    sum += Summma0_i(value - 1);
  }

Dedektivin gündəliyində yazılmış bütün ədədlərin cəmini çıxarıq.

  printf("%lld\n",sum);
}