{"problem":{"name":"ZHY 的集合","description":{"content":"对于两个集合大小为 $x$ 的集合 $A,B$，满足 $A\\cap B=\\varnothing$（空集），ZHY 定义 $f(A,B)$ 如下： - 设 $C=A\\cup B$。将 $C$ 中的元素从小到大排序。 - $f(A,B)=\\displaystyle \\sum_{i=1}^x C_i$。 现在，ZHY 有 $n$ 个大小为 $m$ 的集合 $S_1,S_2,\\cdots,S_n$，","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9491"},"statements":[{"statement_type":"Markdown","content":"对于两个集合大小为 $x$ 的集合 $A,B$，满足 $A\\cap B=\\varnothing$（空集），ZHY 定义 $f(A,B)$ 如下：\n\n- 设 $C=A\\cup B$。将 $C$ 中的元素从小到大排序。\n\n- $f(A,B)=\\displaystyle \\sum_{i=1}^x C_i$。\n\n现在，ZHY 有 $n$ 个大小为 $m$ 的集合 $S_1,S_2,\\cdots,S_n$，他想知道 $\\displaystyle \\sum_{i=1}^n\\sum_{j=i + 1}^n f(S_i,S_j)$ 是多少。\n\n然而，ZHY 并不满足于此。于是他又进行了 $q$ 次修改操作，每次操作会重新给定一个集合。请你在每次修改后都输出一次答案，即 $\\displaystyle \\sum_{i=1}^n\\sum_{j=i + 1}^n f(S_i,S_j)$。保证任意时刻任意一个集合中元素两两不同，保证任意时刻任意两个集合的交为空。\n\n## Input\n\n第一行三个整数 $n,m,q$。\n\n第 $2$ 行到第 $n+1$ 行，每行 $m$ 个整数，描述集合 $S_1,S_2,\\cdots,S_n$。第 $i+1$ 行的 $m$ 个数为集合 $S_i$ 中的 $m$ 个整数。\n\n随后 $q$ 行，每行第一个整数为 $x$，表示将要修改的集合的编号。随后 $m$ 个数表示新的 $S_x$ 中的 $m$ 个整数。\n\n## Output\n\n第一行一个整数表示初始时的答案。\n\n随后 $q$ 行，每行一个整数表示每次修改后的答案。\n\n[samples]\n\n## Background\n\n## 赛后时限改为 1s。\n\nZHY 又一次在赛时看错题了。\n[](T341514)\n\n## Note\n\n**本题采用捆绑测试。**\n\n| $\\mathrm{Subtask} \\kern{2pt} \\mathrm{id}$ | $n$ | $m$ | $q$ | 分值 |\n| :-----: | :-----: | :-----: | :-----: | :-----: |\n| $0$ | $\\le 100$ | $\\le 10$ | $\\le 10$ | $7$ |\n| $1$ | $\\le 100$ | $\\le 100$ | $\\le 100$ | $11$ |\n| $2$ | $\\le 10^3$ | $\\le 100$ | $\\le 10^3$ | $7$ |\n| $3$ | $\\le 10^4$ | $\\le 100$ | $=0$ | $15$ |\n| $4$ | $\\le 10^4$ | $\\le 100$ | $\\le 10^3$ | $27$ |\n| $5$ | $\\le 10^4$ | $\\le 100$ | $\\le 10^4$ | $33$ |\n\n对于所有数据，$0 \\le n, q \\le 10^4$，$1 \\le m \\le 100$，$1 \\le S_{i,j} \\le 10^9$。保证任意时刻对于 $\\forall i\\in [1,n],\\kern{2pt}j \\in [1,m],\\kern{2pt}i' \\in[1,n],\\kern{2pt}j'\\in [1,m]$，若 $i \\ne i'$ 或 $j \\ne j'$，则 $S_{i,j} \\ne S_{i',j'}。$","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9491","tags":["树状数组","O2优化"],"sample_group":[["3 2 2\n1 3\n2 6\n4 8\n1 3 5\n2 7 9","13\n18\n26"]],"created_at":"2026-03-03 11:09:25"}}