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 an be solved using a simple and 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 whole array is non-increasing, permutations are exhausted.
Let LNIS be a suffix $$$k$$$, where $$$k$$$ is position where it begins. Swap previous element, $$$a_{k-1}$$$ and the next largest number (NLN) that exists in suffix $$$k$$$.
Reverse suffix $$$k$$$.
Learn more about Narayana's algorithm This operations can be performed on a treap! Reversal is known, and swapping is just a combination of split and merge operations. Also we need to find LNIS and NLN. LNIS is sorted by definition, so we can apply binary search in order to find NLN of $$$a_{k-1}$$$.
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
Struct node. ~~~~~ struct node { int val, heap_val, size; //size of this tree node *l, r; //left and right subtrees bool reversed, non_incr, non_decr; int first_elem, last_elem; node(int Val=0) : val(Val), size(1), l(0), r(0), reversed(0) { heap_val = rand() * (1<<15) + rand(); //now heap_val to 2^30 non_incr = non_decr = 1; first_elem = last_elem = Val; } }; typedef node treap; treap root; ~~~~~
Recalc of size and other node parametersint get_size(treap t){
return t ? t->size : 0; //this condition means: t != nullptr
}
void recalc(treap t){
if(!get_size(t)) return;
//size
t->size = get_size(t->l) + get_size(t->r)+1;
//first and last elements
t->first_elem = t->l ? t->l->first_elem : t->val;
t->last_elem = t->r ? t->r->last_elem : t->val;
//non-increasing and non-decreasing properties
bool lni=1, lnd=1, rni=1, rnd=1; //non-increasing/decreasing left and right subtrees
if(t->l){ //unite this value with left subtree
if(!t->l->non_incr || t->l->last_elem < t->val) lni=0;
if(!t->l->non_decr || t->l->last_elem > t->val) lnd=0;
}
if(t->r){ //with right subtree
if(!t->r->non_incr || t->r->first_elem > t->val) rni=0;
if(!t->r->non_decr || t->r->first_elem < t->val) rnd=0;
}
t->non_incr = lni&&rni, t->non_decr = lnd&&rnd;
}
Lazy propagation of reversevoid lazy_pr(treap t){
if(!t || !t->reversed) return;
t->reversed=0;
swap(t->l, t->r), swap(t->non_incr, t->non_decr);
if(t->l) t->l->reversed ^= 1; if(t->r) t->r->reversed ^= 1;
}
Splitvoid split(treap t, treap &l, treap &r, int pos, int tree_begin){
if(!t) return void(l=r=0);
lazy_pr(t);
int val_pos = tree_begin + get_size(t->l);
if(pos <= val_pos) split(t->l, l, t->l, pos, tree_begin), r=t;
else split(t->r, t->r, r, pos, val_pos+1), l=t;
recalc(t);
}
Mergevoid merge(treap &t, treap l, treap r){
lazy_pr(l); lazy_pr(r);
if(!l || !r) t = l?l:r;
else if(l->heap_val > r->heap_val) merge(l->r,l->r,r), t=l;
else merge(r->l,l,r->l), t=r;
recalc(t);
}
Build a treap from arrayvoid build(vector<int> &a){
for(int x:a) merge(root, root, new node(x));
}
Find k, the position of start LNISint find_k(treap t, int tree_end){
lazy_pr(t);
pru(t); br;
if(!t || t->non_incr) return tree_end - get_size(t);
int k = find_k(t->r, tree_end), val_pos = tree_end - get_size(t->r);
if(t->r && k == val_pos && t->r->first_elem <= t->val) k--;
if(t->l && k == val_pos-1 && t->l->last_elem >= t->val){
k = find_k(t->l, val_pos-1);
}
return k; //in fact it finds k-1
}
Find the position of NLNint find_nln(treap t, int x, int tree_begin){
lazy_pr(t);
if(!t) return tree_begin;
if(t->val > x) return find_nln(t->l, x, tree_begin);
return find_nln(t->r, x, tree_begin + get_size(t->l)+1);
}
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
}
