{"problem":{"name":"一首诗","description":{"content":"文学大师 ZHY 创作了一首诗。 这首诗由 $n$ 个单词组成，为了方便表述，ZHY 将这首诗记录为一个长度为 $n$ 的整数序列 $a_1,a_2,\\dots,a_n$。创作完后，ZHY 立刻将自己的作品分享给了 YHZ。YHZ 在感受到了诗歌之美后，希望借此提高一下自己的文学素养，于是准备对这首诗中的诗句进行摘抄。 YHZ 认为一个“诗句”，应该是 $a_1,a_2,\\dots,a_n$ ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10255"},"statements":[{"statement_type":"Markdown","content":"文学大师 ZHY 创作了一首诗。\n\n这首诗由 $n$ 个单词组成，为了方便表述，ZHY 将这首诗记录为一个长度为 $n$ 的整数序列 $a_1,a_2,\\dots,a_n$。创作完后，ZHY 立刻将自己的作品分享给了 YHZ。YHZ 在感受到了诗歌之美后，希望借此提高一下自己的文学素养，于是准备对这首诗中的诗句进行摘抄。\n\nYHZ 认为一个“诗句”，应该是 $a_1,a_2,\\dots,a_n$ 的一个**连续**子序列，诗句的长度即为子序列的长度。当然，他不会摘抄所有的诗句，而是只选择“优美的诗句”进行摘抄。由于不懂文法，YHZ 简单地认为一个诗句是“优美的”，当且仅当这个诗句中不存在两个**相邻**的重复单词。形式化的说，一个连续子序列 $a_l,a_{l+1},\\dots,a_r$（$l\\leq r$）组成的诗句是“优美的”，当且仅当对于所有的 $l\\leq i<r$，有 $a_i\\neq a_{i+1}$。\n\nYHZ 发现文学大师 ZHY 写的诗里优美的诗句太多了，所以他需要进行归类。不过还是由于他不懂文法，他希望直接按照句子的长度归类。记 $b_i$ 为长度为 $i$ 的优美的诗句的个数，YHZ 希望知道 $b_1,b_2,\\dots,b_n$。但即使是所有的 $b$ 数量也太多了，所以他只需要知道 $b_1\\oplus b_2\\oplus\\dots\\oplus b_n$。\n\n还没等 YHZ 摘抄结束，文学大师 ZHY 告诉 YHZ 他要进行 $Q$ 次润色。具体地，每次润色，ZHY 会选择一个诗句 $[l_i,r_i]$ 和一个整数 $x_i$，并对所有的 $l_i\\leq j\\leq r_i$，将单词 $a_j$ 修改为 $a_j+x_i$。好学的 YHZ 希望对每次润色后的诗歌进行摘抄，即对于每次修改后的 $a_1,a_2\\dots,a_n$，知道 $b_1\\oplus b_2\\oplus\\dots\\oplus b_n$。\n\n不过文学大师 ZHY 太卷了，他进行的润色次数太多了，YHZ 还是承受不了这么大的工作量，所以他希望你帮帮他。\n\n**形式化题面：**\n\n给定一个序列 $a_{1\\sim n}$，定义 $b_i$ 表示 $a$ 中有多少个长度为 $i$ 的区间使得任意两个相邻的数都不同。有 $q$ 次操作，每次操作给定 $l,r,x$，表示将 $a_{l\\sim r}$ 都加上 $x$。请在第一次操作之前和每次操作之后求出 $b_1\\oplus b_2\\oplus \\cdots \\oplus b_n$。其中 $\\oplus$ 表示按位异或。\n\n## Input\n\n第一行两个正整数 $n,q$。\n\n第二行 $n$ 个整数 $a_{1},a_{2},\\cdots,a_{n}$。\n\n接下来 $q$ 行，每行三个整数 $l_{i},r_{i},x_{i}$，表示一次操作。\n\n## Output\n\n输出 $q+1$ 行，表示第一次操作前和每次操作后的答案。\n\n[samples]\n\n## Background\n\n题目描述最后有形式化题意。\n\n## Note\n\n样例解释：\n\n第一次修改之前序列为 $[1,2,3,4]$，得到 $b_1=4,b_2=3,b_3=2,b_4=1$，故答案为 $4\\oplus 3 \\oplus 2\\oplus 1=4$。\n\n第一次修改之后序列为 $[2,3,3,4]$，得到 $b_1=4,b_2=2,b_3=0,b_4=0$，故答案为 $4\\oplus 2 \\oplus 0\\oplus 0=6$。\n\n第二次修改之后序列为 $[2,4,4,4]$，得到 $b_1=4,b_2=1,b_3=0,b_4=0$，故答案为 $4\\oplus 1 \\oplus 0\\oplus 0=5$。\n\n----\n\n| 子任务编号 | $n$ | $q$ | 特殊性质 | 分值 |\n| :-----------: | :-----------: | :-----------: | :-----------: | :-----------: |\n| $0$ | $\\le 300$ | $\\le 300$ | 无 | $15$ |\n| $1$ | $\\le 5000$ | $\\le 5000$ | 无 | $15$ |\n| $2$ | $\\le 2\\times 10^5$ | $\\le 2\\times 10^5$ | 保证 $a_i,x$ 在值域内均匀随机 | $10$ |\n| $3$ | $\\le 5\\times 10^4$ | $\\le 5\\times 10^4$ | 无 | $30$ |\n| $4$ | $\\le 2\\times 10^5$ | $\\le 2\\times 10^5$ | $l=1,r=n$ | $5$ |\n| $5$ | $\\le 2\\times 10^5$ | $\\le 2\\times 10^5$ | 无 | $25$ |\n\n对于所有数据，$1 \\le n,q \\le 2\\times 10^5$，$1\\le l \\le r \\le n$，$0\\le |x|,|a_i|\\le 10^9$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10255","tags":["洛谷原创","O2优化","洛谷月赛","根号分治"],"sample_group":[["4 2\n1 2 3 4\n1 2 1\n2 3 1","4\n6\n5"]],"created_at":"2026-03-03 11:09:25"}}