Problem Link:EQUAKE Problem - CodeChef
Why in the editorial LINk:EQUAKE - Editorial
pseudo code
for i=1 to 11:
tree[node].ar[i] = tmp[(i + tree[node].p) % 12];
this has been done???I connnot understand this part that we are again rotating the array ??Since already arr[i] contains maximum value when range elements are roated by i position .
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);
}