平方分割。要バグチェック

sqdiv.cpp

/*
  平方分割
  こちらのスライドを参照しながら作成
  http://www.slideshare.net/iwiwi/ss-3578491
  
  簡単なテストケースしか見ていないので、バグがあるかも
  
  n個のクエリが与えられるので、高速に処理したい。
  クエリはクエリタイプ・prm1・prm2から構成される。
  クエリタイプ 0 => a[prm1]=prm2
               1 => a[prm1..prm2] から最小の値を求める。
*/ 

#include<bits/stdc++.h>

using namespace std;


int sqdata[16]; // データ数16
int sqbacket[4];// sqrt(16)

// a[idx] = valの処理を行う。
void sqdiv_set(int idx,int val){
    sqdata[idx]=val; // 普通に値を入れる。
    int l = idx/4*4;
    int smallest = sqdata[l];
    for (int i=1;i<4;i++){
        if (sqdata[l+i] < smallest) 
            smallest = sqdata[l+i];
    }
    sqbacket[l/4] = smallest;
}

// a[l..h] から最小値を取得する
int sqdiv_get(int l,int h){
    int sql = (l+3)/4*4;
    int sqh = (h+1)/4*4;
    int smallest = sqdata[l];
    int i;
    // backetから溢れた部分(左)
    for (i=l;i<sql&&i<=h;i++){
        if (sqdata[i] < smallest) 
            smallest = sqdata[i];
    }
    if (sql>sqh) return smallest;
    // backetで纏められる部分
    for (i=sql/4;i<sqh/4;i++){
        if (sqbacket[i] < smallest) 
            smallest = sqbacket[i];
    }
    // backetから溢れた部分(右)
    for (i=sqh;i<=h;i++){
        if (sqdata[i] < smallest)
            smallest = sqdata[i];
    }
    return smallest;
}

int main(){
    int i,j,t,p1,p2;
    int n;
    
    // 初期化(適当。99で埋めておく)
    fill(sqdata,sqdata+16,99);
    fill(sqbacket,sqbacket+4,99);
    
    // クエリ数読み込み
    cin >> n;
    
    for (i=0;i<n;i++){
        cin >> t >> p1 >> p2;
        if (t == 0){
            // SET QUERY
            sqdiv_set(p1,p2);
        }else if (t==1){
            // GET QUERY
            printf("range[%3d..%3d] . min => %3d\n",p1,p2,sqdiv_get(p1,p2));
        }else if (t==2){
            for (j=0;j<10;j++){
                printf("%3d",sqdata[j]);
            }
            cout<<endl;
        }
    }
    return 0;
}