Is it yet another range query for $$$O(log N)$$$? RSQ, RMQ, average, reversal on subsegment and even... next_permutation? Yes, of course! This problem is easily reduced to reversal on subsegment using a very old Narayana's algorithm. This algorithm invented by Indian mathematician Pandit Narayana more than 600 years ago.
Given array $$$a$$$. How to go to its next permutation?
Find the longest non-increasing suffix of the array (LNIS). If $$$k=0$$$, permutations are exhausted.
Let $$$k$$$ is position where LNIS begins. Swap $$$a_{k-1}$$$ and the next largest number (NLN) that exists in suffix $$$k$$$.
Reverse suffix $$$k$$$.
All we need to do is to swap 2 elements and reverse LNIS. If we reverse it first, then it get sorted, so we can apply binary search in order to find NLN of $$$a_{k-1}$$$. Swapping is just a combination of split and merge operations.
But to find LNIS is more difficult. Let in each subtree maintain if the elements in this tree are non-increasing. Then recursion on the treap selects at most one subtree each step and find LNIS for $$$O(log N)$$$.
How to maintain this flag? Elements of a tree are non-increasing if and only if both subtrees are with non-increasing elements and last element of left subtree $$$\geq$$$ value of tree's root $$$\geq$$$ first element of right subtree. Empty subtrees don't affect the non-increasing order. Since we need to reverse segments, we should to maintain also a flag of non-decreasing order. These two flags are swapping while reversing.
The Code
void next_p(int l, int r, treap t=root){
treap lt,rt, swap1,swap2, t2;
split(t,t,rt,r+1);
int tail = tail(t);
if(tail==l){
t->reversed^=1; //just reverse it
merge(t,t,rt); return;
}
l=tail; //elements to the left aren't changed
split(t,lt,t,l-1); split(t,swap1,t,l); //separate p_(n-k)
t->reversed^=1; //it's easier to reverse tail k before finding p_next
int p_next = upper_b(l,r,t); //find p_next by binary search
split(t,t2,t,p_next); split(t,swap2,t,p_next+1); //separate p_next
merge(t,swap1,t); merge(t,t2,t); merge(t,swap2,t); //unite tail k+1
merge(t,lt,t); merge(t,t,rt); //unite all
}
