『STA - R2』机场修建

Luogu
IDLGP9410
Time1000ms
Memory125MB
DifficultyP6
并查集O2优化分块根号分治
有 $n$ 个城市排成一列,最开始是互不连通的。 每个城市初始都没有人口。 会出现以下操作 / 查询共 $m$ 个: 1. `1 x y` 开通城市 $x$ 和城市 $y$ 之间的双向航班。 2. `2 l r a` 城市 $[l, r]$ 的人口数都 $+a$。 3. `3 x` **如果**所有能够到达城市 $x$ 的人都来到城市 $x$,城市 $x$ 有多少人。 ## Input 第一行两个数 $n, m$。 接下来 $m$ 行,每行一个操作。 ## Output 对于所有的操作 $3$ ,输出答案。 [samples] ## Background 智利在修机场。 ## Note **本题捆绑测试。** - Easy(5pts):$1 \le n, m \le 2 \times 10^5$,且不存在操作 $1$。 - Normal(10pts):$1 \le n, m \le 1000$。 - Hard(20pts):$1 \le n, m \le 10^5$,且操作 $3$ 之后不存在操作 $2$。 - Lunatic(30pts):$1 \le n, m \le 5 \times 10^4$。 - Overdrive(35pts):$1 \le n, m \le 2 \times 10^5$。 对于 $100\%$ 的数据,$1\le n,m\le 2\times 10^5$,$0 \le a \le 10^9$。保证答案在 64 位有符号整形表示的范围内。 ![](https://cdn.luogu.com.cn/upload/image_hosting/dgqoqa8d.png) 出于某些原因,给了较多的部分分。
Samples
Input #1
5 5
1 2 4
2 3 5 2
3 2
1 2 5
3 2
Output #1
2
4
API Response (JSON)
{
  "problem": {
    "name": "『STA - R2』机场修建",
    "description": {
      "content": "有 $n$ 个城市排成一列,最开始是互不连通的。   每个城市初始都没有人口。   会出现以下操作 / 查询共 $m$ 个:   1. `1 x y` 开通城市 $x$ 和城市 $y$ 之间的双向航班。   2. `2 l r a` 城市 $[l, r]$ 的人口数都 $+a$。   3. `3 x` **如果**所有能够到达城市 $x$ 的人都来到城市 $x$,城市 $x$ 有多少人。  ",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 128000
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9410"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "有 $n$ 个城市排成一列,最开始是互不连通的。  \n每个城市初始都没有人口。  \n会出现以下操作 / 查询共 $m$ 个:  \n\n1. `1 x y` 开通城市 $x$ 和城市 $y$ 之间的双向航班。  \n2. `2 l r a` 城市 $[l, r]$ 的人口数都 $+a$。  \n3. `3 x` **如果**所有能够到达城市 $x$ 的人都来到城市 $x$,城市 $x$ 有多少人。  \n\n...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments