LJJ爱数书

题解请查看[https://www.cnblogs.com/Blog-of-Eden/p/9367521.html](https://www.cnblogs.com/Blog-of-Eden/p/9367521.html)

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（n<=200000）**的序列A，设A[L][R]表示序列A第L个位置到第R个位置的连续子序列。 有**m（m<=100000）**次询问，每次询问**输入L,R,K**，求**F(A[L][R],K)的值**。 **注：数据保证K>Max{A[1],A[2],....,A[n]}。**

第1行：两个整数n,m，表示序列长度为n，有m次询问。 第2行：n个整数，第i个整数表示A[i] 第3至m+2行：每行三个整数L,R,K（1<=L<=R<=n，K<=2^30）

共m行：每行一个整数，表示每组询问的答案F(A[L][R],K)

7 2
8 8 8 0 8 8 8
1 7 9
3 5 17

2
16

4 1
5 3 8 2
1 4 9

8

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

12
15
9
3
5
8
5
9
6
7

数据保证每组询问的K>Max{A[1],A[2],....,A[n]}。 10%：n<=10，m=1，K<=10 30%：n<=1000，m=1，K<=2^30 50%：n<=200000，m=1，K<=2^30 另有10%数据：n<=200000，m<=100000，K=2 另有20%数据：n<=30000，m<=30000，K<=2^30 100%：n<=200000，m<=100000，K<=2^30