import java.util.Arrays;

public class SQRTDecomposition<E> {

    private E[] data, blocks;
    private final int N;
    private int B;
    private int Bn;
    private final Merger<E> merger;

    public SQRTDecomposition(E[] nums, Merger<E> merger) {
        this.merger = merger;
        N = nums.length;
        if (N == 0) {
            return;
        }
        B = (int) Math.sqrt(nums.length);
        Bn = N / B + (N % B > 0 ? 1 : 0);
        data = Arrays.copyOf(nums, N);
        blocks = (E[]) new Object[Bn];
        for (int i = 0; i < N; i++) {
            if (blocks[i / B] == null) {
                blocks[i / B] = nums[i];
            } else {
                blocks[i / B] = merger.merge(blocks[i / B], nums[i]);
            }
        }
    }

    public E sqrt(int l, int r) {
        if (l < 0 || l >= N || r < 0 || r >= N || l > r) {
            return null;
        }
        int bStart = l / B, bEnd = r / B;
        E res = null;
        //如果 l r在同一组 但是 l不在最左侧或者r不在最右侧 
        if (bStart == bEnd && (l % B != 0 || (r + 1) % B != 0)) {
            for (int i = l; i <= r; i++) {
                if (res == null) {
                    res = data[i];
                } else {
                    res = merger.merge(res, data[i]);
                }
            }
            return res;
        }
        //l和r在同一组 l在最左侧 r 在左右侧 直接取值
        if (bStart == bEnd) {
            res = blocks[bStart];
            return res;
        }
        boolean flag = true;
        // l 和 r不在同一组 并且 l不在最左侧
        if (l % B != 0) {
            for (int i = l; i < (bStart + 1) * B; i++) {
                if (res == null) {
                    res = data[i];
                } else {
                    res = merger.merge(res, data[i]);
                }
            }
            flag = false;
        }
        //l 和 r不在同一组 并且 r不在最右侧
        if ((r + 1) % B != 0) {
            for (int i = bEnd * B; i <= r; i++) {
                if (res == null) {
                    res = data[i];
                } else {
                    res = merger.merge(res, data[i]);
                }

            }
            flag = false;
        }
        if (flag) {
            //进入此循环说明 l r不在同一组但是 l 在最左侧 r 在最右侧 直接从blocks中取值
            for (int b = bStart; b <= bEnd; b++) {
                if (res == null) {
                    res = blocks[b];
                } else {
                    res = merger.merge(res, blocks[b]);
                }
            }
        } else {
            //反之正常取值
            for (int b = bStart + 1; b < bEnd; b++) {
                if (res == null) {
                    res = blocks[b];
                } else {
                    res = merger.merge(res, blocks[b]);
                }
            }
        }
        return res;
    }
}