Оля та площина#8370
Оля — зразковий розв'язувач задач, яка щодня приймає нові виклики. Проте працювати з дому їй майже неможливо, адже її пустотливий кіт Костянтин завжди готовий нашкодити. Коли Оля отримала на день народження велике біле полотно декартової площини, Костянтин одразу вирішив зіпсувати цей чудовий подарунок.
Площина — це білий квадрат із лівим нижнім кутом у точці та правим верхнім кутом у точці (N, N). Для зручності Оля розміщує по пляшці з чорнилом у кожному куті, тобто в точках , , та (N, N), і сідає писати складну олімпіаду.
Поки Оля працює над задачами, Костянтин може "випадково" перекинути будь-яку пляшку з чорнилом. У результаті прямокутна ділянка між пляшкою та точкою на площині буде повністю залита чорнилом. Звісно, Оля засмучується, але змушена наповнити пляшку і знову повернутися до задач. Далі Костянтин може знову пролити чорнило, затопивши нову область площини.
Іноді, коли Оля стикається з особливо складною задачею, вона вирішує занотувати свої думки на якійсь ділянці площини. Для нотаток вона завжди обирає прямокутник, паралельний осям координат. Звісно, Оля хоче знати, яка частина обраної області вже вкрита чорнилом. Оскільки на олімпіаді вона зайнята розв'язуванням задач, їй потрібна ваша допомога.
Напишіть програму, яка допоможе Олі визначити площу зафарбованої частини площини на основі подій, що відбулися під час олімпіади.
У першому рядку задано два цілих числа та (1 \le N, Q \le 10^5) — розмір площини та кількість подій під час змагання.
Кожен із наступних рядків описує одну подію. Кожний рядок починається з цілого числа , яке вказує тип події.
Якщо 1 \le t \le 4, це означає, що Костянтин проливає відповідну пляшку чорнила. У цьому випадку додаються два цілих числа та (0 \le x, y \le N), які задають протилежну вершину області, яка буде зафарбована в чорний.
Перша пляшка чорнила знаходиться в лівому нижньому куті, друга — в правому нижньому, третя — у лівому верхньому, а четверта — у правому верхньому куті.
Якщо t = 0, додаються чотири цілих числа x_1, y_1, x_2, y_2 (0 \le x_1 < x_2 \le N, 0 \le y_1 < y_2 \le N) — Оля обирає прямокутник, паралельний осям координат, із протилежними вершинами у точках (x_1, y_1) та (x_2, y_2).
Гарантується, що у вхідних даних буде хоча б одна подія типу , а кіт проливає чорнило лише на прямокутники додатної площі.
Для кожного запиту типу виведіть у окремому рядку одне ціле число — площу відповідної частини площини, яка вже покрита чорнилом. Відповіді виводьте у порядку появи запитів у вхідних даних.
Приклад 1
Підзадача | Балів | Додаткові обмеження | Обов'язкові підзадачі |
|---|---|---|---|
0 | 0 | Тести із умови | - |
1 | 5 | 1 \le N, Q \le 100 | 0 |
2 | 6 | 1 \le N, Q \le 1000, t \in \{ 0, 1, 2 \} | - |
3 | 8 | 1 \le N, Q \le 1000 | 0, 1, 2 |
4 | 14 | 1 \le N, Q \le 50000, кількість запитів типу не більше | 0 |
5 | 12 | 1 \le N, Q \le 50000, t \in \{ 0, 1 \}, для всіх запитів типу : якщо запит йде після , то x_a \le x_b, y_a \ge y_b | - |
6 | 8 | 1 \le N, Q \le 50000, t \in \{ 0, 1 \} | - |
7 | 10 | 1 \le N, Q \le 50000, t \in \{ 0, 1, 2 \} | 2, 5, 6 |
8 | 13 | 1 \le N, Q \le 50000 | 0, 1, 2, 3, 4, 5, 6, 7 |
9 | 9 | t \in \{ 0, 1 \} | 5, 6 |
10 | 8 | t \in \{ 0, 1, 2 \} | 2, 5, 6, 7, 9 |
11 | 7 | Без додаткових обмежень | 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 |
