4-й этап Республиканской олимпиады по информатике 2020-2021, 2 тура

Есеп A. Мұнаралар

Ограничение по времени:

1.5 seconds

Ограничение по памяти:

256 megabytes

Тізбек бойында кубтардан құралған $n$ мұнара орнатылған. $i$-ші мұнара $a_i$ бірінің үстіне бірі тұрған кубтардан кұралған. Әр мұнараның биіктігі $k$ кубтан көп болмайтындығына кепіл беріледі. Кубтар екі түрлі бола алады — қатып калған және жай. Қатып калған кубқа гравитация әсер етпейді. Жай куб жерге немесе басқа кубтын үстіне түспегенше дейін құлай береді, ал қатып қалған куб сол биіктікте қатып тұрады. BThero сізден кезек-кезек үш түрлі $q$ сұрау береді.

1. Сізге бір $y$ саны беріледі, $y$ биіктігінде орналасқан барлық кубтар қатып калған кубқа айналады.
2. Сізге бір $y$ саны беріледі, $y$ биіктігінде орналасқан барлық кубтар жай кубқа айналады.
3. Сізге бір $y$ саны беріледі, $y$ биіктігінде жаңа лазер орнатылады. Осыған деін осы биіктікте ешқандай лазер орнатылмағанына кепіл беріледі. Лазердің нөмірі ең кіші басқа лазерлармен колданылмаған оң санға тең. Лазерді $y$ биіктігінде орналасқан горизонтал түзу ретінде елестетуге болады және сол лазерге тиген барлық кубтарды жояды. Егер лазер кубты жойса, және сол кубтын орнына гравиция заңы бойынша басқа жай куб құласа, ол кубта жойылады. Бұл процесс кайта қайталануы мүмкін.

Лазерлардын санын $m$ деп белгілейік. Барлық сұраулардан кейін әр лазердің қанша кубты жойғаның шығарыңыз.

Формат входного файла

Бірінші жолда үш бүтін $n$, $q$, $k$ сандары берілген — мұнаралардын саны, сұраулардың саны және мұнарадағы кубтардың санының шектеуі ($1 <= n, q <= 300000$, $1 <= k <= 10^9$). Екінші жолда $n$ бүтін $a_1$, \dots, $a_n$ сандары берілген ($1 <= a_i <= k$). Келесі $q$ жолда $t_i$, $y_i$ форматында сұраулар берілген — $i$-ші сұраудың түрі және сұраудың түріне байланысты сан($1 <= t_i <= 3$, $1 <= y_i <= k$).

Формат выходного файла

Пробелдармен бөлінген $m$ бүтін $c_1$, \dots, $c_m$ — әр лазердің жойған кубтардың санын шығарыңыз. $m > 0$ екеніне кіпілдік

Система оценки

Бұл есеп $7$ бөлімге бөлінеді.

1. Берілгендегі мысал. $0$ баллға бағаланады.
2. $n, k, q <= 100$. $15$ баллға бағаланады.
3. $n, k, q <= 5000$, $t_i = 3$ әр $1 <= i <= q$. $8$ баллға бағаланады.
4. $n, k, q <= 5000$. $13$ баллға бағаланады.
5. $k <= 300000$. $19$ баллға бағаланады.
6. $t_i \neq 2$ әр $1 <= i <= q$. $16$ баллға бағаланады.
7. Есептің бастапқы шектеулері. $29$ баллға бағаланады.

Пример:

Вход

4 5 8
5 2 4 7
1 5
3 2
3 3
2 5
3 1

Ответ

10 4 4

( Temirlan Baibolov )