ENTRY - Editorial

general
, , , ,
1

PROBLEM LINK:

Contest

Mirror

Practice

Author: Rupesh Maity

Tester: Asim Krishna Prasad

Editorialist: Rupesh Maity

DIFFICULTY:

MEDIUM

PREREQUISITES:

Segment Tree, Lazy Propagation

PROBLEM:

Given an array whose elements are set to 0 initially, apply two operations:

Update: given (L, R), update arr[i] = (arr[i] + 1) % 10, for all L <= i <= R.

Sum: given (L, R), find the sum of all the elements of the array in the range L to R (both inclusive).

QUICK EXPLANATION:

Maintain a segment tree where each node contains the count of the number of occurances of each number from 0 to 9 and maintain a lazy component for each of these nodes. An update would require the circular shifting of the count of occurances of these numbers and updating the parent nodes accordingly.

EXPLANATION:

You need to first learn about Lazy Propagation to understand the most standard way to solve this problem. Since we only have integers ranging from 0 to 9, it is possible to maintain the count of occurances of each of these integers in every node of the segment tree. An update to any node requires us to circular shift the occurance count towards the right. That is, if you’re supposed to update for a node representing the range (l, r), such that(L <= l <= r <= R), where (L, R) is the update range in the question, the count of occurances of 0 is shited to 1, 1 to 2 and so on till 9 to 0. This is a circular shift. We’re doing this because all the 0s in this range are converted to 1s and so on for every element. Remember, we are also maintaining a lazy component to be updated later for all the children. The count of all the parent nodes are updated accordingly in each step. Now to find the sum of this range, we can simply use this count of occurances. Remember to take care of those lazy updates :wink:

This editorial was written assuming that you know about lazy propagation. If you don’t, I recommend you solve a few basic lazy propagation related questions and come back to this question later.

Author’s Solution:

Author’s solution can be found here.

2

#include<stdio.h>
main ()
{
int a [5],i,sum=0,ar [5];
printf (“enter the elements of an array\n”);
for (i=0;i <5;i++)
scanf ("%d",&a [i]);
for (i=0;i <5;i++)
{
ar [i]=a [i];
sum=sum+ar [i];
printf ("%d",ar [i]);
}
printf ("%d",sum);
}