Bitset with get segment FULL

https://official.contest.yandex.ru/opencupXIX/contest/10686 Problem C.Array


package net.egork;

import net.egork.io.InputReader;
import net.egork.io.OutputWriter;

import java.util.Arrays;
import java.util.Random;

import static java.lang.Math.min;
import static java.util.Arrays.copyOfRange;
import static java.util.Arrays.sort;

public class TaskAFuckingArray {
    public void solve(int testNumber, InputReader in, OutputWriter out) {
        if (false) new Tester().test();
        int n = in.readInt();
        int[] a = in.readIntArray(n);
        int answer = new Solver().solve(a);
        out.print(answer);
    }

    class Tester {
        Random rnd = new Random(239);

        void test() {
            for (int t = 0; ; t++) {
                int n = 6;
                int[] a = new int[n];
                for (int i = 0; i < n; i++) a[i] = 2 + rnd.nextInt(200);
                int nai = new Naive().solve(a.clone());
                int sol = new Solver().solve(a.clone());
                if (nai != sol) {
                    System.err.println(Arrays.toString(a));
                    System.err.println(nai);
                    System.err.println(sol);
                    System.err.println(t);
                }
            }
        }
    }

    class Naive {
        int solve(int[] a) {
            n = a.length;
            this.a = a;
            used = new boolean[n];
            maxAnswer = 0;
            for (int i = 0; i < n; i++) {
                used[i] = true;
                dfs(1, a[i]);
                used[i] = false;
            }
            return maxAnswer;
        }

        int n;
        int[] a;
        boolean[] used;
        int maxAnswer;
        void dfs(int at, int answer) {
            if (at == n) {
                if (maxAnswer < answer) {
                    maxAnswer = answer;
                }
                return;
            }
            for (int i = 0; i < n; i++) {
                if (!used[i]) {
                    used[i] = true;
                    dfs(at + 1, answer % a[i]);
                    used[i] = false;
                }
            }
        }
    }

    class Solver {
        int solve(int[] a) {
            int n = a.length;
            sort(a);

            if (a[0] < a[1]) {
                return a[0];
            }

            int n1 = 1;
            for (int i = 1; i < n; i++) {
                if (a[i] != a[i - 1]) {
                    a[n1++] = a[i];
                }
            }
            n = n1;
            a = copyOfRange(a, 0, n1);

            MyBitset answer = new MyBitset(a[n - 1] + 1);
            answer.set(a[n - 1]);
            answer.set(0);
            for (int i = n - 2; i >= 0; i--) {
                for (int j = a[i]; j <= a[n - 1]; j += a[i]) {
                    int k = min(j + a[i] - 1, a[n - 1]);
                    MyBitset sub = answer.get(j, k);
                    answer.makeOr(sub);
                }
                answer.set(a[i]);
            }

            for (int i = a[0] - 1; ; i--) {
                if (answer.get(i)) {
                    return i;
                }
            }
        }
    }

    int type_size_bits = 6;
    int type_size = 1 << type_size_bits;
    int last_bits = (1 << type_size_bits) - 1;

    class MyBitset {
        long[] a;
        int bucketCount;

        MyBitset(int size) {
            if ((size & last_bits) != 0) size += last_bits;
            bucketCount = size >> type_size_bits;
            a = new long[bucketCount];
        }

        void set(int at) {
            a[at >> type_size_bits] |= 1L << (at & last_bits);
        }

        boolean get(int at) {
            long res = a[at >> type_size_bits] & (1L << (at & last_bits));
            return res != 0;
        }

        MyBitset get(int l, int r) {
            int size = r - l + 1;
            MyBitset res = new MyBitset(size);

            int startBucket = l >> type_size_bits;
            int endBucket = r >> type_size_bits;
            if (startBucket == endBucket) {
                for (int i = l; i <= r; i++) {
                    if (get(i)) {
                        res.set(i - l);
                    }
                }
                return res;
            }

            int cut_bits = 0;
            if ((l & last_bits) != 0) {
                for (int i = l; (i & last_bits) != 0; i++) {
                    if (get(i)) {
                        res.set(i - l);
                    }
                    cut_bits++;
                }
                startBucket++;
            }
            if ((r & last_bits) != last_bits) {
                for (int i = r; (i & last_bits) != last_bits; i--) {
                    if (get(i)) {
                        res.set(i - l);
                    }
                }
                endBucket--;
            }
            for (int i = startBucket; i <= endBucket; i++) {
                int bucket0 = i - startBucket;
                long cur = a[i];
                if (cut_bits == 0) {
                    res.a[bucket0] = cur;
                    continue;
                }
                long head = cur & ((1L << (type_size - cut_bits)) - 1);
                long tail = cur ^ head;
                res.a[bucket0] |= head << cut_bits;
                res.a[bucket0 + 1] |= tail >>> (type_size - cut_bits);
            }

            return res;
        }

        void makeOr(MyBitset other) {
            for (int i = 0; i < other.bucketCount; i++) {
                a[i] |= other.a[i];
            }
        }

        @Override
        public String toString() {
            String s = "";
            for (int i = 0; i < bucketCount; i++) {
                for (int j = 0; j < type_size; j++) {
                    if (((a[i] >> j) & 1) == 1) {
                        s += (i * type_size + j) + " ";
                    }
                }
            }
            return s;
        }
    }
}