Next Permutation on Subsegment

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	maomao90	163
2	Um_nik	163
4	atcoder_official	161
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	nor	153
9	Dominater069	153

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

Lazy propagation of reverse

void lazy_pr(treap t){
    if(!t || !t->reversed) return;
    t->reversed=0;
    swap(t->l, t->r), swap(t->non_incr, t->non_decr), swap(t->first_elem, t->last_elem);
    if(t->l) t->l->reversed ^= 1; if(t->r) t->r->reversed ^= 1;
}

Recalc of size and other node parameters

int 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
    lazy_pr(t->l); lazy_pr(t->r);
    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;
}

Split

void 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);
}

Merge

void 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 array

void build(vector<int> &a){
    for(int x:a) merge(root, root, new node(x));
}

Find k, the position of start LNIS

int find_k(treap t, int tree_end){
    lazy_pr(t);
    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;
}

Find the position of NLN

int 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 l, r, swap1, swap2, between;
    split(t, t, r, R+1, 0);
    int k = find_k(t, R)+1;
    split(t, l, t, max(L,k), 0);
    t->reversed ^= 1;
    if(k>L) {
        split(l, l, swap1, k-1, 0);
        int nln = find_nln(t, swap1->val, k);
        //pr(nln);
        split(t, between, t, nln, k); split(t, swap2, t, nln+1, nln);
        merge(t, swap1, t); merge(t, between, t); merge(t, swap2, t);
    }
    merge(t, l, t); merge(t, t, r);
}

Rev.	By	When	Δ	Comment
en18	Guslix	2021-08-21 14:15:26	45
en17	Guslix	2021-08-20 20:00:01	51
en16	Guslix	2021-08-20 19:58:14	53
en15	Guslix	2021-08-20 19:51:12	1	Tiny change: '$O(\log n).$\n\n\n\n<' -> '$O(\log n)$\n\n\n\n<'
en14	Guslix	2021-08-20 19:31:34	51	(published)
en13	Guslix	2021-08-20 18:35:11	422
en12	Guslix	2021-08-20 18:18:48	1405
en11	Guslix	2021-08-20 15:34:52	1142
en10	Guslix	2021-08-20 09:41:35	450
en9	Guslix	2021-08-19 23:59:09	698
en8	Guslix	2021-08-19 20:59:20	129
en7	Guslix	2021-08-19 20:20:06	5
en6	Guslix	2021-08-19 20:19:06	15
en5	Guslix	2021-08-19 20:15:03	548
en4	Guslix	2021-08-19 19:55:57	3193
en3	Guslix	2021-08-19 19:40:49	670
en2	Guslix	2021-08-19 19:01:53	402
en1	Guslix	2021-08-19 10:54:29	1255	Initial revision (saved to drafts)

The Code

History