Is it possible to perform this for $$$O(log N)$$$?
An algorithm for obtaining the next permutation of the set of numbers was invented by Indian mathematician Pandit Narayana more than 600 years ago. Given array $$$a$$$. The way the next permutation is found with Narayana's algorithm: 1. Find the longest non-increasing suffix (LNIS). Let in starts in position $$$k$$$. If $$$k=0$$$, permutations are exhausted. 2. Swap $$$a_{k-1}$$$ and the next largest number (NLN) that exists in suffix $$$k$$$. 3. Reverse suffix $$$k$$$. On a subsegment of the array the next permutation can be found in the same way.
Time complexity: $$$O(N)$$$, because in worst case suffix can be of length $$$n-1$$$. But there is a way to reverse a subsegment for $$$O(log N)$$$ using a treap. So the problem to obtain the next permutation for $$$O(log N)$$$ can be transformed to subsegment reversing.
First, reverse LNIS. 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 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 subsegments, we should to maintain also a flag of non-decreasing order. These two flags are swapping while reversing this tree.
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 NDSint find_nds(treap t, int tree_end){
lazy_pr(t);
if(!t || t->non_incr) return tree_end - get_size(t);
int nds = find_nds(t->r, tree_end), val_pos = tree_end - get_size(t->r);
if(t->r && nds == val_pos && t->r->first_elem <= t->val) nds--;
if(t->l && nds == val_pos-1 && t->l->last_elem >= t->val){
nds = find_nds(t->l, val_pos-1);
}
return nds;
}
Find the next largest numberint 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
}