ZHY 的集合

Luogu

IDLGP9491

Time1000ms

Memory256MB

DifficultyP5

树状数组O2优化

对于两个集合大小为 $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$，他想知道 $\displaystyle \sum_{i=1}^n\sum_{j=i + 1}^n f(S_i,S_j)$ 是多少。然而，ZHY 并不满足于此。于是他又进行了 $q$ 次修改操作，每次操作会重新给定一个集合。请你在每次修改后都输出一次答案，即 $\displaystyle \sum_{i=1}^n\sum_{j=i + 1}^n f(S_i,S_j)$。保证任意时刻任意一个集合中元素两两不同，保证任意时刻任意两个集合的交为空。 ## Input 第一行三个整数 $n,m,q$。第 $2$ 行到第 $n+1$ 行，每行 $m$ 个整数，描述集合 $S_1,S_2,\cdots,S_n$。第 $i+1$ 行的 $m$ 个数为集合 $S_i$ 中的 $m$ 个整数。随后 $q$ 行，每行第一个整数为 $x$，表示将要修改的集合的编号。随后 $m$ 个数表示新的 $S_x$ 中的 $m$ 个整数。 ## Output 第一行一个整数表示初始时的答案。随后 $q$ 行，每行一个整数表示每次修改后的答案。 [samples] ## Background ## 赛后时限改为 1s。 ZHY 又一次在赛时看错题了。 [](T341514) ## Note **本题采用捆绑测试。** | $\mathrm{Subtask} \kern{2pt} \mathrm{id}$ | $n$ | $m$ | $q$ | 分值 | | :-----: | :-----: | :-----: | :-----: | :-----: | | $0$ | $\le 100$ | $\le 10$ | $\le 10$ | $7$ | | $1$ | $\le 100$ | $\le 100$ | $\le 100$ | $11$ | | $2$ | $\le 10^3$ | $\le 100$ | $\le 10^3$ | $7$ | | $3$ | $\le 10^4$ | $\le 100$ | $=0$ | $15$ | | $4$ | $\le 10^4$ | $\le 100$ | $\le 10^3$ | $27$ | | $5$ | $\le 10^4$ | $\le 100$ | $\le 10^4$ | $33$ | 对于所有数据，$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'}。$

Samples

Input #1

Output #1

13
18
26

API Response (JSON)

{
  "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$，...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments