Limits
1.5s, 512 MB

Let's get into the problem directly without much description this time :D .

You are given an array **A** of **N** integers. The elements of the array are **A**1, **A**2, **A**3 ... **A**N . You are also given **Q** queries to perform on this array **A**. In each query, you will be given three integers **L, R, X** where **[L, R]** denotes a sub-segment of the array **A** starting at **A**L and ending at **A**R. You have to find the minimum number of operations needed to make all values of the sub-segment, **[L, R]** of the array **A** equal to **X** i.e. **A**L = **A**L+1 = **A**L+2 = ... = **A**R = **X**. There are two types of operations. You can apply any of the two operations any number of times.

Two types of operations are described below-**Operation 1:** you can choose any index i **(1 ≤** i **≤ N)** of the array **A** and then perform **A**i **=** **A**i **+ 1**.**Operation 2:** you can choose any index i **(1 ≤** i **≤ N)** of the array **A** and then perform **A**i **=** **A**i **- 1**.

**Note: Every query is independent.**

First line contains an integer **T(1 ≤ T ≤ 5)**, the number of test case.

Every test case starts with an integer **N(1 ≤ N ≤ 105)**, the number of elements of the array **A**.

Next line will contain the elements of the array **A**1, **A**2, ..., **A**N **(-109 ≤ A**i **≤ 109)**.

Next line will contain an integer **Q(1 ≤ Q ≤ 105)**, the number of queries.

Next Q lines will contain three integers **L, R(1 ≤ L ≤ R ≤ N)** and **X(-1012 ≤ X ≤ 1012)**.

**Subtasks****Subtask #1 (10 points)****1 ≤ N, Q ≤ 103**.**Subtask #2 (30 points)****1 ≤ N, Q ≤ 105**.

There are at most **10** distinct values in the array **A**.**Subtask #3 (60 points)**

Original Constraints.

For each case, print the case number in a single line.

Then for every query print the minimum number of operations needed to make all values of the sub-segment, **[L, R]** of the array **A** equal to **X**.

Input | Output |
---|---|

1 3 4 5 6 2 1 3 6 1 3 4 | Case 1: 3 3 |

In the **1st** query, you have to apply **"operation 1"** in the **1st** index **two times** and **2nd** index **one time**. So, the answer is **3**.

In the **2nd** query, you have to apply **"operation 2"** in the **2nd** index **one time** and **3rd** index **two times**. So, the answer is **3**.

Login to submit.

47%
Solution Ratio

prodip_bsmrstuEarliest,

EgorKulikovFastest, 0.3s

user.536969Lightest, 9.2 MB

MursaleenShortest, 1682B

Toph uses cookies. By continuing you agree to our Cookie Policy.