P7560 [JOISC 2021] Food Court (Day1)

If the testdata cannot be downloaded on Luogu, please obtain the complete data [here](https://www.ioi-jp.org/camp/2021/2021-sp-tasks/day1/foodcourt-data.zip).

There are $N$ Bookworm food shops, and $M$ families come to enjoy delicious food made from bookworms. Because the food shops are very popular, customers need to line up. At the beginning, all queues are empty. Today, all food shops open again, and $Q$ events occur: - **Join event**: In every food shop with an index in the interval $[L, R]$, family $C$ joins the back of the queue. For each food shop that meets the condition, $K$ people are added to the back of the queue. - **Leave event**: In every food shop with an index in the interval $[L, R]$, if the queue has more than $K$ people, then the first $K$ people leave the queue; otherwise, everyone in the queue leaves. - **Freebie event**: If the queue of food shop $A$ has at least $B$ people, then the food shop gives the $B$-th person counting from the front of the queue one special bookworm; otherwise, the staff member eats the bookworm. For each **Freebie event**, determine whether a customer receives a special bookworm. If yes, output which family the customer belongs to.

The first line contains three integers $N, M, Q$, representing the number of food shops, the number of families, and the number of events. In the next $Q$ lines, each line starts with an integer $T$: - If $T = 1$, then four integers $L, R, C, K$ follow, describing a **Join event**. - If $T = 2$, then three integers $L, R, K$ follow, describing a **Leave event**. - If $T = 3$, then two integers $A, B$ follow, describing a **Freebie event**.

For every **Freebie event**, output one integer per line: - If a customer is given a special bookworm, output the family the customer belongs to. - If the staff member eats the bookworm, output $0$.

#### Sample 1 Explanation We use $Q_i(a_1, a_2, \cdots, a_k)$ to denote the queue of the $i$-th food shop, where $a_1$ is the front and $a_k$ is the back. Here, $a_i = p$ means that the person at position $i$ comes from family $p$. In particular, $Q_i()$ means that the queue is currently empty. According to the events in Sample 1: - The $1$-st **Join event**: $$Q_1(),Q_2(5,5),Q_3(5,5)$$ - The $2$-nd **Join event**: $$Q_1(2,2,2,2),Q_2(5,5,2,2,2,2),Q_3(5,5)$$ - The $3$-rd **Freebie event**: the $3$-rd person in the $2$-nd food shop (from family $2$) is given a special bookworm. - The $4$-th **Leave event**: $$Q_1(2),Q_2(2,2,2),Q_3()$$ - The $5$-th **Freebie event**: the $1$-st food shop has fewer than $2$ people, so the staff member eats the bookworm. - The $6$-th **Join event**: $$Q_1(2),Q_2(2,2,2,4,4),Q_3(4,4)$$ - The $7$-th **Freebie event**: the $2$-nd person in the $3$-rd food shop (from family $4$) is given a special bookworm. #### Constraints and Notes **This problem uses bundled subtasks.** - Subtask 1 (2 pts): $N, Q \le 2000$, satisfies Property A. - Subtask 2 (5 pts): $N, Q \le 2000$. - Subtask 3 (7 pts): $N, Q \le 65000$, satisfies Property B. - Subtask 4 (21 pts): $M = 1$. - Subtask 5 (15 pts): $N, Q \le 65000$, satisfies Property A. - Subtask 6 (13 pts): $N, Q \le 65000$, satisfies Property C. - Subtask 7 (26 pts): $N, Q \le 65000$. - Subtask 8 (11 pts): no special restrictions. For $100\%$ of the data: - $1 \le N, M, Q \le 25 \times 10^4$. - $T \in \{1, 2, 3\}$. - For all **Join events**, $1 \le L \le R \le N$, $1 \le C \le M$, $1 \le K \le 10^9$. - For all **Leave events**, $1 \le L \le R \le N$, $1 \le K \le 10^9$. - For all **Freebie events**, $1 \le A \le N$, $1 \le B \le 10^{15}$. - There is at least one **Freebie event**. There are the following properties: - Property A: For all **Join events** and **Leave events**, $K = 1$. - Property B: For all **Join events**, $R - L \le 10$ and $K = 1$. - Property C: There are only **Join events** and **Freebie events**. #### Note Translated from [The 20th Japanese Olympiad in Informatics Spring Training Camp](https://www.ioi-jp.org/camp/2021/2021-sp-tasks/index.html) [Day1 C フードコート (Food Court) English version](https://www.ioi-jp.org/camp/2021/2021-sp-tasks/day1/foodcourt-en.pdf). Translated by ChatGPT 5