[蓝桥杯 2022 省 A] 推导部分和

Luogu

IDLGP8779

Time1000ms

Memory128MB

DifficultyP4

并查集2022图论建模蓝桥杯省赛

对于一个长度为 $N$ 的整数数列 $A_{1}, A_{2}, \cdots A_{N}$，小蓝想知道下标 $l$ 到 $r$ 的部分和 $\sum\limits_{i=l}^{r}A_i=A_{l}+A_{l+1}+\cdots+A_{r}$ 是多少? 然而，小蓝并不知道数列中每个数的值是多少，他只知道它的 $M$ 个部分和的值。其中第 $i$ 个部分和是下标 $l_{i}$ 到 $r_{i}$ 的部分和 $\sum_{j=l_{i}}^{r_{i}}=A_{l_{i}}+A_{l_{i}+1}+\cdots+A_{r_{i}}$, 值是 $S_{i}$ 。 ## Input 第一行包含 $3$ 个整数 $N, M$ 和 $Q$。分别代表数组长度、已知的部分和数量和询问的部分和数量。接下来 $M$ 行，每行包含 $3$ 个整数 $l_{i}, r_{i}, S_{i}$。接下来 $Q$ 行，每行包含 $2$ 个整数 $l$ 和 $r$，代表一个小蓝想知道的部分和。 ## Output 对于每个询问, 输出一行包含一个整数表示答案。如果答案无法确定, 输出 `UNKNOWN`。 [samples] ## Note 对于 $10 \%$ 的评测用例, $1 \leq N, M, Q \leq 10,-100 \leq S_{i} \leq 100$ 。对于 $20 \%$ 的评测用例, $1 \leq N, M, Q \leq 20,-1000 \leq S_{i} \leq 1000$ 。对于 $30 \%$ 的评测用例, $1 \leq N, M, Q \leq 50,-10000 \leq S_{i} \leq 10000$ 。对于 $40 \%$ 的评测用例, $1 \leq N, M, Q \leq 1000,-10^{6} \leq S_{i} \leq 10^{6}$ 。对于 $60 \%$ 的评测用例, $1 \leq N, M, Q \leq 10000,-10^{9} \leq S_{i} \leq 10^{9}$ 。对于所有评测用例, $1 \leq N, M, Q \leq 10^{5},-10^{12} \leq S_{i} \leq 10^{12}, 1 \leq l_{i} \leq r_{i} \leq N$, $1 \leq l \leq r \leq N$ 。数据保证没有矛盾。蓝桥杯 2022 省赛 A 组 J 题。

Samples

Input #1

Output #1

15
6
UNKNOWN

API Response (JSON)

{
  "problem": {
    "name": "[蓝桥杯 2022 省 A] 推导部分和",
    "description": {
      "content": "对于一个长度为 $N$ 的整数数列 $A_{1}, A_{2}, \\cdots A_{N}$，小蓝想知道下标 $l$ 到 $r$ 的部分和 $\\sum\\limits_{i=l}^{r}A_i=A_{l}+A_{l+1}+\\cdots+A_{r}$ 是多少? 然而，小蓝并不知道数列中每个数的值是多少，他只知道它的 $M$ 个部分和的值。其中第 $i$ 个部分和是下标 $l_{i}$ 到 $r_{i",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8779"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "对于一个长度为 $N$ 的整数数列 $A_{1}, A_{2}, \\cdots A_{N}$，小蓝想知道下标 $l$ 到 $r$ 的部分和 $\\sum\\limits_{i=l}^{r}A_i=A_{l}+A_{l+1}+\\cdots+A_{r}$ 是多少?\n\n然而，小蓝并不知道数列中每个数的值是多少，他只知道它的 $M$ 个部分和的值。其中第 $i$ 个部分和是下标 $l_{i}$ 到 $r_{i...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments