Entering edit mode

You have an array of infinite length with the value of all elements as zero. You are also given the following:

- Two integers N and K
- In the next N lines, you are given three integers L, R, and X. This means that you have to add X to every element in the array from the index L to R (inclusive).

Your task is to find a subsequence from this array that meets the following conditions:

- The subsequence should be of maximum length.
- It should also be the smallest lexicographically.
- The subsequence should form an increasing sequence of the form [Z, Z + K, Z + 2 * K, ..., Z + (L - 1) * K] for a value Z and length L.

- Remember that the sequence A = [A1, A2, ..., AL] is lexicographically smaller than the sequence [B = [B1, B2, ..., BL] if there exists an index i such that Aj = Bj for all j < i and Ai < Bi.

Print the first integer that is the length of the subsequence and then the elements of the subsequence in the same line.

- 1 <= N, K <= 2 * 10^5
- 1 <= L <= R <= 10^9
- 1 <= X <= 10^9

4 2

1 3 1

2 4 2

5 6 3

5 5 1

`2 1 3`

- A tree with
`N`

nodes - An array
`A`

denoting the value of each node - A non-negative integer
`K`

- Pick a node
`r`

and make it the root of the tree. - In the new tree, pick a node
`x`

and for each of the nodes in the subtree of`x`

, update`A[subtree] = A[subtree] ⊕ K`

.

Determine the maximum sum of values of all the nodes in the tree that can be obtained.

- 1-Based indexing.
`⊕`

denotes the Bitwise-XOR operator.- A subtree of a node contains all the nodes that are descendants of that node and the node itself.

**Assumptions:**

`N = 3`

`edges = {(1, 2), (1, 3)}`

`A = [1, 1, 3]`

`K = 3`

**Approach:**

- You perform the following operation to get the maximum sum:
- Pick
`r = 3`

as the root of the tree. - Update the value in the subtree of
`x = 1`

. - The new array becomes
`A = [2, 2, 3]`

.

- Pick

The sum obtained is `2 + 2 + 3 = 7`

which is maximum. Hence, the answer is `7`

.

Note: This is the input format that you must use to provide custom input (available above the Compile and Test button).

- The first line contains
`T`

denoting the number of test cases.`T`

also specifies the number of times you have to run the`maximumSum`

function on a different set of inputs. - For each test case:
- The first line contains an integer
`N`

denoting the number of nodes. - Each of the following
`(N - 1)`

lines contains two space-separated integers denoting an edge between the given nodes. - The next line contains
`N`

space-separated integers denoting the value of nodes. - The next line contains a single integer
`K`

.

- The first line contains an integer

You are given an array *A* of *N* integer elements. You are also given *Q* queries, where each query is one of the following types:

*1 i val*: Update value of element at*i-th*index to val i.e.*A[i]=val*.*2 L R*: Find the value of function ∑i=*L,R*∑j=*i,R*[*F(i,j)]*, where*F(i,j)*represents the sum of elements of array*A*in index range Lto*R*.

Determine the value of function for queries of Type 2.

**Note**: Assume 1-based indexing.

- N = 5
- Q = 2
- A = [2,1,4,3,1]
- query = [(1, 2, 2), (2, 1, 3)]

- First query is of Type 1. Update
*A[2]=2*. Now, array*A*becomes [2, 2, 4, 3, 1] .

- Second query of Type 2 with
*L*= 1,*R*= 3- Value of function is equal to
*F(1,1)+F(1,2)+F(1,3)+F(2,2)+F(2,3)+F(3,3)*= 2+4+8+2+6+4 = 26

- Value of function is equal to

Thus, the answer is 26.

- The first line contains a single integer
*T*, which denotes the number of test cases. - For each test case:
- The first line contains an integer
*N*. - The second line contains an integer
*Q*. - The third line contains
*N*space-separated integers denoting the array*A*. - The next
*Q*lines contain 3 space-separated integers denoting the queries.

- The first line contains an integer

For each test case, print the value of the function for queries of type 2 in space-separated format on a new line.

- 1 ≤
*T*≤ 10 - 1≤
*N*,*Q*≤ 10^{5} - 1 ≤
*A[i]*,*val*≤ 10^{3} - 1 ≤
*i*≤ N - 1 ≤
*L*≤*R*≤ N

You are given *N* integers representing the locations of homes on a straight street (x-axis). The i_{th}home is located at *A _{i}* . You need to determine the optimal integer location

Determine the location of *X* which minimizes the value of function given in the question.

- N = 4
- A = [1,7,11,9,3]

- For all the values of
*X*only*X=6*gives the value of*69*which is minimum among all the integer values of*X*.

Thus, the answer is *6*.

- The first line contains a single integer
*T*, which denotes the number of test cases. - For each test case:
- The first line contains an integer
*N*. - The second line contains
*N*space-separated integers denoting the array*A*.

- The first line contains an integer

For each test case, print the value of*X*which minimizes the value of the function given in the question.

- 1 ≤
*T*≤ 10 - 1≤
*N*≤ 10^{5} - 1 ≤
*A[i]*≤ 10^{9}

You are given *N* integers representing the locations of homes on a straight street (x-axis). The i_{th} home is located at *A*_{i}. You need to determine the optimal integer location *X* to build a dark store such that the sum of the absolute distances from the dark store to each home is minimized. Specifically, you want to minimize the value of:

∑i=*1,N* |*X − A _{i}* | .

Determine the location of *X* which minimizes the value of function given in the question.

- N = 4
- A = [1,7,11,9,3]

- For all the values of
*X*only*X=7*gives the value of*16*which is minimum among all the integer values of*X*.

Thus, the answer is *7*.

- The first line contains a single integer
*T*, which denotes the number of test cases. - For each test case:
- The first line contains an integer
*N*. - The second line contains
*N*space-separated integers denoting the array*A*.

- The first line contains an integer

For each test case, print the value of*X*which minimizes the value of the function given in the question.

- 1 ≤
*T*≤ 10 - 1≤
*N*≤ 10^{5} - 1 ≤
*A[i]*≤ 10^{9}

Entering edit mode

To handle the range updates efficiently, we use a difference array. The steps are as follows:

**Initialize a difference array**: Create a difference array diff of infinite length initialized to zero. Practically, this array can be managed dynamically using a map.**Apply the operations**:- For each operation (L,R,X), update the difference array as follows:
- diff[L]+=X
- diff[R+1]−=X

- For each operation (L,R,X), update the difference array as follows:
**Convert the difference array to the actual array**:- Calculate the prefix sum to get the final values of the array after all operations are applied.

To find the longest subsequence that meets the given conditions:

Next we can form a array corresponding to values which are there in the map.

**NOTE:** There cann't be more than 2n values in the map.

**Next Occurrence Array**:- Create an array
`next_occurrence`

where`next_occurrence[i]`

points to the next index j such that array[j]=array[i]+K. This helps in quickly finding the next element of the desired subsequence.

- Create an array
**Dynamic Programming**:- Create a DP array
`dp`

where`dp[i]`

stores the maximum length of the subsequence starting from index i. - Iterate over the array from the end to the beginning. For each index iii, update
`dp[i]`

based on`next_occurrence[i]`

.

- Create a DP array
**Reconstruct the Subsequence**:- Start from the smallest possible value whose dp value is maximum and use the
`next_occurrence`

array to reconstruct the longest increasing subsequence of the desired length.

**NOTE**: Part 1 holds because map is missing only those values which are equal to previous value which is there in the map and consecutive equal values are useless because k is a positive integer.

- Start from the smallest possible value whose dp value is maximum and use the

Entering edit mode

**Approach for Problem 2:**

Root the tree at node 1, then find sum[v] and sumWithXorApplied[v] for every node v

then subtree of any node v only changes if we make v as new root or any child of v as the new root (no need to consider other nodes in the subtree of v as the new root, because the new subtree of v will be either one of the subtrees that we get after rooting at any child of v)

Entering edit mode

Approach for problem 3->

(Using Segement Tree)

At a node in the segment tree three values will be stored, suppose the node denotes the range (l,r) in the array, then we will store-->

1) val1= summation of all a[i] : l<=i<=r : i.e. a[l] +a[l+1] +a[l+2]....+ a[r]

