Range Maximum Queries
You are given an array of integers, and are asked a lot of queries (at most 10^8) like give two indices find the maximum of all the integers in the array whose index lies between those two.
The generation of the queries as given in the question is
x = x + 7 (mod N - 1)
y = y + 11 (mod N)
l = min(x, y)
r = max(x, y)
You need to find maximum of a* such that l <= i <= r.
The generation of (l, r) pairs is like a pseudo random procedure, so its very very hard task to find a pattern in that. Now as we got (l, r) for each query the finding maximum is quite a standard task of range queries.
There are a lot of ways to find range queries. Some of them are
- O(1) per Update and O(N) per query : Using an array, we can update each element in O(1) and when queried iterate through all elements from l to r.
- O(log N) per Update and O(log N) per query : There are a lot of ways to do this. We can use Segment trees, Binary index trees, etc.
- O(N) per Update and O(1) per query : We can use Sparse Table to solve this case.
The methods used for 2 and 3 are very standard and their explanation can be found at a lot of places.
Some useful links for solving Range Queries using Method 2 are
You can find very useful explanation of all methods including the sparse table method here in this Topcoder Tutorial.