P9279 [AGM 2023 Qualifier] IPs

Mike has just found an internship at the DNS department of a local Internet Service Provider. They know Mike is familiar with IPs, so they asked him to implement a management system for their customers that supports some operations. Some operations are client-specific, while others are specific to the DNS (the company). Mike is actually not very familiar with IPs, so he asks you for help.

The value range of IPs is from $0$ to $10^9$, and initially all clients can use all IPs. There are $N$ countries (indexed from $0$ to $N-1$). Each country has its own IP set, which can be formally represented as the union of several intervals. There are $M$ clients (indexed from $0$ to $M-1$) that Mike needs to help. There are $Q$ operations of the following types: 1. Add a country to the blacklist of all clients. Blacklisting a country blocks all IPs that belong to this country and any countries merged with it. 2. Add the IP interval $[X, Y]$ to the blacklist of all clients. 3. For a specific client, add a country and any countries merged with it to the blacklist. 4. For a specific client, add the IP interval $[X, Y]$ to the blacklist. 5. For a specific client, add a country and any countries merged with it to the whitelist. Whitelisting a country adds all IPs that belong to this country and any countries merged with it to the whitelist. Note that the whitelist has higher priority than any previous or future blacklist for this client. That is, if an IP is whitelisted for a client, it will never be affected by any blacklist operations before or after. 6. For a specific client, add the IP interval $[X, Y]$ to the whitelist. Note that the whitelist has higher priority than any previous or future blacklist for this client. That is, if an IP is whitelisted for a client, it will never be affected by any blacklist operations before or after. 7. Countries $X$ and $Y$ are merged together. 8. Query how many IPs a client can access within the interval $[X, Y]$.

The first line contains three integers $N, M, Q$. It is guaranteed that $1\leq N\leq 10^4$, $1\leq M\leq 10$, $1\leq Q\leq 10^5$. In the next $N$ lines, the first integer $N_i$ indicates that the IP set of the $i$-th country is the union of $N_i$ intervals. Then $2\times N_i$ integers follow to describe these intervals. These numbers are between $0$ and $10^9$. It is guaranteed that $\sum N_i\leq 10^5$. In the next $Q$ lines, the first integer indicates the operation type. Then the corresponding parameters for each operation are given: 1: $countryIdx$, with $0≤countryIdx

For each query, output one line with the answer.

Translated by ChatGPT 5