In this post, we will solve HackerRank Inverse RMQ Problem Solution.
Range Minimum Query is a well-known problem: given an array of distinct integers with size n = 2 and m queries, find the minimum element on subsegment [L₁, Ri]. One of the most efficient and famous solutions to this problem is a segment tree. A segment tree is a full binary tree with 2. n – 1 nodes where the leaves contain the values of the original array and each non-leaf node contains the minimum value of its entire subtree.
Usually, a segment tree is represented as an array of integers with 2n-1 elements. The left child of the ith node is in the (2i+1)th cell, and the right child is in the (2- ¿ + 2)th cell. For example, A = [1, 1, 3, 1, 2, 3, 4] represents the following segment tree where the first number in a node describes the array Index, &, in A and the second number denotes the value stored at index i (which corresponds to the minimum value in that node’s subtree):
You’ve just used ʼn distinct integers to construct your first segment tree and saved it as an array, A. of 2n-1 values. Unfortunately, some evil guy came and either shuffled or altered the elements in your array. Can you use the altered data to restore the original array? If no, print NO on a new line; otherwise, print two lines where the first line contains the word YES and the second line contains 2. n-1 space-separated integers denoting the array’s original values. If there are several possible original arrays, print the lexicographically smallest one.
Input Format
The first line contains a single integer, n. denoting the size of the array. The second line contains 2. n-1 space-separated integers denoting the shuffled values of the segment tree.
Sample Input 0
4
3 1 3 1 2 4 1
Sample Output 0
YES
1 1 3 1 2 3 4
Explanation 0
This is the same segment tree shown in the Problem Statement above.
Sample Input 1
2
1 1 1
Sample Output 1
NO
Explanation 1
A segment tree with three nodes would consist of a root, a left child, and a right child. Because all three numbers in this array are the same and the leaves of the segment tree must be N distinct integers, it’s not possible to reconstruct the original array.
Inverse RMQ C Solution
#include <assert.h>
#include <stddef.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char* readline();
char** split_string(char*);
int* canTree(int n, int* arr){
int logn = 0;
while(n >> logn > 1){
logn++;
}
int sortarr[2*n - 1];
for(int i = 0; i < 2*n - 1; i++){
sortarr[i] = arr[i];
int curr = i;
int inplace = 0;
while(curr > 0 && inplace == 0){
int next = (curr - 1)/2;
if(sortarr[next] < sortarr[curr]){
int temp = sortarr[curr];
sortarr[curr] = sortarr[next];
sortarr[next] = temp;
curr = next;
}
else{
inplace = 1;
}
}
}
for(int i = 0; i < 2*n - 1; i++){
int temp = sortarr[0];
sortarr[0] = sortarr[2*n - i - 2];
sortarr[2*n - i - 2] = temp;
int curr = 0;
int reheaped = 0;
while(reheaped == 0){
int next = curr;
if(2*curr + 1 < 2*n - i - 2 && sortarr[2*curr + 1] > sortarr[next]){
next = 2*curr + 1;
}
if(2*curr + 2 < 2*n - i - 2 && sortarr[2*curr + 2] > sortarr[next]){
next = 2*curr + 2;
}
if(next != curr){
temp = sortarr[curr];
sortarr[curr] = sortarr[next];
sortarr[next] = temp;
curr = next;
}
else{
reheaped = 1;
}
}
}
int *levellist[logn + 1];
int numatlevel[logn + 1];
int **numopen[logn + 1];
for(int i = 0; i <= logn; i++){
levellist[i] = malloc((1<<i)*sizeof(int));
assert(levellist[i] != NULL);
for(int j = 0; j < 1<<i; j++){
levellist[i][j] = INT_MIN;
}
numopen[i] = malloc((1<<i)*sizeof(int*));
assert(numopen[i] != NULL);
for(int j = 0; j <= (1<<i); j++){
numopen[i][j] = malloc((logn + 1)*sizeof(int));
assert(numopen[i][j] != NULL);
for(int k = 0; k <= logn; k++){
numopen[i][j][k] = 0;
}
}
numatlevel[i] = 0;
}
numopen[0][0][0] = 1;
int index = 0;
while(index < 2*n - 1){
int currval = sortarr[index];
int currindex = index;
while(index < 2*n - 1 && sortarr[index] == currval){
index++;
}
int numreps = index - currindex;
int level = (logn + 1) - numreps;
int pos = 0;
if(level < 0 || numopen[0][0][level] == 0){
return NULL;
}
for(int i = 0; i < level; i++){
assert(numopen[i][pos][level] > 0);
numopen[i][pos][level] -= 1;
for(int j = level + 1; j <= logn; j++){
numopen[i][pos][j] += 1;
}
if(i + 1 < level && numopen[i + 1][2*pos][level] > 0){
pos = 2*pos;
}
else{
pos = 2*pos + 1;
}
}
for(int i = level; i <= logn; i++){
levellist[i][pos] = currval;
for(int j = i + 1; j <= logn; j++){
numopen[i][pos][j] += 1;
}
pos = 2*pos;
}
}
int *toreturn = malloc((2*n - 1)*sizeof(int));
assert(toreturn != NULL);
index = 0;
for(int i = 0; i <= logn; i++){
for(int j = 0; j < (1<<i); j++){
toreturn[index] = levellist[i][j];
index++;
}
}
return toreturn;
}
int main() {
FILE* fptr = fopen(getenv("OUTPUT_PATH"), "w");
char* n_endptr;
char* n_str = readline();
int n = strtol(n_str, &n_endptr, 10);
if(n_endptr == n_str || *n_endptr != '\0'){ exit(EXIT_FAILURE);}
char** vals_str = split_string(readline());
int *treelist = malloc((2*n - 1) * sizeof(int));
for(int i = 0; i < 2*n - 1; i++){
char* currval_str = vals_str[i];
char* currval_endptr;
int currval = strtol(currval_str, &currval_endptr, 10);
if(currval_endptr == currval_str || *currval_endptr != '\0'){ exit(EXIT_FAILURE);}
treelist[i] = currval;
}
int* arrlist = canTree(n, treelist);
if(arrlist == NULL){
fprintf(fptr, "NO");
}
else{
fprintf(fptr, "YES\n");
for(int i = 0; i < 2*n - 2; i++){
fprintf(fptr, "%d ", arrlist[i]);
}
fprintf(fptr, "%d", arrlist[2*n - 2]);
}
return 0;
}
char* readline() {
size_t alloc_length = 1024;
size_t data_length = 0;
char* data = malloc(alloc_length);
while (true) {
char* cursor = data + data_length;
char* line = fgets(cursor, alloc_length - data_length, stdin);
if (!line) { break; }
data_length += strlen(cursor);
if (data_length < alloc_length - 1 || data[data_length - 1] == '\n') { break; }
size_t new_length = alloc_length << 1;
data = realloc(data, new_length);
if (!data) { break; }
alloc_length = new_length;
}
if (data[data_length - 1] == '\n') {
data[data_length - 1] = '\0';
}
if(data[data_length - 1] != '\0'){
data_length++;
data = realloc(data, data_length);
data[data_length - 1] = '\0';
}
data = realloc(data, data_length);
return data;
}
char** split_string(char* str) {
char** splits = NULL;
char* token = strtok(str, " ");
int spaces = 0;
while (token) {
splits = realloc(splits, sizeof(char*) * ++spaces);
if (!splits) {
return splits;
}
splits[spaces - 1] = token;
token = strtok(NULL, " ");
}
return splits;
}
Inverse RMQ C++ Solution
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> ii;
typedef pair<long long, int> lli;
typedef long long ll;
typedef unsigned long long ull;
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Rep(i,a,b) for(int i=a;i>=b;i--)
#define REP(i, n) for(int i = 0; i < n; i++)
#define FOR(i, f) for(__typeof(f.begin()) i = f.begin(); i != f.end(); i++)
#define fi first
#define se second
#define pb push_back
#define sz(s) int(s.size())
#define reset(f, x) memset(f, x, sizeof(f))
#define all(x) x.begin(), x.end()
#define two(x) (1LL << x)
#define getbit(x, i) ((x >> (i-1)) & 1LL)
#define onbit(x, i) (x | (1LL << (i-1)))
#define offbit(x, i) (x & ~(1 << (i-1)))
const int N = (1 << 18) + 10;
int t[4*N], a[4*N], n, m;
int b[N], cnt[N], nn, vmax;
bool was[4*N];
int ans[4*N];
vector<ii> p;
set<int> num[50];
bool cmp(ii a, ii b) {
if (a.se != b.se) return a.se > b.se;
return a.fi < b.fi;
}
bool check(int i) {
if (2*i+1 >= m) return true;
if (ans[i] != min(ans[i*2+1], ans[i*2+2])) return false;
return (check(i*2+1) & check(i*2+2));
}
bool solve() {
REP(i, m) if (!was[i]) {
int h = vmax-trunc(log(i+1)/log(2));
if (num[h].empty()) return false;
int now = i;
auto it = num[h].begin();
if (i) it = num[h].upper_bound(ans[(i-1)/2]);
if (it == num[h].end()) return false;
For(cnt, 1, h) {
ans[now] = *it;
was[now] = true;
now = now*2 + 1;
}
num[h].erase(it);
}
return true;
}
int main() {
//freopen("in.txt","r",stdin);
cin >> n;
m = 2*n-1;
For(i, 1, m) cin >> a[i];
sort(a+1, a+m+1);
a[0] = a[1] - 1;
vmax = trunc(log(n) / log(2)) + 1;
For(i, 1, m)
if (a[i] != a[i-1]) p.pb(ii(a[i], 1));
else p.back().se++;
sort(all(p), cmp);
REP(i, sz(p)) if (p[i].se <= vmax) num[p[i].se].insert(p[i].fi);
// FOR(i, p) cout << i->fi << ' ' << i->se << "\n";
if (sz(p) != n) cout << "NO";
else if (!solve()) cout << "NO";
else {
cout << "YES\n";
REP(i, m) cout << ans[i] << ' ';
}
}
Inverse RMQ C Sharp Solution
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution {
static int[] GetCounts(int n){
var arr = new int[n];
int step = 1;
while(step<=n){
for(int i=0;i<n;i+=step){
arr[i]++;
}
step*=2;
}
return arr;
}
//sorts val and ind after values
static void Sort(ref int[] val,ref int[] ind){
var zipped = val.Zip(ind, (x,y)=>new {x,y}).OrderByDescending(pair=>pair.x).ToList();
val = zipped.Select(pair=>pair.x).ToArray();
ind = zipped.Select(pair=>pair.y).ToArray();
}
static void Recursion(int[] res, int[] nums, int index, int a, int b, int n){
if (b >= n)
{
Console.WriteLine("YES");
Console.WriteLine(String.Join(" ", res));
}
else
{
for (int i = 0; i < b - a; i++)
{
if (res[a + i] > nums[index + i])
{
int j = index + i + 1;
while (j < index + b - a && res[a + i] > nums[j])
{
j++;
}
if (j == index + b - a)
{
Console.WriteLine("NO");
return;
}
else
{
int temp = nums[j];
for (int z = j; z >index+i; z--)
{
nums[z] = nums[z-1];
}
nums[index + i] = temp;
}
}
}
for (int i = 0; i < b - a; i++)
{
if (b + 2 * i == 4018)
{
var cur = new int[b - a];
for(int q = 0; q < b-a; q++)
{
cur[q] = res[a + q];
}
}
if (b + 2 * i + 1 == 4018)
{
var cur = new int[b - a];
for (int q = 0; q < b - a; q++)
{
cur[q] = nums[index+q];
}
}
res[b + 2 * i] = res[a + i];
res[b + 2 * i + 1] = nums[index + i];
}
Recursion(res, nums, index + b - a, b, b + 2 * (b - a), n);
}
}
static void Solve(int n, int[] arr){
var idealcounts = GetCounts(n).OrderByDescending(t=>t).ToArray();
int N=arr.Length;
Array.Sort(arr);
var nums = new int[n];
var counts = new int[n];
int ind1=0,ind2=0;
while(ind1<n){
nums[ind1]=arr[ind2];
while(ind2<N && nums[ind1]==arr[ind2]){
counts[ind1]++;
ind2++;
}
ind1++;
if(ind2==N && ind1!=n){
Console.WriteLine("NO");
return;
}
}
Sort(ref counts, ref nums);
for(int i=0;i<n;i++){
if(counts[i]!=idealcounts[i]){
Console.WriteLine("NO");
return;
}
}
int[] res = new int[N];
int step =1;
for(int i=0;i<n;){
res[i]=nums[0];
i+=step;
step*=2;
}
Recursion(res, nums, 1, 0, 1, n);
}
static void Main(String[] args) {
int n = Convert.ToInt32(Console.ReadLine());
string[] nums = Console.ReadLine().Split(' ');
int[] arr = Array.ConvertAll(nums, t=>Convert.ToInt32(t));
Solve(n,arr);
}
}
Inverse RMQ Java Solution
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.HashMap;
import java.io.IOException;
import java.io.Reader;
import java.io.InputStreamReader;
import java.util.TreeSet;
import java.util.TreeMap;
import java.util.StringTokenizer;
import java.util.Map;
import java.util.Map.Entry;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.BufferedReader;
import java.io.InputStream;
/**
* Built using CHelper plug-in
* Actual solution is at the top
*/
public class Solution {
public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
InputReader in = new InputReader(inputStream);
OutputWriter out = new OutputWriter(outputStream);
InversedRMQ solver = new InversedRMQ();
solver.solve(1, in, out);
out.close();
}
static class InversedRMQ {
public void solve(int testNumber, InputReader in, OutputWriter out) {
int n = in.readInt();
int k = 2 * n - 1;
final Map<Integer, Integer> count = new TreeMap<>();
for (int i = 0; i < k; i++) {
int x = in.readInt();
count.put(x, count.getOrDefault(x, 0) + 1);
}
final TreeSet<Integer>[] types = new TreeSet[k + 1];
final Map<Integer, Integer> result = new HashMap<>();
for (int i = 0; i < types.length; i++) {
types[i] = new TreeSet<>();
}
int log = 0, n_ = n;
while (n_ > 0) {
n_ >>= 1;
log++;
}
types[log].add(1);
for (Map.Entry<Integer, Integer> entry : count.entrySet()) {
if (types[entry.getValue()].isEmpty()) {
out.printLine("NO");
return;
}
int wh = types[entry.getValue()].pollFirst();
result.put(entry.getKey(), wh);
for (int i = 0; i < entry.getValue() - 1; i++) {
types[entry.getValue() - i - 1].add(wh * 2 + 1);
wh <<= 1;
}
}
final int[] ans = new int[k + 1];
for (Map.Entry<Integer, Integer> entry : result.entrySet()) {
int wh = entry.getValue(), value = entry.getKey();
while (wh <= k) {
ans[wh] = value;
wh <<= 1;
}
}
out.printLine("YES");
for (int i = 1; i <= k; i++) {
out.print(ans[i], ' ');
}
out.printLine();
}
}
static class OutputWriter {
private PrintWriter writer;
public OutputWriter(Writer writer) {
this.writer = new PrintWriter(writer);
}
public OutputWriter(OutputStream stream) {
this(new OutputStreamWriter(stream));
}
public void print(Object... args) {
for (Object arg : args) {
writer.print(arg);
}
}
public void printLine(Object... args) {
print(args);
writer.println();
}
void close() {
writer.close();
}
}
static class InputReader {
private BufferedReader reader;
private StringTokenizer tokenizer;
public InputReader(Reader reader) {
this.reader = new BufferedReader(reader);
}
public InputReader(InputStream stream) {
this(new InputStreamReader(stream));
}
public String nextLine() {
try {
return reader.readLine();
} catch (IOException e) {
throw new RuntimeException(e);
}
}
public String readWord() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
tokenizer = new StringTokenizer(nextLine());
}
return tokenizer.nextToken();
}
public int readInt() {
return Integer.parseInt(readWord());
}
}
}
Inverse RMQ JavaScript Solution
var VALUE = 0;
var LEFT = 1;
var RIGHT = 2;
var UP = 3;
var COLOR = 4;
var WIDTH = 5;
var RED = 0;
var BLACK = 1;
var MIN_SIZE = 4;
var RBTree = function (cmp) {
if (cmp === undefined) {
cmp = function (a, b) {
if (a < b) {
return -1;
}
if (a > b) {
return 1;
}
return 0;
};
}
this.cmp = cmp;
this.nodes = [];
this.size = 0; // total used and unused nodes
this.next = null; //head of linked list of unused nodes
this.count = 0; // number of used nodes
this.root = null //the root index node
};
RBTree.prototype.resize = function (new_size) {
if (new_size > this.size) {
var min_i = this.nodes.length;
var i = new_size * WIDTH;
var next = this.next;
this.nodes.length = i;
while (i > min_i) {
i -= WIDTH;
this.nodes[i] = next;
next = i;
}
this.next = next;
this.size = new_size;
} else {
}
}
RBTree.prototype.insert = function (x) {
if (this.count >= this.size) {
if (this.size < MIN_SIZE) {
this.resize(MIN_SIZE);
} else {
this.resize(this.size * 2);
}
}
var idx = this.next;
this.next = this.nodes[idx];
this.nodes[idx + VALUE] = x;
this.nodes[idx + LEFT] = null;
this.nodes[idx + RIGHT] = null;
this.nodes[idx + COLOR] = RED;
this.count++;
if (this.root === null) {
this.nodes[idx + UP] = null;
this.root = idx;
} else {
var parent = this.root;
while (true) {
if (this.cmp(x, this.nodes[parent + VALUE]) < 0) {
var leaf = this.nodes[parent + LEFT];
if (leaf == null) {
this.nodes[parent + LEFT] = idx;
this.nodes[idx + UP] = parent;
break;
} else {
parent = leaf;
}
} else {
var leaf = this.nodes[parent + RIGHT];
if (leaf == null) {
this.nodes[parent + RIGHT] = idx;
this.nodes[idx + UP] = parent;
break;
} else {
parent = leaf;
}
}
}
}
this.fix_coloring_near(idx);
};
RBTree.prototype.fix_coloring_near = function (idx) {
var parent = this.nodes[idx + UP];
if (parent == null) {
this.nodes[idx + COLOR] = BLACK;
} else if (this.nodes[parent + COLOR] == RED) {
var gramps = this.nodes[parent + UP];
var uncle = gramps;
var g_dir;
if (this.nodes[gramps + LEFT] == parent) {
g_dir = LEFT;
uncle = this.nodes[gramps + RIGHT];
} else {
g_dir = RIGHT;
uncle = this.nodes[gramps + LEFT];
}
var uncle_color = BLACK;
if (uncle !== null) {
uncle_color = this.nodes[uncle + COLOR];
}
if (uncle_color == RED) {
this.nodes[uncle + COLOR] = BLACK;
this.nodes[parent + COLOR] = BLACK;
this.nodes[gramps + COLOR] = RED;
this.fix_coloring_near(gramps);
} else {
if (this.nodes[parent + g_dir] !== idx) {
var p_dir = LEFT + RIGHT - g_dir;
var child = this.nodes[idx + g_dir];
this.nodes[parent + p_dir] = child;
if (child !== null) {
this.nodes[child + UP] = parent;
}
this.nodes[idx + g_dir] = parent;
this.nodes[parent + UP] = idx;
this.nodes[gramps + g_dir] = idx;
this.nodes[idx + UP] = gramps;
idx = parent;
parent = this.nodes[parent + UP];
}
this.nodes[gramps + COLOR] = RED;
this.nodes[parent + COLOR] = BLACK;
var c_dir = LEFT + RIGHT - g_dir;
var child = this.nodes[parent + c_dir];
this.nodes[gramps + g_dir] = child;
if (child !== null) {
this.nodes[child + UP] = gramps;
}
var ggramps = this.nodes[gramps + UP];
if (ggramps === null) {
this.nodes[parent + UP] = null;
this.root = parent;
} else {
if (this.nodes[ggramps + LEFT] === gramps) {
this.nodes[ggramps + LEFT] = parent;
} else {
this.nodes[ggramps + RIGHT] = parent;
}
this.nodes[parent + UP] = ggramps;
}
this.nodes[parent + c_dir] = gramps;
this.nodes[gramps + UP] = parent;
}
}
};
RBTree.prototype.remove = function (idx) {
if (this.nodes[idx + LEFT] !== null && this.nodes[idx + RIGHT] !== null) {
var single_parent = this.nodes[idx + RIGHT];
while (this.nodes[single_parent + LEFT] !== null) {
single_parent = this.nodes[single_parent + LEFT];
}
this.nodes[idx + VALUE] = this.nodes[single_parent + VALUE];
idx = single_parent;
}
var parent = this.nodes[idx + UP];
if (this.nodes[idx + COLOR] === RED) {
if (this.nodes[parent + LEFT] === idx) {
this.nodes[parent + LEFT] = null;
} else {
this.nodes[parent + RIGHT] = null;
}
} else {
var child = this.nodes[idx + LEFT];
if (child === null) {
child = this.nodes[idx + RIGHT];
}
if (child !== null) {
this.nodes[child + COLOR] = BLACK;
if (parent === null) {
this.nodes[child + UP] = null;
this.root = child;
} else {
if (this.nodes[parent + LEFT] === idx) {
this.nodes[parent + LEFT] = child;
} else {
this.nodes[parent + RIGHT] = child;
}
this.nodes[child + UP] = parent;
}
} else {
if (parent === null) {
this.root = null;
} else {
if (this.nodes[parent + LEFT] === idx) {
this.nodes[parent + LEFT] = null;
this.fix_short_branch(parent, LEFT);
} else {
this.nodes[parent + RIGHT] = null;
this.fix_short_branch(parent, RIGHT);
}
}
}
}
this.nodes[idx] = this.next;
this.next = idx;
this.count--;
};
RBTree.prototype.fix_short_branch = function (idx, short_dir) {
var long_dir = LEFT + RIGHT - short_dir;
var short_child = this.nodes[idx + short_dir];
var long_child = this.nodes[idx + long_dir];
if (this.nodes[long_child + COLOR] === RED) {
this.nodes[long_child + COLOR] = BLACK;
this.nodes[idx + COLOR] = RED;
var kid = this.nodes[long_child + short_dir];
var gramps = this.nodes[idx + UP];
if (gramps === null) {
this.root = long_child;
} else {
if (this.nodes[gramps + LEFT] === idx) {
this.nodes[gramps + LEFT] = long_child;
} else {
this.nodes[gramps + RIGHT] = long_child;
}
}
this.nodes[long_child + UP] = gramps;
this.nodes[long_child + short_dir] = idx;
this.nodes[idx + UP] = long_child;
this.nodes[idx + long_dir] = kid;
this.nodes[kid + UP] = idx;
long_child = kid;
}
var long_long = this.nodes[long_child + long_dir];
var long_short = this.nodes[long_child + short_dir];
var long_long_color = BLACK;
if (long_long !== null && this.nodes[long_long + COLOR] === RED) {
long_long_color = RED;
}
var long_short_color = BLACK;
if (long_short !== null && this.nodes[long_short + COLOR] === RED) {
long_short_color = RED;
}
if (this.nodes[idx + COLOR] === BLACK && long_long_color === BLACK && long_short_color === BLACK) {
this.nodes[long_child + COLOR] = RED;
var gramps = this.nodes[idx + UP];
if (gramps === null) {
} else {
if (this.nodes[gramps + LEFT] === idx) {
this.fix_short_branch(gramps, LEFT);
} else {
this.fix_short_branch(gramps, RIGHT);
}
}
} else if (this.nodes[idx + COLOR] === RED && long_long_color === BLACK && long_short_color === BLACK) {
this.nodes[long_child + COLOR] = RED;
this.nodes[idx + COLOR] = BLACK;
} else {
if (long_long_color === BLACK) {
this.nodes[long_child + COLOR] = RED;
this.nodes[long_short + COLOR] = BLACK;
var kid = this.nodes[long_short + long_dir];
if (kid === null) {
this.nodes[long_child + short_dir] = null;
} else {
this.nodes[long_child + short_dir] = kid;
this.nodes[kid + UP] = long_child;
}
this.nodes[long_short + long_dir] = long_child;
this.nodes[long_child + UP] = long_short;
this.nodes[idx + long_dir] = long_short;
this.nodes[long_short + UP] = idx;
long_long = long_child;
long_child = long_short;
}
this.nodes[long_child + COLOR] = this.nodes[idx + COLOR];
this.nodes[idx + COLOR] = BLACK;
this.nodes[long_long + COLOR] = BLACK;
var gramps = this.nodes[idx + UP];
var kid = this.nodes[long_child + short_dir];
if (gramps === null) {
this.root = long_child;
} else {
if (this.nodes[gramps + LEFT] === idx) {
this.nodes[gramps + LEFT] = long_child;
} else {
this.nodes[gramps + RIGHT] = long_child;
}
}
this.nodes[long_child + UP] = gramps;
this.nodes[long_child + short_dir] = idx;
this.nodes[idx + UP] = long_child;
if (kid === null) {
this.nodes[idx + long_dir] = null;
} else {
this.nodes[idx + long_dir] = kid;
this.nodes[kid + UP] = idx;
}
}
};
RBTree.prototype.pop_min_over_x = function (x) {
var best_idx = null;
var best_value;
var idx = this.root;
while (idx !== null) {
var value = this.nodes[idx + VALUE];
if (this.cmp(value, x) > 0) {
best_idx = idx;
best_value = value;
idx = this.nodes[idx + LEFT];
} else {
idx = this.nodes[idx + RIGHT];
}
}
if (best_idx !== null) {
this.remove(best_idx);
}
return best_value;
}
var offset = 20000000000;
function processData(input) {
var lines = input.split('\n');
var n = Number(lines.shift());
var nodes = lines.shift().split(' ');
var counts = nodes.reduce((acc, i) => {
if (acc[i] === undefined) {
acc[i] = 1;
} else {
acc[i]++;
}
return acc;
}, {});
var levels = {};
var max_level = 0;
var uniq_count = 0;
for (var a in counts) {
if (counts.hasOwnProperty(a)) {
let level = counts[a];
if (levels[level] === undefined) {
levels[level] = new RBTree();
levels[level].insert(Number(a));
} else {
levels[level].insert(Number(a));
}
uniq_count++;
if (max_level < level) {
max_level = level;
}
}
}
var level = max_level;
if (uniq_count == n && Math.pow(2, level - 1) == n && nodes.length == (2 * n - 1)) {
var tree = new Array(nodes.length);
var good = true;
var cur_level = levels[level];
tree[0] = cur_level.nodes[cur_level.root + VALUE];
counts[tree[0]]--;
var p = 0;
var i = 1;
while (i < nodes.length) {
var parent = tree[p];
p++;
if (level > counts[parent]) {
level = counts[parent];
cur_level = levels[level];
}
tree[i] = parent;
counts[parent]--;
i++;
var val = cur_level.pop_min_over_x(parent);
if (val === undefined) {
good = false;
break;
} else {
tree[i] = val;
counts[val]--;
i++;
}
}
if (good) {
console.log('YES');
console.log(tree.join(' '));
} else {
console.log('NO');
}
} else {
console.log('NO');
}
}
process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
_input += input;
});
process.stdin.on("end", function () {
processData(_input);
});
Inverse RMQ Python Solution
import sys
from bisect import bisect_right
def z(a, b):
B = sorted(b)
r = []
for i in range(len(a)):
ind = bisect_right(B, a[i])
r += [a[i], B[ind]]
del B[ind]
#print(a, b, r)
return r
n = int(input())
nl = 0
x = n
while x:
nl += 1
x >>= 1
a = list(map(int,input().split()))
occ = {}
for e in a:
if not e in occ:
occ[e] = 0
occ[e] += 1
cnt_occ = {}
for i, v in occ.items():
if not v in cnt_occ:
cnt_occ[v] = 0
cnt_occ[v] += 1
for i in range(1, nl):
if not i in cnt_occ or cnt_occ[i] != (1 << (nl - 1 - i)):
print('NO')
sys.exit(0)
ah = [[] for _ in range(nl + 2)]
for i, v in occ.items():
ah[v].append(i)
sofar = ah[nl]
res = list(sofar)
for i in range(1, nl):
sofar = z(sofar, ah[nl - i])
res += sofar
print('YES')
print(' '.join(map(str,res)))