BZOJ2759 一个动态树好题

Luogu
IDLGP10660
Time1000ms
Memory512MB
DifficultyP6
O2优化动态树 LCT扩展欧几里德算法
有 $n$ 个未知数 $x_1,x_2,\dots,x_n$ 和 $n$ 个等式组成的同余方程组:$x_i\equiv k_i\times x_{p_i} + b_i \pmod {10007}$。 你需要进行 $q$ 次操作,每次操作为下列两种情况之一: - `A a`,询问当前 $x_a$ 的解,无解输出 `-1`,多解输出 `-2` 否则输出 $x_a$。 - `C a x y z`,修改一个等式 $k_a \gets x,p_a \gets y,b_a \gets z$。 ## Input 第一行一个整数 $n$。 接下来 $n$ 行,每行三个整数 $k_i,p_i,b_i$。 接下来一行一个整数 $q$。 再接下来 $q$ 行,每行一个操作,见题意所述。 ## Output 对每个询问,输出一行一个整数。 [samples] ## Note 对于所有数据,$k_i,b_i,x_i \in [0,10007) \cap \Z$。$1\leq n\leq 3\times 10^4$,$0\leq q\leq 10^5$,其中询问操作占总操作数的约 $80\%$。
Samples
Input #1
5
2 2 1
2 3 2
2 4 3
2 5 4
2 3 5
5
A 1
A 2
C 5 3 1 1
A 4
A 5
Output #1
4276
7141
4256
2126
API Response (JSON)
{
  "problem": {
    "name": "BZOJ2759 一个动态树好题",
    "description": {
      "content": "有 $n$ 个未知数 $x_1,x_2,\\dots,x_n$ 和 $n$ 个等式组成的同余方程组:$x_i\\equiv k_i\\times x_{p_i} + b_i \\pmod {10007}$。 你需要进行 $q$ 次操作,每次操作为下列两种情况之一: - `A a`,询问当前 $x_a$ 的解,无解输出 `-1`,多解输出 `-2` 否则输出 $x_a$。 - `C a x y z`,修改",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10660"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "有 $n$ 个未知数 $x_1,x_2,\\dots,x_n$ 和 $n$ 个等式组成的同余方程组:$x_i\\equiv k_i\\times x_{p_i} + b_i \\pmod {10007}$。\n\n你需要进行 $q$ 次操作,每次操作为下列两种情况之一:\n- `A a`,询问当前 $x_a$ 的解,无解输出 `-1`,多解输出 `-2` 否则输出 $x_a$。\n- `C a x y z`,修改...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments