### Omar_Elaraby's blog

By Omar_Elaraby, 5 days ago,

I need help to solve this problem from an ICPC Regional Contest

It's easy to find the MEX difference of the subarray [l:r] in O(1), F(l, r). but what makes it hard is to find the maximum MEX difference among all subarrays inside range l:r

• 0

 » 5 days ago, # |   +1 can you provide the link of this problem ?
•  » » 5 days ago, # ^ |   0
•  » » » 5 days ago, # ^ |   +4 here is my codefeel free to ask me anything !
•  » » » » 4 days ago, # ^ |   0 Thank you
•  » » » » » 4 days ago, # ^ |   0 What can i do if i am not allowed to see the contest? Really wanna upsolve this now(
•  » » » » » » 4 days ago, # ^ | ← Rev. 3 →   +1 you need to join this group in order to see the contest
•  » » » » » » » 4 days ago, # ^ |   0 .ComplaintFrame { display: inline-block; position: absolute; top: 0; right: -1.4em; } .ComplaintFrame a { text-decoration: none; color: #ff8c00; opacity: 0.5; } .ComplaintFrame a:hover { opacity: 1; } ._ComplaintFrame_popup p, ._ComplaintFrame_popup button { margin-top: 1rem; } ._ComplaintFrame_popup input[type=submit] { padding: 0.25rem 2rem; } ._ComplaintFrame_popup ul { margin-top: 1em !important; margin-bottom: 1em !important; } ty!
 » 5 days ago, # |   +4 my approach: first, absolute values are hard to work with so let's remove them by calculating the max value of MEX(P,a,b) - MEX(Q,a,b) over all a,b for a query (and similarly MEX(Q,a,b) - MEX(P,a,b)) and answer is the max of these 2now to maximize MEX(P,a,b) - MEX(Q,a,b), let's think of a naive solution first: let's loop over all values X which MEX(P,a,b) can be, and try to minimize MEX(Q,a,b). Well observe that as you extend a subarray by 1 ([a,b] -> [a-1,b] or [a,b+1]) the mex can only increase, so we want to find the smallest subarray where MEX(P,a,b) equals Xwell this can be done with a simple loop:first calculate index: for(int i = 0; i < n; i++) a_index[a[i]] = i; then something like: int l = n, r = -1; for(int i = 0; i < n; i++) { l = min(l, a_index[i]); r = max(r, a_index[i]); } finally we can observe that these "minimal-mex" subarrays in a can only increase in length, so for a query, we can binary search the largest mex for which that corresponding "minimal-length" subarray is contained in the query. And also store MEX(P,a,b) - MEX(Q,a,b) in an array, prefix-maxed
•  » » 4 days ago, # ^ |   0 Thank You