{"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$ 好感度的最大值是多少。你能帮帮他吗？\n\n注意：好感度不是相互的。$p$ 对 $q$ 的好感度可以不等于 $q$ 对 $p$ 的好感度。\n\n## Input\n\n输入的第一行有两个正整数 $n,m$，分别表示同学的人数和事情的个数。\n\n之后有 $m$ 行，每行有四个正整数 $op,a,b,c$ 描述一次事情。\n- 如果 $op$ 为 $1$，表示事情发生后，$a$ 号同学对 $b$ 号同学的好感度增加了 $c$。\n- 如果 $op$ 为 $2$，表示事情发生后，$a$ 号同学对 $b$ 号同学的好感度减少了 $c$。\n\n## Output\n\n输出共 $m$ 行，每行一个整数，表示一个同学对另一个同学的好感度最大值。\n\n[samples]\n\n## Note\n\n**【样例 1 解释】**\n\n班里有 $2$ 位同学，发生了 $3$ 件事情。下面用表格来整理这三件事情。\n\n|事情编号|事情效果|$1$ 对 $2$ 好感度|$2$ 对 $1$ 好感度|输出数字|\n|:-:|:-:|:-:|:-:|:-:|\n|初始||$0$|$0$||\n|$1$|$1$ 对 $2$ 的好感度增加 $4$|$4$|$0$|$4$|\n|$2$|$2$ 对 $1$ 的好感度增加 $6$|$4$|$6$|$6$|\n|$3$|$2$ 对 $1$ 的好感度减少 $3$|$4$|$3$|$4$|\n\n**【数据范围】**\n\n|测试点编号|$n\\le$|$m\\le$|特殊性质|\n|:-:|:-:|:-:|:-:|\n|$1\\sim 4$|$10$|$10$|无|\n|$5\\sim 7$|$100$|$100$|每个事情发生前，$a$ 对 $b$ 好感度都是 $0$（只有一件事情会影响 $a$ 对 $b$ 的好感度）|\n|$8\\sim 11$|$100$|$100$|对于每个事情，都有 $a=1$|\n|$12\\sim 15$|$100$|$100$|保证 $op=1$|\n|$16\\sim 20$|$100$|$100$|无|\n\n对于所有数据，保证 $2\\le n\\le 100$，$1\\le a,b\\le n$，$1\\le c\\le 10^5$，且任意时刻任何人对其他所有人的好感度都是自然数。","is_translate":false,"language":"English"}],"meta":{"iden":"LGB4030","tags":["2024","O2优化","数组","语言月赛"],"sample_group":[["2 3\n1 1 2 4\n1 2 1 6\n2 2 1 3\n","4\n6\n4\n"]],"created_at":"2026-03-03 11:09:25"}}