Пять задач, где всё запоминает множество: сколько различных чисел или слов, есть ли что-то в списке и какие буквы встречаются на участке строки, которая всё время меняется.
- «Сколько различных?» — вставьте всё в множество и выведите
s.size(). Со словами это тоже работает:set<string>. - Для вопросов о списке сначала сложите весь список в множество, а потом
отвечайте на каждый вопрос с помощью
count. - Номера бабочек доходят до 2·10⁹. Это ещё помещается в
int(его предел — около 2,1·10⁹), ноlong longничего не стоит и снимает все сомнения. - До 3·10⁵ слов и 3·10⁵ вопросов: используйте строки быстрого ввода-вывода и
"\n". - Для букв заведите по множеству позиций на каждую букву. Замена переносит одну
позицию из множества старой буквы в множество новой; вопрос проверяет все 26
букв через
lower_bound.