[NOISG 2019 Prelim] Experimental Charges

Luogu

IDLGP10734

Time2000ms

Memory512MB

DifficultyP4

2019并查集NOISG（新加坡）

现有 $N$ 个带电粒子，带正电子的粒子会和带负电子的粒子相互吸引，而带同一种电子的粒子会相互排斥。有 $Q$ 次操作，每次操作表示为 $T_i,A_i,B_i$，可根据 $T_i$ 的不同分为三种类型： - `A` 操作代表 $A_i,B_i$ 互相吸引。 - `R` 操作代表 $A_i,B_i$ 互相排斥。 - `Q` 操作询问按照目前已知的信息，如果 $A_i,B_i$ 放在一起，会发生什么。对于每个 `Q` 操作，如果互相吸引，输出 `A`；如果互相排斥，输出 `R`；如果无法确定，输出 `?`。保证至少有一种可能使得所有操作不冲突。 ## Input 第一行两个整数 $N,Q$。接下来的 $Q$ 行，每行一个字符 $T_i$ 与两个整数 $A_i,B_i$，表示一种操作。 ## Output 若干行，每行表示一次 `Q` 操作的回答。 [samples] ## Background 翻译自 [NOISG2019 Prelim C.Experimental Charges](https://github.com/noisg/sg_noi_archive/blob/master/2019_prelim/)。 ## Note ### 【样例 #1 解释】对于第一次询问，并不能确定 $1,2$ 之间的关系，输出 `?`。对于第二次询问，可以确定 $1,2$ 相斥，输出 `R`。 ### 【数据范围】 | $\text{Subtask}$ | 分值 | $N,Q$ | $T_i,A_i,B_i$ | | :----------: | :----------: | :----------: | :----------: | | $0$ | $7$ | $N=2,Q\leq 10$ | 无 | | $1$ | $11$ | 无 | $A_i=1$ 或 $B_i=1$ | | $2$ | $14$ | 无 | $T_i$ 仅可能为 `R` 或 `Q` | | $3$ | $12$ | 无 | 所有关系给出后才有查询操作 | | $4$ | $25$ | $1\leq N,Q \leq 10^3$ | 无 | | $5$ | $31$ | 无 | 无 | 对于 $100\%$ 的数据： - $1 \leq N,Q \leq 10^5$ - $1 \leq A_i \neq B_i \leq N$ - $T_i$ 仅可能为 `A`，`R` 或 `Q`。

Samples

Input #1

Output #1

?
R

Input #2

Output #2

A
A

API Response (JSON)

{
  "problem": {
    "name": "[NOISG 2019 Prelim] Experimental Charges",
    "description": {
      "content": "现有 $N$ 个带电粒子，带正电子的粒子会和带负电子的粒子相互吸引，而带同一种电子的粒子会相互排斥。 有 $Q$ 次操作，每次操作表示为 $T_i,A_i,B_i$，可根据 $T_i$ 的不同分为三种类型： - `A` 操作代表 $A_i,B_i$ 互相吸引。 - `R` 操作代表 $A_i,B_i$ 互相排斥。 - `Q` 操作询问按照目前已知的信息，如果 $A_i,B_i$ 放在一起，会发生",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10734"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "现有 $N$ 个带电粒子，带正电子的粒子会和带负电子的粒子相互吸引，而带同一种电子的粒子会相互排斥。\n\n有 $Q$ 次操作，每次操作表示为 $T_i,A_i,B_i$，可根据 $T_i$ 的不同分为三种类型：\n- `A` 操作代表 $A_i,B_i$ 互相吸引。\n- `R` 操作代表 $A_i,B_i$ 互相排斥。\n- `Q` 操作询问按照目前已知的信息，如果 $A_i,B_i$ 放在一起，会发生...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments