[ICPC 2022 Xi'an R] Bridge

Luogu

IDLGP9358

Time2000ms

Memory512MB

DifficultyP6

平衡树2022O2优化动态树 LCTICPC西安

There are $n$ countries numbered from $1$ to $n$ in Erathia. Each country can be regarded as a chain with $m+1$ nodes numbered from $1$ to $m+1$. Initially, node $(a, b)$ is connected with node $(a, b + 1)$ by a street where node $(a, b)$ denotes the $b$-th node of the $a$-th country. There are no bridges between any two countries at first. You need to process $q$ queries of the following two types. - $1\ a\ b$ ($1\leq a < n, 1\leq b\leq m$). Build a bridge between node $(a, b)$ and node $(a + 1, b)$. It is guranteed that at any time, **each node is connected with at most one bridge**. - $2\ a$ ($1\leq a\leq n$). A hero will walk through Erathia. This hero starts from $(a, 1)$. If the hero is at $(x, y)$ and there is a unvisited bridge connected to him, he passes it, or he goes to $(x, y + 1)$. Once he arrived the $(m+1)$-th node of any conutry, he stops. Please note that 'unvisited bridge' is **independently** judged for each query. Your task is to print which country the hero is in at last for the second kind of query. It can be proved that the hero's route is always unique under these constraints. ## Input The first line contains three integers $n$, $m$ and $q$ ($1 \leq n, m, q \leq 10 ^ 5$). Each of the following $q$ lines represents a query with format described above. ## Output For each query of type $2$, output a line with an integer representing the answer. [samples] ## Note **Source**: The 2022 ICPC Asia Xi'an Regional Contest Problem A. **Author**: MonkeyKing.

Samples

Input #1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[ICPC 2022 Xi'an R] Bridge",
    "description": {
      "content": "There are $n$ countries numbered from $1$ to $n$ in Erathia. Each country can be regarded as a chain with $m+1$ nodes numbered from $1$ to $m+1$. Initially, node $(a, b)$ is connected with node $(a, b",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9358"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There are $n$ countries numbered from $1$ to $n$ in Erathia. Each country can be regarded as a chain with $m+1$ nodes numbered from $1$ to $m+1$. Initially, node $(a, b)$ is connected with node $(a, b...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments