PROBLEM LINK:
Setter- Kasra Mazaheri
Tester- Encho Mishinev
Editorialist- Abhishek Pandey
DIFFICULTY:
HARD
PRE-REQUISITES:
Observations, Segment Tree & Lazy Propagation, Binary Lifting OR Persistant Segment Tree
PROBLEM:
You are given a permutation (array) of size N, answer Q queries of form:
- L \ R - Find maximum length subarray such that the subarray has consecutive numbers.
QUICK-EXPLANATION:
Key to AC- You either need to observe the lemmas or define what operations you need and select appropriate data structure for the problem.
We will explain setter’s solution which uses observations and binary lifting. First, observe the following lemmas:
- Call a subarray [i,j] as “good” if all numbers in it can be re-arranged such that they are all consecutive.
- If 2 intersecting subarrays, A and B are good, then their union A \cup B is also good.
- If 2 intersecting subarrays A and B are good, then their intersection A \cap B is also good.
Lets say we have an array right[i] which tells that “[i,right[i]] is the largest good subarray possible starting from i”. Similarly define another array left[i]. Now, we have this slow, but correct algorithm:
- Start with i=L and j=R. Set ans=1.
- We know that array [i,right[i]\ ] is good. If it also lies within range [L,R] of query, then update ans=max(ans,right[i] - i +1) and set i=right[i]+1. Do this until either right[i] >R
- While j \geq i and left[j] \geq i, consider subarray [left[j],j] and update answer as ans=max(ans,j-left[j]+1). Update j=left[j] - 1
- If i > j, we are done. Else we are yet to consider the subarray [i,j]. By lemma 2, since it is an intersection of 2 good subarrays, the subarray [i,j] is also good. Hence we do a final check for ans=max(ans,j-i+1).
To speed the algorithm up, instead of considering all subarrays one by one, consider them in groups of 2^j at once by binary lifting and update answer considering the largest subarray in that group.
Now only thing we need is to calculate these arrays left[] and right[]. This is achieved via segment tree with lazy propagation. Some elaboration on that is given below:
- Say we are updating for index j - this means we will consider all subarrays ending at index j.
- Let max[i...j] represent maximum element in range [i,j]. Similarly define min[i...j].
- Notice that for a good subarray [i,j], max[i...j] - min[i...j] + (i-j)=0.
- Maintain 2 monotonous queues, one for maintaining max and one for min. We will use them to appropriately update max[i...j] and min[i...j] parts above for the subarrays.
- The (i-j) part is handled by just adding a -1 in range [1,i] (You will notice that -1 will be added i-k times for an index k such that k < i, hence keeping track of this value correctly.
- The same algorithm can be repeated to get the other array, by just reversing the direction of iteration.
EXPLANATION:
We will divide this editorial into 4 sections:
- Discussing and proving the lemmas.
- Discussing how left[] and right[] arrays lead us to a solution.
- Discussing Binary lifting on above.
- Discussing how to calculate the left[] and right[] arrays to wrap up the solution.
This editorial uses point-style format. A little bit of experimentation to keep things clear and maintain stress on important parts. A bit of downside is that the editorial will appear non-trivially lengthier than paragraph-style counterpart (as you might have seen in QE 
). So please make sure that you understand each and every point where-ever bullet points are used.
So lets get started 
PS: A good sub-array, referred below has same meaning as in Quick Explanation, i.e. "Call a subarray [i,j] as “good” if all numbers in it can be re-arranged such that they are all consecutive. "
Discussing and proving the lemmas
Observing these lemmas was quite a task - because while they are easy to prove, you’d need to have some eye or amount of effort in coming up with how they are relevant to solving the problem. This section will prove them just for sake of clarity, and so we can freely invoke them in further section(s) without any fear of unknown. 
Lemma 1: If two intersecting subarrays, say A and B, are good individually then their union A \cup B is also good.
I will give an intuitional proof here. However, you can also find an alternate proof in the bonus corner for the same.
We know that A and B are intersecting , so their intersection has at least 1 element. In other words, A \cap B \neq \phi.
We define 2 variables:
- A'= A - A \cap B, in other words, A' has elements belonging ONLY to A and not to B.
- B'= B - A \cap B, in other words, B' has elements belonging ONLY to B and not to A.
One thing should be clear, that A = A' + A\cap B and similarly B= B' + A\cap B.
Now, I argue the following:
- I start with set A'.
- If I append A \cap B at end of it, I get A, which is a good set.
- I also know that if I start with A \cap B, and append B' at end of it (or vice versa), I get B which is another good set.
- Now, A is good with all elements consecutive. I add B' at end of it. Since A contains all elements of A\cap B, and those elements make a good set if we add elements of B' in the set, then A' + A\cap B + B' is a good set. But we know that A \cup B = A' + A\cap B+B'.
- The argument becomes even simpler if we remove the abstraction of “good”. The argument simply states that since all elements of set A' + A\cap B are consecutive, and all elements of set A\cap B+ B' are also consecutive, then all elements of set A' + A\cap B+B' should be consecutive as well given that repetitions are not allowed!
Hence proved. We can also prove the same via contradiction as in the bonus section.
Lemma 2: If 2 intersecting subarrays A and B are good, then their intersection A \cap B is also good.
The above seems unintuitional at first - and hence it seems a bit complex to prove as well. But I have reaped the easiest way to prove it to you, so read the below carefully:
- We proceed via contradiction. Say A \cap B is NOT good! This means there are some non-consecutive elements in it.
- If the intersection, A\cap B is of size 1, it is good by definition and the proof ends. Else, we continue below with assumption that size of A\cap B is at least 2.
- Recall our definition of A' and B'.
- Since A (i.e. A' + A\cap B) is a good subarray, this means all the “missing” elements between the non-consecutive elements of A\cap B are supplied by A' !
- Similarly, since B (i.e. B' + A\cap B) is a good subarray, this means all the “missing” elements between the non-consecutive elements of A\cap B are supplied by B' !
- This means those “missing elements” lie in A' as well as B'
- But the question guarantees that all elements are distinct! Hence, a contradiction!
Hence our assumption that A \cap B is not a good subarray is false!
Both lemmas are hence, proved.
How the left and right arrays can lead us to solution
Starting here, we will take the first step towards solution.
Lets assume that somehow we got 2 arrays as follows:
- left[]: This array is defined as, left[i] will contain the leftmost index such that [left[i],i] is a good subarray. Note that left[i] can be equal to i.
- right[] : Similar to above, right[i] will contain the rightmost index such that [i,right[i]] is a good subarray. Note that right[i] can be equal to i.
If we have these 2 arrays, then we can solve the problem with following slow, but correct solution:
- Say my query range is [L,R]
- Define two variables, i=L and j=R. Set ans=1.
- We know that array [i,right[i]\ ] is good. If it also lies within range [L,R] of query, then update ans=max(ans,right[i] - i +1) and set i=right[i]+1. Do this until either right[i] >R
- Now, while j \geq i and left[j] \geq i, consider subarray [left[j],j] and update answer as ans=max(ans,j-left[j]+1). Update j=left[j] - 1. Our limit here is i and not L because we have already processed the range [L,i]
- If i > j, we are done. Else we are yet to consider the subarray [i,j]. We know that [i,j] is an intersection of two good subarrays [left[j],j] and [i,right[i]]. Hence, by lemma 2 the subarray [i,j] must also be good! Hence, we update ans=max(ans,j-i+1) and conclude the result.
Now, why is the above correct? The reason we need to spend time on this, despite any hunch or intuition one might have is, the above algorithm is greedy (more on the bonus corner).
The proof is actually short and simple. We will use proof by contradiction.
- Say query is [L,R]. We define i and j as in our algorithm.
- Lets consider the subarray [i,right[i]]. The proof can be replicated for other direction, i.e. [left[j],j]
- Say there is some index k, such that i < k < right[i] and that [k,right[k]] is actually the largest good subarray (and hence solution to our query).
- By lemma 1, we know that if A and B are two intersecting good subarrays, then their union is also good. Consider A=[i,right[i]] and B=[k,right[k]]. Since both A and B are intersecting, as well as good, A \cup B must be good as well! Hence, [i,right[k]] is also a good subarray!
- But if this is the case, then recall the definition of right[i]. It is the rightmost index upto which [i,right[i]] is good! Hence, either right[i] == right[k] (which means [k,right[k]] cannot be optimal solution as its smaller than [i,right[i]]) or we got a contradiction as if right[k] > right[i], then by definition right[i] should have extended further upto right[k].
With this, we conclude this section. It will help you in further section if you are clear with every point of the algorithm mentioned here. In case of issues, please quote the text and ping
Applying Binary Lifting on above
Contrary to your expectations, this section is a breeze. The only pre-requisite you need is that you should know basic binary lifting (eg - able to find LCA using that), and the algorithm described in section 2.
In previous section, our solution was correct, but slow. It was slow because it was considering each good subarray one by one, and in worst case (when all good subarrays have size 1), it will take O(N) to answer the query.
What is our bottleneck above? We are considering all good subarrays one by one. What if we consider multiple of them at once? This is where binary lifting comes in. The algorithm will go like-
- Define a variable k. Note that L,R,i,j etc hold the definitions as in quick explanation and previous section.
- Now, earlier if I am currently at index i, I will just check that [i,right[i]] is within query or not. Instead, I will now check for 2^k of them at once now!
- In other words, I will check if all those 2^k good subarrays lie within query or not. If not, I will decrement k until they all lie within query.
- Once I know that now next 2^k groups are lying in the query region, I just need the size of maximum good subarray among them!
- Hence, I re-define the right[] (and hence left[]) arrays so that right[i][k] stores a pair of values, which are: (\text{end point of } 2^{k'th} \text{group, size of longest good subarray in this group)}
- In easier words, I am just storing the required endpoint (so I know which index to process next), and size of longest good subarray among all 2^k subarrays we considered. These two values are stored in right[i][k]
Essentially, we will consider multiple good subarrays (eg - [i,right[i]], [right[i]+1,right[right[i]] ],\ etc, check size of maximum good subarray among them, and proceed to the next group(s) of good subarrays to process.This processes multiple groups at once and makes our solution fast.
At the end of the day, if you were clear with the brute force algorithm in previous section, you will find we are doing no great feat here- we are just considering multiple groups at once and processing them all at once.
As a closing question to this section, are you able to appreciate the idea of grouping? If yes, then can you also appreciate on how binary lifting can actually be inconsequential to (i.e. not an important part of) the main solution? More about it in the bonus corner
Discussing how to calculate left and right subarrays
Note - In this section, i and j do not have same meaning as in previous sections. [i,j] will have its traditional meaning, i.e. a subarray starting at i and ending at j.
Now on to the big supper. We know that if we somehow have the left[][] and right[][] arrays, then we can very easily solve the problem. But how do we get them?
To keep things simple, this section is divided into 2 sections, each focussing a key step to find these arrays.
Finding binary lifted left and right arrays if we have original left and right arrays
What is the point of this section? The point of the section is that, to find left[i][k] and right[i][k] we require the original left[] and right[] arrays for base case. I want to keep the confusing/tough part for the last because once you get stuck at one point, nothing below that point in editorial makes sense to you.
Note -In this section, I will refer to the original (i.e. without binary lifting) left and right arrays as left_{old}[] and right_{old}[].
Now, suppose we have the original left_{old}[i] and right_{old}[i] arrays as discussed in brute force approach. How can we make the binary-lifted left[][] and right[][] arrays from them?
Without loss of generality, lets discuss calculating right[i][k]. The process to get left[i][k] is pretty much the same.
Base Case-
- If we have the right_{old}[] array, then we can calculate the values of binary lifted right[i][0] easily! Since right[i][0] considers 2^0=1 group, i.e. itself, its endpoint will be right_{old}[i] and size will be right_{old}[i]-i+1. Hence, right[i][0] is calculated for every i.
Recurrence-
The relation is actually pretty same. Say we are calculating right[i][j] and that we have all values of level right[i][j-1] for all i and j.
-
Recall that right[i][j] stores a pair of 2 things - the ending point of the 2^j good subarrays if we start from i, as well as size of longest good subarray among them. Now, the ending point can be easily calculated as:
-
\text{Ending Index =} right[(right[i][j-1] +1)] [j-1]
-
Recall that right[i][j-1] stores ending point of 2^{j-1}'th good subarray starting from i. So right[i][j-1]+1 is the starting point of immediately next good subarray. Starting from there, if we advance 2^{j-1} good subarrays more, then we know the ending point of 2^j'th good subarray starting from i. Thats the interpretation of above.
-
The maximum element can be calculated as : \text{Maximum Element = } max( right[i][j-1].maximum , right[(right[i][j-1]+1)][j-1].maximum)
-
Notice that our entire group of 2^j subarrays is a combination of two groups of size 2^{j-1}, from [i,right[i][j-1]] and [right[i][j-1]+1,right[right[i][j-1]+1][j-1]]. All that we are doing is that, “Longest size of good subarray in this group of size 2^j = max( longest size if first 2^{j-1} good subarrays, longest size in next 2^{j-1} subarrays)”. That is the interpretation of above expression.
With this the recurrence of binary lifting reaches its conclusion. We have the base case to generate right[i][0], and using that we can generate right[i][1] and then similarly use right[i][1] to get right[i][2] and so on.
Check yourself: When we usually combine groups, we check at 3 places instead of two. Consider a separate problem, you are asked to tell maximum number of consecutive 1's in a given range. You will check at 3 places instead of 2, one each for the 2 groups you are combining (for max of answer for those groups), and one more at the point where both groups merge, to see if it gives a new maximum once the groups combine. Why did we not do it here?
Generating original left and right arrays
Congrats if you made it till here. Take a break if you want, you should try to give your full attention to this section. Dont forget to stay hydrated, warm and kind .
Lets start with basic first. Its not very hard to observe that if a subarray/sequence is good (i.e. consecutive), then \text{Max Element - Min Element} gives one less than the length of the sequence! Meaning, for a good subarray [i,j], we will have-
Max[i...j]-Min[i...j] = j-i where Max[i...j] represents max element in range [i,j] and similarly Min[i...j] represents the minimum element in the range.
Hence, we deduce that for a good subarray, Max[i...j] - Min[i...j] + (i-j) = 0. We will use this to calculate the left[] and right[] arrays.
To do so, we will follow the below algorithm. Note that the below algorithm calculates the left[] array. We can reuse it to get the right[] array as well by reversing the direction.
- We make an array var[]. Our plan is, we will process all indices one by one. Say we are processing index j, we will consider all subarrays ending at j. Hence, var[i] (for i < j, obviously) will store if [i,j] is a good subarray or not.
- var[i] will achieve the above by storing value of Max[i...j] - Min[i...j] + (i-j). If its 0, then [i,j] is a good subarray.
- We will use segment tree with lazy propagation (to support range updates) to do the above.
- We will make 2 monotone queues, one to keep track of the required range’s maximum and other to keep track of required range’s minima. If you have trouble seeing why they are needed, check out this problem. The queues will perform function similar to stack to tell the correct values of max[i...j] and min[i...j]. You can check bonus section for more details. For each of required ranges, we will add max[i...j] to it and subtract min[i...j] from it.
- The only thing remaining is to keep track of is value (i-j). While it seems tricky to keep track of, its actually easy. If we are processing j, we add a -1 to range [1,j-1] and this part is done! (More explanation at bonus corner)
- All thats remaining is to check that out of all positions where val[i] is 0, which one is the leftmost. This is a trivial segment tree query.
You can additionally check this comment for alternate explanation.
And with these, you are completely done with the problem! The good part is, in case you are not sure how to go about implementing it, you will be able to understand setter’s code pretty well enough to inspire (and still not copy) the implementation.
With this, we are done with the hardest problem of set.
SOLUTION
Note, setter’s right[] and left[] arrays are not both end-point inclusive, i.e. instead of [i,right[i]] being a good subarray , [i,right[i]-1] will be the good subarray.
Setter
// In The Name Of The Queen
#include<bits/stdc++.h>
#define x first
#define y second
#define lc (id << 1)
#define rc (lc ^ 1)
#define md (l + r >> 1)
using namespace std;
const int N = 500005, LG = 19;
int n, q, P[N], F[N * 4], MNS[N * 4], LZ[N * 4];
pair < int , int > L[N][LG], R[N][LG];
void Build(int id = 1, int l = 1, int r = n + 1)
{
F[id] = l; MNS[id] = LZ[id] = 0;
if (r - l > 1)
Build(lc, l, md), Build(rc, md, r);
}
void Add(int le, int ri, int val, int id = 1, int l = 1, int r = n + 1)
{
if (ri <= l || r <= le)
return ;
if (le <= l && r <= ri)
{
MNS[id] += val;
LZ[id] += val;
return ;
}
Add(le, ri, val, lc, l, md);
Add(le, ri, val, rc, md, r);
MNS[id] = min(MNS[lc], MNS[rc]) + LZ[id];
//if (MNS[lc] <= MNS[rc]) F[id] = F[lc];
//else F[id] = F[rc];
}
int GetFirst(int id = 1, int l = 1, int r = n + 1)
{
if (r - l < 2)
return (l);
if (MNS[lc] <= MNS[rc])
return (GetFirst(lc, l, md));
return (GetFirst(rc, md, r));
}
inline vector < int > Solve()
{
Build(); Add(1, n + 1, 1);
vector < int > MX = {0}, MN = {0}, Fnc(n + 1, 0);
for (int i = 1; i <= n; i ++)
{
while (MX.size() > 1 && P[MX.back()] < P[i])
Add(MX[MX.size() - 2] + 1, MX.back() + 1, P[i] - P[MX.back()]), MX.pop_back();
while (MN.size() > 1 && P[MN.back()] > P[i])
Add(MN[MN.size() - 2] + 1, MN.back() + 1, P[MN.back()] - P[i]), MN.pop_back();
MX.push_back(i); MN.push_back(i); Add(1, i + 1, -1);
assert(!MNS[1]);
Fnc[i] = GetFirst() - 1;
}
return (Fnc);
}
int main()
{
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; i ++)
scanf("%d", &P[i]);
vector < int > A = Solve();
for (int i = 1; i <= n; i ++)
L[i][0].x = A[i], L[i][0].y = i - L[i][0].x;
reverse(P + 1, P + n + 1);
A = Solve();
reverse(A.begin() + 1, A.end());
for (int i = 1; i <= n; i ++)
R[i][0].x = n + 1 - A[i], R[i][0].y = R[i][0].x - i;
R[n + 1][0].x = n + 1;
for (int i = 1; i < LG; i ++)
for (int j = 0; j <= n + 1; j ++)
{
L[j][i].x = L[L[j][i - 1].x][i - 1].x;
L[j][i].y = max(L[j][i - 1].y, L[L[j][i - 1].x][i - 1].y);
R[j][i].x = R[R[j][i - 1].x][i - 1].x;
R[j][i].y = max(R[j][i - 1].y, R[R[j][i - 1].x][i - 1].y);
}
for (int last = 0; q; q --)
{
int l, r, Mx = 1;
scanf("%d%d", &l, &r);
l = (l + last - 1) % n + 1;
r = (r + last - 1) % n + 1;
if (l > r) swap(l, r);
for (int i = LG - 1; ~ i; i --)
if (R[l][i].x <= r + 1)
Mx = max(Mx, R[l][i].y), l = R[l][i].x;
for (int i = LG - 1; ~ i; i --)
if (L[r][i].x >= l - 1)
Mx = max(Mx, L[r][i].y), r = L[r][i].x;
Mx = max(Mx, r - l + 1);
printf("%d\n", Mx);
last = Mx;
}
return 0;
}
Tester
#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;
int n,q;
int nums[1000111];
int pos[1000111];
vector<int> rightAns[1000111];
vector<int> leftAns[1000111];
vector< pair<int,int> > leftFits[1000111];
vector< pair<int,int> > rightFits[1000111];
vector< pair<int,int> > relevant;
int fullSolution[1000111];
void build(int ver, int L, int R)
{
if (L > R)
return;
int i,j;
int mid = (L + R) / 2;
for (int iter = 0; iter < 2; iter++)
{
int leftSeg = mid, rightSeg = mid;
int leftGoalSeg = mid, rightGoalSeg = mid;
int minVal = nums[mid], maxVal = nums[mid];
int minGoalVal = nums[mid], maxGoalVal = nums[mid];
bool bad = false;
relevant.clear();
while(rightSeg <= R && leftSeg >= L && !bad)
{
if (leftSeg == leftGoalSeg && rightSeg == rightGoalSeg && minVal == minGoalVal && maxVal && maxGoalVal)
{
relevant.push_back(make_pair(leftSeg, rightSeg));
if (iter == 0)
rightGoalSeg++;
else
leftGoalSeg--;
continue;
}
while(rightSeg < rightGoalSeg)
{
rightSeg++;
minGoalVal = min(minGoalVal, nums[rightSeg]);
maxGoalVal = max(maxGoalVal, nums[rightSeg]);
}
while(leftSeg > leftGoalSeg)
{
leftSeg--;
minGoalVal = min(minGoalVal, nums[leftSeg]);
maxGoalVal = max(maxGoalVal, nums[leftSeg]);
}
while(maxVal < maxGoalVal)
{
maxVal++;
leftGoalSeg = min(leftGoalSeg, pos[maxVal]);
rightGoalSeg = max(rightGoalSeg, pos[maxVal]);
if (leftGoalSeg < L || rightGoalSeg > R)
{
bad = true;
break;
}
}
while(minVal > minGoalVal)
{
minVal--;
leftGoalSeg = min(leftGoalSeg, pos[minVal]);
rightGoalSeg = max(rightGoalSeg, pos[minVal]);
if (leftGoalSeg < L || rightGoalSeg > R)
{
bad = true;
break;
}
}
}
if (iter == 0)
{
rightAns[ver].resize(R - mid + 1);
rightFits[ver].push_back(relevant[0]);
for (i=1;i<relevant.size();i++)
{
rightFits[ver].push_back(relevant[i]);
}
}
else
{
leftAns[ver].resize(mid - L + 1);
leftFits[ver].push_back(relevant[0]);
for (i=1;i<relevant.size();i++)
{
leftFits[ver].push_back(relevant[i]);
}
}
}
///
int ptr = 0;
int curL = mid, curR = mid;
for (i=0;i<rightFits[ver].size();i++)
{
curL = min(curL, rightFits[ver][i].first);
curR = max(curR, rightFits[ver][i].second);
while(ptr < leftFits[ver].size() && leftFits[ver][ptr].second <= curR)
{
curL = min(curL, leftFits[ver][ptr].first);
ptr++;
}
int ending = (i+1 < rightFits[ver].size()) ? rightFits[ver][i+1].second : R;
for (j=rightFits[ver][i].second;j<=ending;j++)
{
rightAns[ver][j - mid] = curR - curL + 1;
}
}
ptr = 0;
curL = mid;
curR = mid;
for (i=0;i<leftFits[ver].size();i++)
{
curL = min(curL, leftFits[ver][i].first);
curR = max(curR, leftFits[ver][i].second);
while(ptr < rightFits[ver].size() && rightFits[ver][ptr].first >= curL)
{
curR = max(curR, rightFits[ver][ptr].second);
ptr++;
}
int ending = (i+1 < leftFits[ver].size()) ? leftFits[ver][i+1].first : L;
for (j=leftFits[ver][i].first;j>=ending;j--)
{
leftAns[ver][mid - j] = curR - curL + 1;
}
}
///
fullSolution[ver] = max(leftAns[ver].back(), rightAns[ver].back());
build(2*ver, L, mid-1);
build(2*ver+1, mid+1, R);
if (L <= mid-1)
fullSolution[ver] = max(fullSolution[ver], fullSolution[2*ver]);
if (mid+1 <= R)
fullSolution[ver] = max(fullSolution[ver], fullSolution[2*ver+1]);
return;
}
int getBest(int ver, int L, int R)
{
int l = leftFits[ver][0].first, r = leftFits[ver][0].second;
int lft = 0, rt = leftFits[ver].size() - 1, md;
while(lft <= rt)
{
md = (lft + rt) / 2;
if (leftFits[ver][md].first >= L && leftFits[ver][md].second <= R)
{
l = min(l, leftFits[ver][md].first);
r = max(r, leftFits[ver][md].second);
lft = md + 1;
}
else
rt = md - 1;
}
lft = 0;
rt = rightFits[ver].size() - 1;
while(lft <= rt)
{
md = (lft + rt) / 2;
if (rightFits[ver][md].first >= L && rightFits[ver][md].second <= R)
{
l = min(l, rightFits[ver][md].first);
r = max(r, rightFits[ver][md].second);
lft = md + 1;
}
else
rt = md - 1;
}
return r - l + 1;
}
int fullSolve(int ver,int L,int R)
{
if (L > R)
return 0;
return fullSolution[ver];
}
int leftSolve(int ver, int L, int R, int l, int r)
{
if (L > R)
return 0;
int mid = (L + R) / 2;
if (mid < l)
return leftSolve(2*ver+1, mid+1, R, l, r);
int res = leftAns[ver][mid-l];
res = max(res, fullSolve(2*ver+1, mid+1, R));
return max(res, leftSolve(2*ver, L, mid-1, l, r));
}
int rightSolve(int ver, int L, int R, int l, int r)
{
if (L > R)
return 0;
int mid = (L + R) / 2;
if (mid > r)
return rightSolve(2*ver, L, mid-1, l, r);
int res = rightAns[ver][r-mid];
res = max(res, fullSolve(2*ver, L, mid-1));
return max(res, rightSolve(2*ver+1, mid+1, R, l, r));
}
int mainSolve(int ver, int L, int R, int l, int r)
{
int mid = (L + R) / 2;
if (mid > r)
return mainSolve(2*ver, L, mid-1, l, r);
else if (mid < l)
return mainSolve(2*ver+1, mid+1, R, l, r);
else
{
return max(max(leftSolve(2*ver, L, mid-1, l, r), rightSolve(2*ver+1, mid+1, R, l, r)), getBest(ver, l, r));
}
}
int main()
{
int i,j;
scanf("%d %d",&n,&q);
for (i=1;i<=n;i++)
{
scanf("%d",&nums[i]);
pos[ nums[i] ] = i;
}
build(1, 1, n);
int last = 0;
for (i=1;i<=q;i++)
{
int l,r;
scanf("%d %d",&l,&r);
l = (l + last - 1) % n + 1;
r = (r + last - 1) % n + 1;
if (l > r)
{
int swp = l;
l = r;
r = swp;
}
last = mainSolve(1, 1, n, l, r);
printf("%d\n",last);
}
return 0;
}
Time Complexity=O((N+Q)*LogN)
Space Complexity=O((N+Q)*LogN)
CHEF VIJJU’S CORNER
- Prove/Disprove that left[] and right[] array’s values exist for every index i. If you disprove it, discuss how it still leads to correct solution.
Solution
If we allow left[i]=i and similarly allow right[i]=i, the values exist for all values. Else they do not. Setter’s solution allows the above, except that it stores i+1 instead of i for implementation ease.
Proof via contradiction for A U B being good.
Lets assume that A \cup B is NOT good despite A and B being good. Now, A and B are intersecting as well, so their intersection has at least 1 element. In other words, A \cap B \neq \phi.
We define A' and B' similarly as done in editorial. Now, we do the following-
Since A \cup B is not good, there must be at least 2 elements which are not consecutive! Since A\cup B=A'+A\cap B+B', following cases arise here:
- Both these non-consecutive elements belong only to A' or only to B'
- One of the elements belongs to A' or B' and other to A\cap B
- Both elements belong to A\cap B
Given that all elements are distinct, if any of the non-consecutive elements belong to A' or B' - we are done with proof. This is because then we can argue that “If in the set of A' + A\cap B+B', these non-consecutive elements come from, say B' alone, then how is B (i.e. B'+A\cap B) good?”. In other words, if the missing elements between these 2 non-consecutive elements in B' are not contained in A\cap B +A', then they wont be contained in just A\cap B either! Similarly we can argue if both offending elements belong to A'.
The second possibility of one of them belonging to A\cap B and other to A' or B' is easily disregarded because then either A (i.e. A' + A\cap B) or B (i.e. B' +A\cap B) will not be good because of presence of offending elements in them!
The final possibility, is trivially disregarded by lemma 2
I felt that this proof makes a lot more sense, and is more welcoming if read after intuitions in editorial, and hence I kept it here instead of in main editorial so things remain concise.
Note that one merit(?) of this proof is that it proves both the lemmas at once, and can lead to contestant getting both observations at once (…or perhaps neither at all if he gets stuck!)
Why you need to spend time proving correctness of brute force in section 2
Ultimately the algorithm is saying that “If I am at index i and going right, I check [i,right[i]], which is the largest good subarray starting at i, and update i to right[i]+1. I do not check for any index between i and right[i] because i is directly updated to right[i]+1”.
How are we sure that no index in range (i,right[i]) [both exclusive] will lead to correct answer? This point usually is a litmus test on if the problem is greedy or if dp or some other algorithm is required. While its true that a lot of people try for proof by AC in long, it cannot be denied that developing such skills to quickly prove/disprove algorithms helps a lot to advance rating greatly and is indispensible in interviews.
Observation at end of section 3
That was a bit of closing question. I guess if you clicked here, you want to know why I said binary lifting might not actually be a major part of solution? Lets go:
Focus on our bottleneck, and in high level terms tell me what we did to solve it.
The bottleneck was that we were processing good subarrays one by one and that made the solution slow. To solve it, we got an algorithm to process “groups” of subarrays at once!
The answer lies there. Binary lifting is not the only algorithm which can divide your data into groups. Can you think of others? I think square root decomposition etc are good candidates. Basically, we took one algorithm to group our data so we can process entire groups at once. So if you have some other algorithm which groups data (and is applicable here), you can also use it! Hence, if you look from a higher view, Binary Lifting is just an “implementation” of the grouping algorithm required, and we can replace it with any other grouping algorithm we deem fit. Our algorithm will still be correct with the new grouping mechanism.
This is what the software industry calls “Plug-in, Plug-out” principle. They keep the parts of their software as independent as possible, so that if they feel that some part needs optimization or rewriting, they simply “plug” it out, perhaps change to a better implementation, and plug it back it. Given that you did not do a design mishap (As in, using some unneeded variables/references from other part of program), this works really flexibly. And this is why companies etc, at least here in India, try to force candidate to complete a function with required logic (where company can control what information you get/use and dependencies on other parts of code you create) instead of candidates writing entire code themselves.
Why we did not need to check at point of merging while binary lifting
Because all our good subarrays are disjoint!
In the problem of given consecutive 1's, it is possible that on combining 2 groups (simplest example being [1,1,1] and [1,1]) we get a new answer.
Whether you have to check at point of union or not is highly problem specific. In our case, we already establish that going over the groups one by one is ideal. In above example, notice that the ideal sequence of 1's was separated into two groups to lie partially in both. But in our case, we are including the whole group in range.
Point of union is checked if answer can lie partially in left and right subgroup - but since we are not dividing the good subarrays at all - instead keeping them whole, and given the fact that they are all disjoint, we do not come across this issue. Hence, simply taking max of answer of the 2 groups works.
Use of 2 queues in calculating left and right arrays
These queues are needed to keep track of required range’s maxima and minima. Lets see this with an example.
Say my array is [1,2,5,4,3,6]. Say we are currently at index 5 (1-based indexing), i.e. at element 3. Now, the maximum element in range [1,5], [2,5] and [3,5] is 5. But the maximum element in range [4,5] is 4.
Hence, to make sure the values of max[i...j] and min[i...j] remain correct in the solution, we use the queues.
Why adding -1 in range 1 to j-1 is sufficient
We want to keep track of value (i-j) here. See that while processing each j, we add -1 to range [1,j-1]. This means:
- At Index j-1, -1 is added only once by while processing j.
- At index j-2, a -1 was added while we processed for j-1. j added another -1. Total reduction is -2, which is desired.
- At index j-3, we added -1 while processing indices (j-2,j-1,j) and hence total of 3 is deducted which is the requirement
- …
- At index 1, we added -1 while processing indices (2,3,4,...,j) and hence its added (j-1) times, which is the required deduction.
If we are at j, then to account for term i-j, we want value at j-1 to be reduced by 1, …, value at index 1 to be reduced by j-1, which is what happens above.
Setter's Notes
First we have to establish a few lemmas :
- Lemma 1 : If two intersecting subarrays are good then their union is also good.
- Lemma 2 : If two intersecting subarrays are good then their common subarray is also good.
Now let’s try to solve another problem : We are given queries of form (x, y) and we have to divide the subarray (x, y) into minimum number of consecutive good subarrays.
For example if subarray (x, y) looks like (4, 3, 1, 8, 9, 7) then the answer would be 3 : (4, 3) (1) (8, 9, 7). To solve this problem we have to realize that we should take the biggest good subarray we can from the start of (x, y) and then solve the problem for the rest of it (some sort of greedy algorithm). The reason is deducted from the Lemmas introduced above.
Knowing all this, we are left with this greedy problem. To solve it we have to define an array right[i] : The maximum index where subarray [i, right[i]] is good. Similarly define left[i]. Now we can answer a query like this : while right[x] \leq y, we take subarray [x, right[x]] and assign x = right[x] + 1. This is correct since we should act greedy as described earlier. So now we have right[x] > y. We can do the same thing from the end of the array, i.e while left[y] \geq x we take this subarray [left[y], y] and assign y = left[y] - 1. Now if x > y then the problem is solved. Otherwise we know that left[y] < x <= y < right[x]. Considering lemma 2 we deduct that subarray [x, y] is actually also good so we can take the whole subarray as one piece.
This solution solves the problem but it’s slow. We can speed it up via binary lifting; Instead of taking good subarrays one by one, we can take them in goups of 2^i resulting in O(log(N)) time. Now all we are left to do is calculate left[i] (right[i] is calculated similarly).
We can loop over r from 1 to N and keep track of a segment tree where the l-th index of this segment tree equals to max(r - l) - min(r - l) - (r - l). Then a subarray is good if it’s value is equal to zero. We also know that the values are all non-negative so we can keep track of minimum value, then left[r] is the minimum index where we have a minimum (zero) in our segment tree. We can keep track of this segment tree in O(N * log(N)) so the problem is finally solved in O((N + Q) * log(N)).
There’s one more lemma left :
- Lemma 3 : An optimal division of an interval into minimum number of good subarrays always includes a maximum good subarray in that interval. This lemma is derived from lemma 1.
Now that we know how to divide the subarray (x, y) into minimum number of good subarrays, we can also keep track of the maximum size of a good subarray in our binary lifting. Thus the problem is solved in O((N + Q) * log(N)). This concludes the solution.
- The alternate solution of this problem via persistent segment tree is not mentioned in editorial because that’d have made the editorial too verbose. However, if you have a command over this data structure, the question just reduces to making the data-structure do a set of operations. In that case, this editorial by @tmwilliamlin can help you.
Why is this editorial so verbose bruh
I cant help it!
I know that there are a LOT of places I could have just said “And we do X and use Y” without expanding on how and why - but I feel this is one of those problems which even less proficient coders can get the logic of. This question, hence, can serve as a stepping stone for them in their transition to solving harder problems. I made sure that quick explanation suffices for almost all people who do not need the verbose explanation (and hence they can skip parts they feel they know), but for rest its better to have something here.
Related Problems
- Pudding Monsters
- Learning Dishes - Binary Lifting
- Batman and Tree
- ADDMUL