{"problem":{"name":"「yyOI R1」youyou 的序列","description":{"content":"给定一个长度为 $n$ 的序列 $a_{1\\dots n}$，以及 $q$ 次操作。 定义一次操作为：交换 $a_k$ 与 $a_{k+1}$ 的值，并**立即**询问所有以 $a_i \\;( i\\in [1,n])$ 为峰的[子序列](https://oi-wiki.org/string/basic/#%E5%AD%90%E5%BA%8F%E5%88%97)数量之和，对 $4294967296","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":131072},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9639"},"statements":[{"statement_type":"Markdown","content":"给定一个长度为 $n$ 的序列 $a_{1\\dots n}$，以及 $q$ 次操作。\n\n定义一次操作为：交换 $a_k$ 与 $a_{k+1}$ 的值，并**立即**询问所有以 $a_i \\;( i\\in [1,n])$ 为峰的[子序列](https://oi-wiki.org/string/basic/#%E5%AD%90%E5%BA%8F%E5%88%97)数量之和，对 $4294967296$ 取模。**这里的交换是暂时的，也就是说，它仅在下一次操作前有效。**\n\n在此我们认为，一个长度至少为 $1$ 的序列 $[a_1,a_2 ,\\cdots,a_{s-1},a_s,a_{s+1},\\cdots,a_{n-1},a_n ]$，满足 $a_1<a_2<\\cdots<a_{s-1}<a_s>a_{s+1}>\\cdots >a_{n-1}>a_n$，则称此序列为以 $a_s$ 为峰的序列。\n\n你的任务是回答出所有操作的答案。\n\n## Input\n\n第一行输入两个整数 $n,q$。\n\n第二行输入 $n$ 个正整数，表示一开始的序列 $a_{1\\dots n}$。\n\n第三行，输入一个整数 $k$，表示进行第一次操作（定义见上），保证 $1\\le k <n$。\n\n---\n\n第 $2$ 到第 $q$ 次操作的 $k$ 值由如下方法得到：\n\n```cpp\nint Answer(unsigned int ans)\n{\n    unsigned int BASE=998244353ll*ans+ans*ans+ans/9991+ans%2159;\n    BASE^=9810;\n    BASE^=51971;\n    BASE=BASE>>7;\n    BASE=BASE<<11;\n    BASE^=751669;\n    BASE^=23465695622566ll;\n    return BASE%(n-1)+1;\n}\n```\n当你每完成一次询问后，将你这次询问的答案 $ans$ 作为参数，**恰好**调用一次 `Answer(ans)` 。\n\n得到的返回值即为下一次操作的 $k$。\n\n**注意：本输入方式仅用于减少输入量，标准算法不依赖于此输入方式。**\n\n## Output\n\n你需要输出所有操作的答案，每个答案输出一行。\n\n[samples]\n\n## Note\n\n### 样例解释 #1\n\n第一次操作的 $k$ 为 $1$。\n\n此时序列为 $[5,1,7,3]$。\n\n峰为 $a_1$：$[5]$，$[5,1]$，$[5,3]$。\n\n峰为 $a_2$：$[1]$。\n\n峰为 $a_3$：$[7]$，$[5,7]$，$[1,7]$，$[7,3]$，$[5,7,3]$，$[1,7,3]$。\n\n峰为 $a_4$：$[3]$，$[1,3]$。\n\n共计 $12$ 个不同的子序列，答案输出 $12$。\n\n第二次和第三次操作的 $k$ 均为 $3$ ，此时有 $13$ 个不同的序列满足条件。\n\n### 样例解释 #2\n\n第一次操作的 $k$ 为 $1$。\n\n此时序列为 $[7,7,7,7,6]$。\n\n峰为 $a_1$：$[7]$，$[7,6]$。\n\n峰为 $a_2$：$[7]$，$[7,6]$。\n\n峰为 $a_3$：$[7]$，$[7,6]$。\n\n峰为 $a_4$：$[7]$，$[7,6]$。\n\n峰为 $a_5$：$[6]$。\n\n共计 $9$ 个不同的子序列，答案输出 $9$。\n\n后四次操作同理。\n\n---\n\n### 数据范围\n\n**本题采用捆绑测试。**\n\n| 子任务编号 | $n$ | $q$ | 分数 |\n| :-----------: | :-----------: | :-----------: | :-----------: |\n| $1$ | $\\le 500$ | $\\le 100 $ |$10$ |\n| $2$ | $\\le2\\times10^3$|$ \\le 5\\times10^3$ | $20$ |\n| $3$ | $\\le3\\times10^4$ |$\\le 10^4$ | $30$ |\n| $4$ | $\\le10^6$|$ \\le10^6$ | $40$ |\n\n对于 $100\\%$ 的数据，$2\\le n\\le10^6$，$1\\le q\\le10^6$，$1\\le a_i\\le10^4$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9639","tags":["动态规划 DP","树状数组","O2优化"],"sample_group":[["4 3\n1 5 7 3\n1\n","12\n13\n13\n"],["5 5\n7 7 7 7 6\n1","9\n9\n9\n9\n9"]],"created_at":"2026-03-03 11:09:25"}}