{"problem":{"name":"「KDOI-03」序列变换","description":{"content":"给定一个长度为 $n$ 的 $\\tt01$ 序列 $a$ 和 $q$ 次询问，询问参数 $k$。 每次询问给定 $L,R$，其中 $1\\leq L\\leq R\\leq n$，你可以进行如下操作： + 选择一个下标 $L<i\\le R$； + 将 $a_{i-1}$ 赋值为 $a_{i-1}\\oplus a_i$，$a_{i+1}$  赋值为 $a_{i+1}\\oplus a_i$。如果 $i=","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":4000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8864"},"statements":[{"statement_type":"Markdown","content":"给定一个长度为 $n$ 的 $\\tt01$ 序列 $a$ 和 $q$ 次询问，询问参数 $k$。\n\n每次询问给定 $L,R$，其中 $1\\leq L\\leq R\\leq n$，你可以进行如下操作：\n\n+ 选择一个下标 $L<i\\le R$；\n+ 将 $a_{i-1}$ 赋值为 $a_{i-1}\\oplus a_i$，$a_{i+1}$  赋值为 $a_{i+1}\\oplus a_i$。如果 $i=n$，则不对 $a_{i+1}$ 作出改变。其中 $\\oplus$ 表示按位异或运算。\n\n求使得 $[L,R]$ 区间内**至多**有 $k$ 个 $\\tt1$ 的最小操作次数。询问之间相互独立，也就是说，每次询问后重置为初始序列。\n\n## Input\n\n从标准输入读入数据。\n\n第一行包含三个正整数 $n,k,q$。\n\n第二行包含 $n$ 个非负整数 $a_1,a_2,\\cdots,a_n$。\n\n接下来 $q$ 行，每行包含两个正整数 $L,R$，表示一次询问。\n\n## Output\n\n输出到标准输出。\n\n输出共 $q$ 行，每行包含一个整数，表示答案。\n\n[samples]\n\n## Note\n\n**【样例 1 解释】**\n\n如图，用绿色代表 $\\tt0$，红色代表 $\\tt1$，初始序列如下：\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/hxw9knxu.png)\n\n对于第 $1$ 次询问，选择 $i=3$，则序列变为下图：\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/zvb2lfi8.png)\n\n对于第 $2$ 次询问，选择 $i=2$，则序列变为下图：\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/wubvxvaa.png)\n\n**【样例 2 解释】**\n\n对于第 $1$ 次询问，由于 $a_{12},a_{13},a_{14},a_{15}$ 中只有 $2$ 个 $\\tt1$，所以不需要进行任何操作。\n\n对于第 $6$ 次询问，可以依次选择 $i=\\{7,8,9,10,11,12\\}$。\n\n**【样例 3】**\n\n见选手文件中的 `control/control3.in` 与 `control/control3.ans`。\n\n此样例满足测试点 $7\\sim10$ 的限制。\n\n**【样例 4】**\n\n见选手文件中的 `control/control4.in` 与 `control/control4.ans`。\n\n此样例满足测试点 $15\\sim17$ 的限制。\n\n**【样例 5】**\n\n见选手文件中的 `control/control5.in` 与 `control/control5.ans`。\n\n此样例满足测试点 $18\\sim21$ 的限制。\n\n***\n\n**【数据范围】**\n\n对于 $100\\%$ 的数据， $2\\le n\\le 3~000$，$1\\le k\\le \n\\min(n,1~000)$，$1\\le q\\le 5\\times10^5$，$0\\le a_i\\le 1$。\n\n|测试点编号|$n\\le$|$k\\le$|$q\\le$|特殊性质|\n|:--:|:--:|:--:|:--:|:--:|\n|$1\\sim3$|$80$|$50$|$2~000$|无|\n|$4\\sim6$|$400$|$300$|$1$|$k$ 是偶数|\n|$7\\sim10$|$400$|$2$|$10~000$|无|\n|$11\\sim14$|$400$|$300$|$10~000$|无|\n|$15\\sim17$|$3~000$|$10$|$5\\times10^5$|无|\n|$18\\sim21$|$3~000$|$1~000$|$5\\times10^5$|$k$ 是偶数|\n|$22\\sim25$|$3~000$|$1~000$|$5\\times10^5$|无|","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8864","tags":["动态规划 DP","2022","洛谷原创","O2优化","动态规划优化","矩阵加速","四边形不等式"],"sample_group":[["5 1 2\n1 1 1 0 1\n2 3\n1 3","1\n1"],["20 3 22\n0 0 1 1 1 1 1 0 0 0 0 0 1 0 1 0 0 1 0 1 \n12 15\n1 6\n5 10\n2 5\n9 18\n6 17\n2 13\n4 16\n2 8\n9 19\n10 15\n7 15\n1 3\n14 18\n6 17\n12 14\n7 16\n14 18\n11 12\n3 5\n3 6\n3 15\n","0\n1\n0\n0\n0\n6\n3\n5\n1\n0\n0\n0\n0\n0\n6\n0\n0\n0\n0\n0\n1\n3\n"]],"created_at":"2026-03-03 11:09:25"}}