题目背景

题解请查看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