Блог пользователя adamantium

Автор adamantium, история, 8 лет назад, По-английски

I tried to solve this problem but failed. Would anyone please help me to solve this problem

Problem Statement:

Sameen has:

1.An array having N integers

2.Q friends

His friends are curious about the array. So, each of his friends asks Sameen a question about the array. Every question is described by 3 integers: i, j and k. In reply to a question, Sameen has to say the “k alternating sum” of the subarray starting at position i and ending at position j [1 based indexing]

“k alternating sum” of a subarray starting at position i and ending at position j can be calculated in the following way:

Add the first k numbers[starting from position i]

Subtract the second k numbers[starting from position i+k]

Add the third k numbers[starting from position i+2*k]

Subtract the fourth k numbers[starting from position i+3*k]

And so on till adding/subtracting the j-th number…

(j-i+1) will be divisible by k.

[See sample Input/output and explanation section for more details]

Can you help Sameen in answering the questions?

Input:

The first line of input contains two integers N and Q. The next line contains N integers, the numbers in the array. Then each of the following Q lines contains 3 integers i, j & k.

Output:

For each query output an integer in a separate line, the answer for that query. Queries should be answered in the order given in the input.

Constraints:

1 ≤ k ≤ 100000

1 ≤ N ≤ 100000

1 ≤ Q ≤ 100000

-1000000000 ≤ Value of a number in the array ≤ 1000000000

(j-i+1) will be divisible by k.

Sample Input:

6 6

4 1 -2 -3 4 5

2 5 2

1 6 1

1 6 3

1 6 6

3 3 1

3 4 1

Sample Output:

-2

3

-3

9

-2

1

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

Break the problem into two cases: when k > sqrt(n) and when k <= sqrt(n). Deal with them in different ways.

Case 1: For any k > sqrt(N) there will be less than sqrt(N) alternating segment. If you have an array, having cumulative sum, you can get the sum of a contiguous segment in O(1). So you can just loop over the alternating parts and get the sum in O(sqrt(N)) for a single query.

Case 2: Now when k <= sqrt(n), you need to do some preprocessing.

let arr[k][i] be the "k alternating sum" of a subarray which starts at position i and keeps alternating untill it reaches a position x such that if you add another segment of size k then it will go out of the array. [ This array can be computed in O(N) , and as you're doing it for every k < sqrt(n), the total complexity is O(N * sqrt(N))] With the help of this array, you can answer every query having k < sqrt(N) in O(1).

Hope that helps.