[语言月赛 202409] 距离

Luogu

IDLGB4030

Time1000ms

Memory512MB

DifficultyP1

2024O2优化数组语言月赛

迅风的班上一共有 $n$ 个人，学号为 $1\sim n$。每个同学都对班里其他所有同学有一个**好感度**，这个好感度始终是自然数。一开始每个人对其他人的**好感度**为 $0$。接下来在这个班级里按时间顺序发生了 $m$ 件事情。每件事情发生后，会让一位同学对另一位同学的好感度增加或减少。迅风想在**每一件事发生后**，立刻知道如果他随便选两个同学 $p,q$，那么 $p$ 对 $q$ 好感度的最大值是多少。你能帮帮他吗？注意：好感度不是相互的。$p$ 对 $q$ 的好感度可以不等于 $q$ 对 $p$ 的好感度。 ## Input 输入的第一行有两个正整数 $n,m$，分别表示同学的人数和事情的个数。之后有 $m$ 行，每行有四个正整数 $op,a,b,c$ 描述一次事情。 - 如果 $op$ 为 $1$，表示事情发生后，$a$ 号同学对 $b$ 号同学的好感度增加了 $c$。 - 如果 $op$ 为 $2$，表示事情发生后，$a$ 号同学对 $b$ 号同学的好感度减少了 $c$。 ## Output 输出共 $m$ 行，每行一个整数，表示一个同学对另一个同学的好感度最大值。 [samples] ## Note **【样例 1 解释】** 班里有 $2$ 位同学，发生了 $3$ 件事情。下面用表格来整理这三件事情。 |事情编号|事情效果|$1$ 对 $2$ 好感度|$2$ 对 $1$ 好感度|输出数字| |:-:|:-:|:-:|:-:|:-:| |初始||$0$|$0$|| |$1$|$1$ 对 $2$ 的好感度增加 $4$|$4$|$0$|$4$| |$2$|$2$ 对 $1$ 的好感度增加 $6$|$4$|$6$|$6$| |$3$|$2$ 对 $1$ 的好感度减少 $3$|$4$|$3$|$4$| **【数据范围】** |测试点编号|$n\le$|$m\le$|特殊性质| |:-:|:-:|:-:|:-:| |$1\sim 4$|$10$|$10$|无| |$5\sim 7$|$100$|$100$|每个事情发生前，$a$ 对 $b$ 好感度都是 $0$（只有一件事情会影响 $a$ 对 $b$ 的好感度）| |$8\sim 11$|$100$|$100$|对于每个事情，都有 $a=1$| |$12\sim 15$|$100$|$100$|保证 $op=1$| |$16\sim 20$|$100$|$100$|无| 对于所有数据，保证 $2\le n\le 100$，$1\le a,b\le n$，$1\le c\le 10^5$，且任意时刻任何人对其他所有人的好感度都是自然数。

Samples

Input #1

Output #1

4
6
4

API Response (JSON)

{
  "problem": {
    "name": "[语言月赛 202409] 距离",
    "description": {
      "content": "迅风的班上一共有 $n$ 个人，学号为 $1\\sim n$。每个同学都对班里其他所有同学有一个**好感度**，这个好感度始终是自然数。一开始每个人对其他人的**好感度**为 $0$。 接下来在这个班级里按时间顺序发生了 $m$ 件事情。每件事情发生后，会让一位同学对另一位同学的好感度增加或减少。 迅风想在**每一件事发生后**，立刻知道如果他随便选两个同学 $p,q$，那么 $p$ 对 $q$",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P1"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB4030"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "迅风的班上一共有 $n$ 个人，学号为 $1\\sim n$。每个同学都对班里其他所有同学有一个**好感度**，这个好感度始终是自然数。一开始每个人对其他人的**好感度**为 $0$。\n\n接下来在这个班级里按时间顺序发生了 $m$ 件事情。每件事情发生后，会让一位同学对另一位同学的好感度增加或减少。\n\n迅风想在**每一件事发生后**，立刻知道如果他随便选两个同学 $p,q$，那么 $p$ 对 $q$...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments