A5996. LJJ 爱数书
编程题
省选/NOI-
知识点
题目描述
LJJ 的家里有一本「数书」，也就是说里面全都是数字的书，LJJ 十分喜爱它。
数书里有一个序列 $A$，每次操作可以使一段连续的区间加 $1$ 或减 $1$ 并对 $K$ 取模（$K-1$ 加 $1$ 后变为 $0$，$0$ 减 $1$ 后变为 $K-1$），我们定义和谐函数 $F(A,K)$ 表示最少的操作次数，使得序列的所有元素都变为 $0$。
例如 $A=\{3,3,2,3\},K=4$ 时，通过把 $A$ 变成 $\{0,0,3,0\}$，再把 $A$ 变成 $\{0,0,0,0\}$ 就能达到要求，所以 $F(A,K)=2$。
现在，输入长度为 $n$ 的序列 $A$，设 $A_{l,r}$ 表示序列 $A$ 第 $l$ 个位置到第 $r$ 个位置的连续子序列。有 $m$ 次询问，每次询问输入 $l,r,K$，求 $F(A_{l,r},K)$ 的值。
数书里有一个序列 $A$，每次操作可以使一段连续的区间加 $1$ 或减 $1$ 并对 $K$ 取模（$K-1$ 加 $1$ 后变为 $0$，$0$ 减 $1$ 后变为 $K-1$），我们定义和谐函数 $F(A,K)$ 表示最少的操作次数，使得序列的所有元素都变为 $0$。
例如 $A=\{3,3,2,3\},K=4$ 时，通过把 $A$ 变成 $\{0,0,3,0\}$，再把 $A$ 变成 $\{0,0,0,0\}$ 就能达到要求，所以 $F(A,K)=2$。
现在，输入长度为 $n$ 的序列 $A$，设 $A_{l,r}$ 表示序列 $A$ 第 $l$ 个位置到第 $r$ 个位置的连续子序列。有 $m$ 次询问，每次询问输入 $l,r,K$，求 $F(A_{l,r},K)$ 的值。
输入格式
第一行两个整数 $n,m$，表示序列长度为 $n$，有 $m$ 次询问；
第二行有 $n$ 个整数，第 $i$ 个整数表示 $A_i$；
第三至第 $m+2$ 行，每行三个整数 $l,r,K$。
第二行有 $n$ 个整数，第 $i$ 个整数表示 $A_i$；
第三至第 $m+2$ 行，每行三个整数 $l,r,K$。
输出格式
共 $m$ 行，每行一个整数，表示每组询问的答案。
输入输出样例
输入 #1
7 2 8 8 8 0 8 8 8 1 7 9 3 5 17
输出 #1
2 16
输入 #2
4 1 5 3 8 2 1 4 9
输出 #2
8
输入 #3
10 10 7 7 6 5 5 2 8 5 0 3 1 8 11 3 10 11 4 7 12 9 10 12 3 5 10 2 7 10 7 9 10 2 7 11 1 4 11 4 7 10
输出 #3
12 15 9 3 5 8 5 9 6 7
说明/提示
对于 $10\%$ 的数据，$n\le 10,m=1,K\le 10$；
对于 $30\%$ 的数据，$n\le 1000,m=1,K\le 2^{30}$；
对于 $50\%$ 的数据，$n\le 2\times 10^5,m=1,K\le 2^{30}$；
另有 $10\%$ 的数据，$n\le 2\times 10^5,m\le 10^5,K=2$；
另有 $20\%$ 的数据，$n,m\le 3\times 10^4,K\le 2^{30}$；
对于全部数据，$1\le n\le 2\times 10^5,1\le m\le 10^5,K\le 2^{30},1\le l\le r\le n$，保证 $K\gt \max \{A_1,A_2,\cdots ,A_n\}$。
对于 $30\%$ 的数据，$n\le 1000,m=1,K\le 2^{30}$；
对于 $50\%$ 的数据，$n\le 2\times 10^5,m=1,K\le 2^{30}$；
另有 $10\%$ 的数据，$n\le 2\times 10^5,m\le 10^5,K=2$；
另有 $20\%$ 的数据，$n,m\le 3\times 10^4,K\le 2^{30}$；
对于全部数据，$1\le n\le 2\times 10^5,1\le m\le 10^5,K\le 2^{30},1\le l\le r\le n$，保证 $K\gt \max \{A_1,A_2,\cdots ,A_n\}$。