CPC4 - Editorial

general
, , , , , ,
1

PROBLEM LINK:

Contest

Author: Chhekur

Tester: Pankaj Devesh

Editorialist: Pawan Kushwah

DIFFICULTY:

Easy

PREREQUISITES:

Segment Tree, SQRT Decomposition, DP

PROBLEM:

You have to print number of elements in given range (L,R), which are strictly greater than K.

QUICK EXPLANATION:

You are given an array of elements and you have to perform Q queries on it.
In update query you have to replace the Xth element of array with value Y.
In range query you have to iterate all the element in range from L to R and count elements, which are strictly greater than K.

EXPLANATION:

For an efficient solution of this problem, you must approach this problem via SQRT Decomposition or Segement Tree.
First of all you have to decompose the given array as follows:

  • If the length of given array is n, then size of one decomposed block would be √n.
  • And number of such decomposed blocks would be ceil(n/size_of_one_decomposed_block).
  • For update query, you have to update a particular element of given array as well as the equivalent block of decomposed array.
  • For range query, you have to iterate decomposed array according to given range (L,R).

Author’s solution can be found here.