Statistika sevənlər üçün (Həll təhlili)

Tutaq ki, $v$ massivində tramvaylarla daşınan insanların sayı haqqında statistik məlumatlar var. Daşınan insanlar sayına görə hər $x$ üçün həmin dəyərin göründüyü indekslərin vektorunu saxlayırıq. Başqa sözlə, map təsvirində $p[x]$, il ərzində dəqiq olaraq $x$ insan daşınan şəhərlərin nömrələrini saxlayır.

Sorğu (l, r, x) formasında aşağıdakı kimi işə salınır:

• Əgər $x$ dəyəri map strukturunda yoxdursa, dərhal '$0$' qaytarırıq.

• Əks halda, ikili axtarış lower_bound ilə $p[x]$ massivində $l$-dən kiçik olmayan ilk indeksə baxırıq.

• Əgər tapılan indeks $r$-dən böyük deyil, deməli, şəhərlər arasında $l$-dan $r$-ə qədər olan nömrələr arasında $x$ dəyəri həqiqətən mövcuddur.

Misal

Birinci misal üçün $p$ strukturunun necə görünəcəyinə baxaq.

• p[123] = \{1\};

• p[314] = \{3\};

• p[434] = \{5\};

• p[666] = \{2, 4\};

Məsələn, (1, 5, 314) sorğusunu yaymaq üçün aşağıdakı addımları edin:

• $p[314]$ massivinin mövcudluğunu yoxlayırıq;

• Daha sonra ikili axtarış istifadə edərək, $p[314]$ massivində l = 1-dən kiçik olmayan ən kiçik dəyəri tapırıq. Bu halda bu dəyər $1$-dir.

• Çünki r = 5-dən çox deyil, cavab olaraq '$1$' qaytarılır.

Alqoritmin realizə olunması

İstifadə olunan məlumat strukturlarını yaradaq:

• $v$ massivi tramvaylarla daşınmış insanların sayını saxlayır;

• $p$ təsviri isə $v$ daxilində tapılan hər $x$ dəyəri üçün indekslərin (pozisiyalar) siyahısını saxlayır.

vector<int> v;
map<int, vector<int>> p;

Giriş məlumatları oxuyuruq.

cin >> n;
v.resize(n + 1);
for (i = 1; i <= n; i++)
{
  cin >> v[i];

$i$ nömrəli şəhərdə $v[i]$ insan daşınıb. Şəhərlər $1$-dən başlayaraq nömrələnir.

  p[v[i]].push_back(i);
}

Sorğu sayını $q$ oxuyuruq.

cin >> q;

Cavabı $result$ sətirində yaradacağıq.

result = "";

Ardıcıllıqla $q$ sorğularını (l, r, x) emal edirik.

for (i = 0; i < q; i++)
{
  cin >> l >> r >> x;

Əgər heç bir şəhərdə $x$ qədər sərnişin daşınmayıbsa, cavaba '$0$' yazırıq.

  if (p.find(x) == p.end())
  {
    result += '0';
    continue;
  }

$p[x]$ massivində $l$-dən $r$-ə qədər olan ən az bir rəqəmin olub-olmadığını müəyyən etməliyik. $p[x]$ daxilində $l$-dən kiçik olmayan ilk tapılanı axtarırıq.

  vector<int>::iterator it = lower_bound(p[x].begin(), p[x].end(), l);

Əgər belə bir rəqəm mövcuddursa və $r$-dən böyük deyilsə, cavaba '$1$' yazırıq.

  if (it != p[x].end() && *it <= r)
    result += '1';
  else
    result += '0';
}

Cavabı çap edirik.

cout << result << endl;