{"problem":{"name":"「MXOI Round 1」涂色","description":{"content":"小 C 正在用彩铅给一张 $n$ 行 $m$ 列的方格纸涂色。初始时，所有方格都是空白的。 他一共要进行 $q$ 次涂色，每次涂色会选取一行或一列，给这一行或这一列的所有方格都添加 $1$ 层颜色。 小 C 喜欢浅色，所以他会在每次涂色结束后，把所有被涂上 $k$ 层颜色的方格的颜色都擦掉，让这些方格都变成空白的。 小 C 想知道，在最终共有多少方格被涂上了颜色。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9583"},"statements":[{"statement_type":"Markdown","content":"小 C 正在用彩铅给一张 $n$ 行 $m$ 列的方格纸涂色。初始时，所有方格都是空白的。\n\n他一共要进行 $q$ 次涂色，每次涂色会选取一行或一列，给这一行或这一列的所有方格都添加 $1$ 层颜色。\n\n小 C 喜欢浅色，所以他会在每次涂色结束后，把所有被涂上 $k$ 层颜色的方格的颜色都擦掉，让这些方格都变成空白的。\n\n小 C 想知道，在最终共有多少方格被涂上了颜色。\n\n## Input\n\n第一行四个整数 $n,m,q,k$。\n\n接下来 $q$ 行，每行两个整数 $op,x$。\n\n- 若 $op=1$，则表示给第 $x$ 行的所有方格都添加 $1$ 层颜色；  \n- 若 $op=2$，则表示给第 $x$ 列的所有方格都添加 $1$ 层颜色。\n\n## Output\n\n一个整数，表示在最终共有多少方格被涂上了颜色。\n\n[samples]\n\n## Note\n\n#### 【样例解释 #1】\n\n第 $1$ 行第 $1$ 列的方格没有被涂上颜色，第 $1$ 行第 $2$ 列的方格被涂上了 $1$ 层颜色，第 $1$ 行第 $3$ 列的方格没有被涂上颜色，第 $1$ 行第 $4$ 列的方格被涂上了 $1$ 层颜色；\n\n第 $2$ 行第 $1$ 列的方格被涂上了 $1$ 层颜色，第 $2$ 行第 $2$ 列的方格被涂上了 $2$ 层颜色，第 $2$ 行第 $3$ 列的方格被涂上了 $1$ 层颜色，第 $2$ 行第 $4$ 列的方格被涂上了 $2$ 层颜色；\n\n第 $3$ 行第 $1$ 列的方格被涂上了 $2$ 层颜色，第 $3$ 行第 $2$ 列的方格的颜色被擦掉了，第 $3$ 行第 $3$ 列的方格被涂上了 $2$ 层颜色，第 $3$ 行第 $4$ 列的方格的颜色也被擦掉了；\n\n最终，共有 $8$ 个方格被涂上了颜色。\n\n#### 【样例 #2】\n\n见附加文件中的 `paint/paint2.in` 与 `paint/paint2.ans`。\n\n该样例满足测试点 $1$ 的限制。\n\n#### 【样例 #3】\n\n见附加文件中的 `paint/paint3.in` 与 `paint/paint3.ans`。\n\n该样例满足测试点 $5$ 的限制。\n\n#### 【样例 #4】\n\n见附加文件中的 `paint/paint4.in` 与 `paint/paint4.ans`。\n\n该样例满足测试点 $20$ 的限制。\n\n#### 【数据范围】\n\n对于 $100\\%$ 的数据，$1 \\le n,m \\le 2\\times 10^5$，$1 \\le k \\le q \\le 5 \\times 10^5$，$op \\in \\{1,2\\}$，保证当 $op=1$ 时 $1 \\le x \\le n$，当 $op=2$ 时 $1 \\le x \\le m$。\n\n|测试点编号|$n,m \\le$|$q \\le$|特殊性质|\n|:---:|:---:|:---:|:---:|\n|$1\\sim4$|$3000$|$3000$|无|\n|$5\\sim9$|$3000$|$5\\times10^5$|无|\n|$10\\sim12$|$2\\times10^5$|$5\\times10^5$|A|\n|$13\\sim16$|$2\\times10^5$|$5\\times10^5$|B|\n|$17\\sim20$|$2\\times10^5$|$5\\times10^5$|无|\n\n特殊性质 A：保证 $op=1$。\n\n特殊性质 B：保证 $k=2$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9583","tags":["模拟","洛谷原创","O2优化","排序","差分","洛谷月赛"],"sample_group":[["3 4 5 3\n1 3\n2 4\n1 2\n1 3\n2 2","8"]],"created_at":"2026-03-03 11:09:25"}}