2) val2= summation of all i*a[i] : l<=i<=r : i.e. l*a[l] + (l+1)*a[l+1] + (l+2)*a[l+2] +.... + r*a[r]

3) val3= summation of all i*i*a[i] : l<=i<=r : i.e. l*l*a[l] + ((l+1)*(l+1)*a[l+1]) +.......+ r*r*a[r]

now for the update we can do a point update operation on the segment tree and update the val1, val2, and val3 for them as required.

Now for the query part, if we can to use the contribution techinique, i.e. we will calculate the contribution of each of the elements in the given summation equation and then calculate the sum of their individual contribution. Now if we carefully see the expression given it is basically the summation of the sum of all the subarrays that can be formed in the range (l,r). Now if we try to calculate the contribution of each element then it will be -->

let a[i] be the value of that element and cnt be the number of subarrays in (l,r) in which the i'th element is also present. Hence, cnt = [i-l+1] *[r-j+1].

Now the contribution will be-> a[i]*cnt

On simplifying the expression comes out to be-->

a[i]*(r-l+1-lr) + (i*a[i])*(l+r) - (i*i*val)

now if we take the summation of the contribution it will be simply:

our final ans= val1*(r-l+1-lr) + val2*(l+r) - val3 : val1, val2, val3 can be calculated using the segment tree for the range (l,r)

Time-Complexity: Using a segment tree for querying and update hence O((q+n)log(n))

Loading Similar Posts

code you provide a code for this :)