package ru.ifmo.nds.util;

import ru.ifmo.nds.util.veb.VanEmdeBoasSet;

public class VanEmdeBoasRankQueryStructure extends RankQueryStructure {
    private final VanEmdeBoasRangeHandle theOnlyHandle;

    public VanEmdeBoasRankQueryStructure(int maximumPoints) {
        theOnlyHandle = new VanEmdeBoasRangeHandle(maximumPoints);
    }

    @Override
    public RangeHandle createHandle(int storageStart, int from, int until, int[] indices, int[] keys) {
        theOnlyHandle.clear();
        return theOnlyHandle;
    }

    private static class VanEmdeBoasRangeHandle extends RangeHandle {
        private final VanEmdeBoasSet set;
        private final int[] values;

        VanEmdeBoasRangeHandle(int maximumPoints) {
            int scale = 0;
            while (maximumPoints > 1 << scale) {
                ++scale;
            }
            set = VanEmdeBoasSet.create(scale);
            values = new int[maximumPoints];
        }

        void clear() {
            set.clear();
        }

        @Override
        public RangeHandle put(int key, int value) {
            set.setEnsuringMonotonicity(key, 0, value, values);
            return this;
        }

        @Override
        public int getMaximumWithKeyAtMost(int key, int minimumMeaningfulAnswer) {
            key = set.prevInclusively(key);
            return key == -1 ? -1 : values[key];
        }
    }
}

@@ -155,39 +155,36 @@
 e final 
-VanEmdeBoasRa
+EmptyOrSi
 ng
+l
 eHandle 
 theOnlyH
@@ -175,23 +175,21 @@
 eHandle 
-theOnly
+small
 Handle;%0A
@@ -255,31 +255,50 @@
 ) %7B%0A        
-theOnly
+VanEmdeBoasRangeHandle big
 Handle = new
@@ -333,24 +333,82 @@
 mumPoints);%0A
+        smallHandle = new EmptyOrSingleHandle(bigHandle);%0A
     %7D%0A%0A    @
@@ -532,60 +532,1448 @@
     
-theOnlyHandle.clear();%0A        return theOnlyHandle;
+smallHandle.clear();%0A        return smallHandle;%0A    %7D%0A%0A    private static class EmptyOrSingleHandle extends RangeHandle %7B%0A        private final VanEmdeBoasRangeHandle forTwoOrMore;%0A        private int key = Integer.MAX_VALUE, value = Integer.MIN_VALUE;%0A%0A        private EmptyOrSingleHandle(VanEmdeBoasRangeHandle forTwoOrMore) %7B%0A            this.forTwoOrMore = forTwoOrMore;%0A        %7D%0A%0A        @Override%0A        public RangeHandle put(int key, int value) %7B%0A            if (key %3C this.key) %7B%0A                if (value %3C this.value) %7B%0A                    forTwoOrMore.put(this.key, this.value);%0A                    return forTwoOrMore.put(key, value);%0A                %7D%0A                this.key = key;%0A                this.value = value;%0A            %7D else if (key == this.key) %7B%0A                if (this.value %3C value) %7B%0A                    this.value = value;%0A                %7D%0A            %7D else %7B%0A                if (value %3E this.value) %7B%0A                    forTwoOrMore.put(this.key, this.value);%0A                    return forTwoOrMore.put(key, value);%0A                %7D%0A            %7D%0A            return this;%0A        %7D%0A%0A        @Override%0A        public int getMaximumWithKeyAtMost(int key, int minimumMeaningfulAnswer) %7B%0A            return key %3E= this.key ? value : -1;%0A        %7D%0A%0A        void clear() %7B%0A            forTwoOrMore.clear();%0A            this.key = Integer.MAX_VALUE;%0A            this.value = Integer.MIN_VALUE;%0A        %7D
 %0A   

Isolate a single-element case on the range handle level.