PROBLEM LINK:
Author: Pavel Sheftelevich
Tester: Praveen Dhinwa and Hiroto Sekido
Editorialist: Lalit Kundu
DIFFICULTY:
Medium
PREREQUISITES:
Segment Trees/Lazy Propagation
PROBLEM:
Rotation by power F on an integer P is defined as circularly shifting the digits of number F times. Leading zeroes are maintained while rotation.
You have an array A of N(<=8*105) integers where Ai <104. There are M(<=2*105) queries. Queries are of two types:
- Type 0, described by 0 Li Ri Fi: For each element on interval [Li, Ri] rotate it with power Fi.
- Type 1, described by 1 Li Ri: Print the largest element on interval [Li, Ri].
EXPLANATION:
First let us discuss a simple problem where queries are of form “update(i,x) ie. update A[i]=x” and “query(l,r) print largest element in l to r”. This can be done straightaway by segment trees. You can learn about segment trees from here.
Now, suppose the update query requires us to update an interval in the array ie. add value to all elements in range l to r. For this we maintain at each node in the segment tree the value that is to be added in the interval. In lazy version we only mark those child which need to be updated and update it when needed. Before every update/query on an interval we propagate the lazy flag to the children if required. You can learn more on lazy propagation from here.
In our question, the update query is to circularly rotate all elements in a range. Note that a number of K digits is same after K circular rotations, so we can process update queries modulo length. But in our question we can have A_i of length 1 or 2 or 3 or 4 digits, so we process queries modulo LCM(1,2,3,4)=12.
We build a segment tree where each node stores a lazy flag which denotes by how much this segment is to be rotated. Also each node stores and array of size 12, where arr[i] denotes the maximum element in the interval denoted by current node where each element has been rotated by i.
This pseudo code will make it clear:
struct node
{
int ar[12];
// arr[i]=the maximum in the interval denoted by current node
// where each element has been rotated by i.
int p;
// lazy flag for how many rotations are to be propagated
}
node tree[4*MAXN]; //declaring the tree
// we build the tree initially
build_tree(node, a, b)
{
if(a==b) // leaf node
{
for i=1 to 11:
tree[node].ar[i]=rotate(A[a],i) // A[a] rotated by i.
}
build_tree(node*2,a,(a+b)/2); // build left child
build_tree(1+node*2,1+(a+b)/2,b); // build right child
// initialise root value
for(i=1 to 11)
tree[node].ar[i]=max(tree[node*2].ar[i],tree[1+node*2].ar[i])
}
// rotate each element A[i] to A[j] by value
update(node, a, b, i, j, value)
{
if(tree[node].p!=0) // this node needs to be updated
{
//we need to rotate each element by tree[node].p
//this is equivalent to left circularly rotating the array tree[node].ar by tree[node].p
tmp=tree[node].ar
for i=1 to 11:
tree[node].ar[i] = tmp[(i + tree[node].p) % 12];
if(a!=b) //propagate the rotation to children
{
tree[node*2].p += tree[node].p; // Mark child as lazy
tree[node*2].p %= 12;
tree[node*2+1].p += tree[node].p; // Mark child as lazy
tree[node*2+1].p %= 12;
}
tree[node].p=0; //reset the lazy flag for current interval
}
if(current segment not with range [i,j])
return;
if(segment[a,b] within [i,j])
{
rotate whole array tree[node].ar by tree[node].p;
if(a!=b)
mark children as lazy;
reset current node;
return;
}
update_tree(node*2, a, (a+b)/2, i, j, value); // Updating left child
update_tree(1+node*2, 1+(a+b)/2, b, i, j, value); // Updating right child
for i=0 to 11
tree[node].ar[i] = max(tree[node*2].ar[i], tree[node*2+1].ar[i]); // Init root value
}
//query tree to get max element value in range [i,j]
query(node, a, b, i, j)
{
if [a,b] out of range: return -inf;
if(tree[node].p!=0) // node needs to be updated
{
update array ar;
if(a!=b) mark children lazy;
reset current node;
}
if(segment[a,b] with [i,j])
return tree[node].ar[tree[node].p];
q1= query(node*2, a, (a+b)/2, i, j); // Query left child
q2= query(node*2, 1+(a+b)/2, b, i, j); // Query left child
return max(q1,q2);
}
Each update and query takes O(log N) worst case.