JavaでPaiza攻略 : 平方分割

平方分割

https://paiza.jp/works/mondai/query_primer/query_primer__square_division
Java初学者ですが、こちらの問題を頑張って解きました。
PythonやCでの解説記事はよく見かけるものの、Javaで攻略している記事をあまり見かけない為、記念に残しておこうと思います。

当初、テスト1と4は通るのに、テスト2と3がランタイムエラーになるため、その原因探しに苦しみました。
ブロックごとの計算におけるforループの記述に問題があったわけですが、
気づくまで大変時間がかかった。

感想

平方分割というアルゴリズムを初めて知ったので、物凄く勉強になりました。
当初、分割しただけじゃ計算量そこまで変わらないのでは〜？と思っておりましたが、
予め計算済みの配列を用意しておくことで、範囲内の計算をスキップ出来るわけですね。

以下、問題なくパスしたコード。

Main.java

import java.util.*;

public class Main{
    int[] array;    //元の配列
    int[] blocks;   //ブロックごとの最大値を格納
    int blockSize;
    
    public Main(int[] array){
        this.array = array;
        blockSize = (int)Math.sqrt(array.length);
        int blockCount = (array.length + blockSize -1)/blockSize;
        blocks = new int[blockCount];
        
        Arrays.fill(blocks, Integer.MIN_VALUE);
        
        //ブロックごとの最大値を計算
        for(int i=0; i<array.length; i++){
            blocks[i/blockSize] = Math.max(blocks[i/blockSize], array[i]);
        }
    }
    
    public int queryMax(int l, int r){
        int block_l = (l-1)/blockSize;
        int block_r = (r-1)/blockSize;
        int max = Integer.MIN_VALUE;
        
        //同じブロックの場合
        if(block_l == block_r){
            for(int i=l-1; i<=r-1; i++){
                max = Math.max(max, array[i]);
            }
        }else{
            //leftブロックを計算
            for(int i=l-1; i<(block_l+1)*blockSize && i<array.length; i++){
                max = Math.max(max, array[i]);
            }
            
            //中間ブロックを計算
            for(int i=block_l+1; i<block_r; i++){
                max = Math.max(max, blocks[i]);
            }
            
            //rightブロックを計算
            for(int i=block_r*blockSize; i<=r-1 && i<array.length; i++){
                max = Math.max(max, array[i]);
            }
        }
        
        return max;
    }
    
    public static void main(String... args){
        Scanner sc = new Scanner(System.in);
        int n = 10000;
        int k = sc.nextInt();
        
        int[] input = new int[n];
        for(int i=0; i<n; i++){
            input[i] = sc.nextInt();
        }
        
        Main m = new Main(input);
        
        for(int i=0; i<k; i++){
            int l = sc.nextInt();
            int r = sc.nextInt();
            System.out.println(m.queryMax(l, r));
        }
        
        sc.close();
    }
}