{"problem":{"name":"「SvR-2」令人为难的区间操作问题","description":{"content":"小 F 正在研究[斐波那契数列](https://zh.wikipedia.org/wiki/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0)，他惊讶地发现，可以把这种数列 $F$ 的定义式略作修改，得到 $\\digamma$ 数列： $$\\digamma(x)=\\{1,1,-1,-1,1,1,-1,-1,1,\\ldots\\}$$ 注意到 $\\dig","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":131072},"difficulty":{"LuoguStyle":"P2"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9086"},"statements":[{"statement_type":"Markdown","content":"小 F 正在研究[斐波那契数列](https://zh.wikipedia.org/wiki/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0)，他惊讶地发现，可以把这种数列 $F$ 的定义式略作修改，得到 $\\digamma$ 数列：\n\n$$\\digamma(x)=\\{1,1,-1,-1,1,1,-1,-1,1,\\ldots\\}$$\n\n注意到 $\\digamma$ 数列具有周期性，最小正周期 $T=4$。\n\n请注意这里 $\\digamma$ 数列与数学上用其表示的[双伽玛函数](https://zh.wikipedia.org/wiki/%E5%8F%8C%E4%BC%BD%E7%8E%9B%E5%87%BD%E6%95%B0)的区别。\n\n小 F 找到一个长度为 $n$ 的数列 $a$，他每次对其进行如下操作：\n\n- 选定两个整数 $l,r$，满足 $1\\le l\\le r\\le n$。\n- 对于每个满足 $l\\le i\\le r$ 的 $i$，将 $a_i$ 加上 $\\digamma(i-l+1)$。\n- 记录下本次操作（即第 $j$ 次操作）的选定区间的长度 $len_j=r-l+1$。\n\n他一共进行了 $m$ 次操作，操作后得到数列记作 $b$，同时记 $sum=\\sum_{i=1}^mlen_i$。\n\n不幸的是，小 F 把 $sum$ 和数列 $len$ 都弄丢了，他只记得 $n$ 和数列 $a,b$。\n\n现在，他想请你根据这些信息，求出 $sum$ 的**奇偶**，**即 $\\textbf{\\textit{sum}}$ 对 $\\textbf2$ 取模后的值**。\n\n## Input\n\n**本题有多组数据。**\n\n第一行一个整数 $T$，表示数据组数。\n\n接下来 $3\\cdot T$ 行，描述每组数据。对于每组数据：\n\n- 第一行一个整数 $n$。\n- 第二行 $n$ 个整数，描述数列 $a$。\n- 第三行 $n$ 个整数，描述数列 $b$。\n\n**数据保证数列 $a$ 一定可以经过若干操作变为数列 $b$。**\n\n## Output\n\n对于每组数据，输出仅一行一个数，即 $sum$ 对 $2$ 取模后的值。\n\n[samples]\n\n## Background\n\n**Problem Number:** $\\textit{45}$\n\n众所周知，区间操作问题应该求出区间和、最大值等值。但今天小 F 有个不情之请。\n\n## Note\n\n#### 样例 1 说明\n\n注意到可能进行的是如下操作：\n\n- 第 $1$ 次操作选定 $l=2,r=3$，则数列变成 $[1,{\\underline{\\color{red}\\textbf{3}}},{\\underline{\\color{red}\\textbf{4}}},4]$。此时 $len_1=2$。\n- 第 $2$ 次操作选定 $l=1,r=3$，则数列变成 $[{\\underline{\\color{red}\\textbf{2}}},{\\underline{\\color{red}\\textbf{4}}},{\\underline{\\color{red}\\textbf{3}}},4]$。此时 $len_2=3$。\n\n则 $sum=len_1+len_2=5$，是奇数。故 $sum\\bmod 2=1$。\n\n#### 数据规模与约定\n**本题采用捆绑测试**\n$$\n\\newcommand{\\arraystretch}{1.5}\n\\begin{array}{c|c|c|c}\\hline\\hline\n\\textbf{Subtask} & \\bm{\\sum n\\le} & \\textbf{特殊性质} & \\textbf{分值} \\\\\\hline\n\\textsf{1} & \\le 10 & a_i,b_i\\le 10^9 & 10 \\\\\\hline\n\\textsf{2} & \\le 10^3 & a_i,b_i\\le 10^9 & 20 \\\\\\hline\n\\textsf{3} & \\text{无特殊限制} & a_i,b_i\\le 10^9 & 20 \\\\\\hline\n\\textsf{4} & \\text{无特殊限制} & a_i\\le b_i & 20 \\\\\\hline\n\\textsf{5} & \\text{无特殊限制} & - & 30 \\\\\\hline\\hline\n\\end{array}\n$$\n\n对于 $100\\%$ 的数据，有 $1\\le T\\le 10^3$，$1\\le n\\le 10^5$，$1\\le a_i,b_i\\le 10^{18}$。\n\n单个测试点内保证 $\\sum n\\le 2\\times 10^5$。\n\n#### 说明\n\n$\\digamma$ 数列拥有如下的递推式：\n\n$$\n\\digamma(x)=\n\\begin{cases}\n1,&x\\le 2\\\\\n-1,&x=3\\\\\n\\digamma(x-1)-\\digamma(x-2)+\\digamma(x-3),&x>3.\n\\end{cases}\n$$","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9086","tags":["模拟","洛谷原创","O2优化","洛谷月赛"],"sample_group":[["1\n4\n1 2 3 4\n2 4 3 4","1"]],"created_at":"2026-03-03 11:09:25"}}