Для любителів статистики (Розбір)

Нехай масив $v$ містить статистичні дані про кількість людей, перевезених трамваями. Для кожної кількості перевезених людей $x$ ми зберігаємо вектор індексів, на яких це значення зустрічається. Іншими словами, в map відображенні $p[x]$ зберігаються номери міст, в яких за рік було перевезено рівно $x$ осіб.

Запит вигляду (l, r, x) обробляється наступним чином:

• Якщо значення $x$ відсутнє у структурі map, відразу виводимо '0'.

• В іншому випадку за допомогою бінарного пошуку lower_bound знаходимо в масиві $p[x]$ перший індекс, не менший $l$.

• Якщо знайдений індекс не перевищує $r$, значить значення $x$ дійсно зустрічається серед міст з номерами від $l$ до $r$.

Приклад

Розглянемо, як виглядатиме структура $p$ для першого прикладу.

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

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

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

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

Наприклад, для обробки запиту (1, 5, 314) необхідно виконати наступні кроки:

• Перевірити, чи існує масив $p[314]$;

• Потім, використовуючи бінарний пошук в масиві $p[314]$, знайти найменше значення, не менше l = 1. У даному випадку це число $1$.

• Оскільки воно не перевищує r = 5, відповідь на запит '1'.

Реалізація алгоритму

Оголосимо використовувані структури даних:

• Масив $v$ зберігає статистичні дані про кількість перевезених трамваями людей;

• Відображення $p$ містить для кожного значення $x$, що зустрічається у вхідному масиві $v$, список індексів (позицій), на яких це значення зустрічається.

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

Читаємо вхідні дані.

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

У місті номер $i$ перевезено $v[i]$ людей. Міста нумеруємо починаючи з $1$.

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

Читаємо кількість запитів $q$.

cin >> q;

Відповідь будемо генерувати в рядку $result$.

result = "";

Послідовно обробляємо $q$ запитів (l, r, x).

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

Якщо $x$ пасажирів не перевозилося в жодному місті, то в відповідь записуємо '0'.

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

Необхідно визначити, чи є в масиві $p[x]$ хоча б одне число від $l$ до $r$. Шукаємо перше входження в $p[x]$, не менше $l$.

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

Якщо таке число присутнє і воно не більше $r$, то в відповідь записуємо '1'.

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

Виводимо відповідь.

cout << result << endl;