Задача 2 от конкурса на PC Magazine & Musala Soft
(2002/2003 г.)
СТАТИСТИКА
Най-новият клиент на Монблан Ложи е статистическата фирма
Фън-стат. При едно от провежданите от Фън-стат изследвания се
получават голямо количество цели числа, като характеристики на
изследваните обекти – по едно число за всеки обект. При това доста
често се появяват нови обекти, а някои от старите не са актуални и
не са от интерес за текущото състояние. В никой момент не е нужно
да се съхраняват два или повече обекта с еднаква характеристика;
но след изключването на обект с дадена характеристика, след време
може да се появи друг обект със същата характеристика. Във всеки
момент броят на актуалните обекти е не повече от 4 000 000. При
изготвянето на резултатите (например в хистограма) за някакъв
текущ момент, естествен е въпросът: колко актуални в момента
обекта имат характеристика в зададен интервал? Като съвсем наскоро
назначен програмист Пиер получи тази лесна задача. Той трябва да
направи програма, която да регистрира нови числа (характеристики
на обекти), да изтрива числа от текущите (характеристики на
неактуални обекти), както и да намира броя на обектите, чиито
характеристики са в зададен целочислен интервал.
Входните данни са зададени в текстов файл STAT.INP. Всеки ред на
входния файл съдържа една от командите:
1 N – добави обект с характеристика числото N.
2 N – изтрий обект с характеристика числото N.
3 М N – намери броя на обектите с характеристика, намираща се в
затворения интервал [M,N].
4 – край на входните данни.
Входният файл винаги съдържа команда за край на входните данни и
тя е на последния ред. Числата N и М ще са между 1 и 4 000 000 000
включително.
Изходът на програмата трябва да е в текстовия файл STAT.OUT, който
съдържа по един ред за всяка команда, различна от командата за
край на входните данни. За командата добави се извежда 1, ако няма
актуален обект с тази характеристика (тогава се добавя обект с
тази характеристика) или 0, ако е имало обект с такава
характеристика (в този случай командата не променя броя на
съхранените обекти). За командата изтрий се извежда 1, ако е
изтрит обект с дадената характеристика или 0, ако не е имало обект
с тази характеристика (и в този случай командата не променя броя
на съхранените обекти). За командата намери се извежда търсеният
брой. Пиер се справи и с тази задача, а Вие?
Пример
STAT.INP
1 10
1 5
1 7
1 5
3 1 10
2 5
3 1 10
2 5
4
STAT.OUT
1
1
1
0
3
1
2
0