4421. Для любителей статистики

Вы никогда не задумывались над тем, сколько человек за год перевозят трамваи города с десятимиллионным населением, в котором каждый третий житель пользуется трамваем по два раза в день?

   Предположим, что на планете Земля n городов, в которых есть трамваи. Любители статистики подсчитали для каждого из этих городов, сколько человек перевезено трамваями этого города за последний год. Из этих данных была составлена таблица, в которой города были отсортированы по алфавиту. Позже выяснилось, что для статистики названия городов несущественны, и тогда их просто заменили числами от 1 до n. Поисковая система, работающая с этими данными, должна уметь быстро отвечать на вопрос, есть ли среди городов с номерами от l до r такой, что за год трамваи этого города перевезли ровно x человек. Вам предстоит реализовать этот модуль системы.

Вход.  В первой строке дано целое число n, 0 < n < 70000. В следующей строке приведены статистические данные в виде списка целых чисел через пробел, i-е число в этом списке – количество человек, перевезенных за год трамваями i-го города. Все числа в списке положительны и не превосходят 10⁹ – 1 . В третьей строке дано количество запросов q (0 < q < 70000). В следующих q строках перечислены запросы. Каждый запрос – это тройка целых чисел l, r и x (1 ≤ l ≤ r ≤ n; 0 < x < 10⁹), записанных через пробел.

Выход. Выведите строку длины q, в которой i-й символ равен "1", если ответ на i-й запрос утвердителен, и "0" в противном случае.

Пример входа	Пример выхода
5 123 666 314 666 434 5 1 5 314 1 5 578 2 4 666 4 4 713 1 1 123	10101

РЕШЕНИЕ

бинарный поиск

Анализ алгоритма

Для каждого города создадим пару: количество перевезенных в нем людей и номер города. Отсортируем города по числу перевезенных людей (если оно одинаково, то сортируем города по возрастанию их номеров).

Для каждого запроса (l, r, x) ищем позицию пары (x, l) в массиве городов по нижней границе и позицию пары (x, r) по верхней границе. Если эти позиции совпадают, то ответ на запрос отрицательный. Иначе существует город, в котором перевезено в точности x людей, причем его номер лежит между l и r включительно.

Пример

Отсортируем города из примера по количеству перевезенных людей.

Рассмотрим первый запрос. Ищем место, куда можно вставить пару (314, 1) по нижней границе. Таковой будет позиция 1. Пару (314, 5) по верхней границе можно вставить в позицию 2. Поскольку позиции разные, то у нас существует город, в котором трамваи перевезли в точности 314 людей, причем номер этого города лежит между 1 и 5 включительно.

Во втором запросе соответствующая вставка пар (578, 1) и (578, 5) произойдет в одну и ту же – третью позицию. Ответ на запрос отрицательный.

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

Структура city содержит информацию об одном городе: в people находится количество перевезенных в нем трамваями людей, в num – номер соответствующего города. Массив a будет хранить информацию о городах.

#define MAX 70010

struct city

{

int people, num;

city(int people = 0, int num = 0)

{this->people = people; this->num = num;}

} a[MAX];

Сортируем города по увеличению числа перевезенных людей. Если городов с одинаковым количеством перевезенных людей несколько, то сортируем их по возрастанию номеров.

int f(city a, city b)

{

if(a.people == b.people) return a.num < b.num;

return a.people < b.people;

}

Ищем позицию Left пары city(x, l) по нижней границе и позицию Right пары city(x, r) по верхней границе. Если они совпадают – то искомого города не существует. Иначе существует город, в котором трамваи перевезли в точности x пассажиров, причем его номер лежит от l до r включительно.

int Query(int l, int r, int x)

{

int Left = lower_bound(a,a+n,city(x,l),f) - a;

int Right = upper_bound(a,a+n,city(x,r),f) - a;

return Left < Right;

}

Основная часть программы. Считываем информацию о перевезенных людях в городах.

scanf("%d",&n);

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

scanf("%d",&a[i].people), a[i].num = i + 1;

sort(a,a+n,f);

Обрабатываем q запросов.

scanf("%d",&q);

while(q--)

{

scanf("%d %d %d",&l,&r,&x);

printf("%d",Query(l,r,x));

}

printf("\n");