{"problem":{"name":"[常州市赛 2024] 棋盘","description":{"content":"小 Y 有一个 $n\\times n$ 棋盘，开始时这个棋盘每个格子的颜色是白黑相间的，即第一行的第 $1,3,5\\cdots$ 个格子是白色，第 $2,4,6\\cdots$ 个格子是黑色，第二行第 $2,4,6\\cdots$ 个格子是白色，第 $1,3,5\\cdots$ 个格子是黑色，如下图所示。 $$ \\def\\b{\\color{ff}\\rule{10px}{10px}\\kern{1px}","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGB4229"},"statements":[{"statement_type":"Markdown","content":"小 Y 有一个 $n\\times n$ 棋盘，开始时这个棋盘每个格子的颜色是白黑相间的，即第一行的第 $1,3,5\\cdots$ 个格子是白色，第 $2,4,6\\cdots$ 个格子是黑色，第二行第 $2,4,6\\cdots$ 个格子是白色，第 $1,3,5\\cdots$ 个格子是黑色，如下图所示。\n\n$$\n\\def\\b{\\color{ff}\\rule{10px}{10px}\\kern{1px}}\n\\def\\w{\\color{white}\\rule{10px}{10px}\\kern{1px}}\n\\def\\bg{\\color{black}\\rule{33.5px}{33.5px}}\n\\def\\eps{\\\\[-39.5px]}\n\\def\\ep{\\\\[-5.5px]}\n\\begin{aligned}\n\\bg\\eps\n\\w\\b\\w\\ep\n\\b\\w\\b\\ep\n\\w\\b\\w\n\\end{aligned}\n$$\n\n小 Y 会进行 $q$ 次操作，每次操作会将某一行或者某一列的所有格子的颜色反转，即白色格子变成黑色格子，黑色格子变成白色格子。\n\n小 Y 想知道，在每次操作之后，一共有多少个同颜色（全黑或全白）的连通区域。这里联通指的是**四连通**，即两个格子之间有边相邻才算联通。\n\n## Input\n\n第 $1$ 行 $2$ 个正整数 $n,q$，表示棋盘的大小和操作的次数。\n\n第 $2$ 到 $q+1$ 行每行 $2$ 个正整数 $\\text{opt}_i,a_i$，若 $\\text{opt}_i=1$ 则表示反转的是行，$\\text{opt}_i=2$ 则表示反转的是列，$a_i$ 表示反转的是第几行（列）。\n\n## Output\n\n输出 $q$ 行每行一个整数，表示在经过该次操作后，一共有多少个同颜色的联通区域。\n\n[samples]\n\n## Background\n\n搬运自 <http://czoj.com.cn/p/955>。数据为民间数据。\n\n## Note\n\n### 样例 $\\textbf 1$ 解释\n$$\n\\def\\b{\\color{ff}\\rule{10px}{10px}\\kern{1px}}\n\\def\\w{\\color{white}\\rule{10px}{10px}\\kern{1px}}\n\\def\\bg{\\color{black}\\rule{33.5px}{33.5px}}\n\\def\\eps{\\\\[-39.5px]}\n\\def\\ep{\\\\[-5.5px]}\n\\begin{aligned}\n\\bg\\eps\n\\w\\b\\w\\ep\n\\b\\w\\b\\ep\n\\w\\b\\w\n\\end{aligned}\n\\to\n\\begin{aligned}\n\\bg\\eps\n\\w\\b\\w\\ep\n\\w\\b\\w\\ep\n\\w\\b\\w\n\\end{aligned}\n\\to\n\\begin{aligned}\n\\bg\\eps\n\\w\\b\\b\\ep\n\\w\\b\\b\\ep\n\\w\\b\\b\n\\end{aligned}\n\\to\n\\begin{aligned}\n\\bg\\eps\n\\w\\b\\b\\ep\n\\b\\w\\w\\ep\n\\w\\b\\b\n\\end{aligned}\n$$\n\n### 数据范围\n对于所有数据，$1≤q, n≤10^5, 1≤\\text{opt}_i≤2, 1≤a_i≤n$。\n\n|测试点编号|$n$|$q$|特殊性质|\n|:-:|:-:|:-:|:-:|\n|$1\\sim4$|$\\le 4$|$\\le 10$|无|\n|$5\\sim6$|$\\le10^5$|$=1$|无|\n|$7\\sim9$|$\\le10^5$|$\\le10^5$|$\\alpha$|\n|$10$|$\\le10^5$|$\\le10^5$|无|\n\n- 特殊性质 $\\alpha$：保证同一个测试点所有的 $\\text{opt}_i$ 均相等。","is_translate":false,"language":"English"}],"meta":{"iden":"LGB4229","tags":["2024","江苏","Ad-hoc","科创活动","小学活动"],"sample_group":[["3 3\n1 2\n2 3\n1 2","3\n2\n6"],["100000 1\n1 1","9999900000"],["15000 5\n1 90\n1 1231\n1 91\n1 1233\n1 1232","224970000\n224940000\n224940000\n224910000\n224940000"]],"created_at":"2026-03-03 11:09:25"}}