Вы никогда не
задумывались, сколько человек за год перевозят трамваи в городе с населением
десять миллионов, если каждый третий житель пользуется трамваем дважды в день?
Предположим, что
на планете Земля имеется n городов, в которых действуют
трамвайные линии. Любители статистики подсчитали для каждого из этих городов,
сколько человек перевезли трамваи за последний год. На основе этих данных была
составлена таблица, в которой города были отсортированы по алфавиту.
Впоследствии выяснилось, что для статистических задач названия городов
несущественны, поэтому их просто заменили числами от 1 до n.
Поисковая
система, работающая с этими данными, должна уметь быстро отвечать на запрос:
существует ли среди городов с номерами от l до r хотя бы один, в котором трамваи
за год перевезли ровно x человек?
Вам предстоит
реализовать этот модуль системы.
Вход. В первой строке
задано одно целое число n (0 < n < 70000) – количество городов.
Во второй строке
содержатся n натуральных чисел – статистические
данные, где i-е число обозначает количество человек, перевезённых
трамваями i-го города за последний год. Все значения не превышают 109 – 1.
В третьей строке
задано целое число q (0 < q < 70000) – количество запросов.
В
следующих q строках описаны сами запросы. Каждый запрос
состоит из трёх целых чисел l, r и x (1 ≤ l ≤ r ≤ n; 0 < x < 109).
Выход. Выведите строку из q символов. i-й символ строки
должен быть равен ‘1’, если существует хотя бы один город с номером от l до r,
в котором трамваи перевезли ровно x человек. В противном
случае выведите ‘0’.
|
Пример
входа |
Пример
выхода |
|
5 123 666 314
666 434 5 1 5 314 1 5 578 2 4 666 4 4 713 1 1 123 |
10101 |
бинарный
поиск
Пусть массив 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;