Range Minimum Query

問題文
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_A

Range Minimum Queryを平方分割で解いた。

#include<iostream>
#include<algorithm>
#include<vector>
#include<climits>

#define max_n 100000

using namespace std;

typedef long long ll;

const ll B=1000;

ll a[max_n],m[max_n/B];

void update(ll i,ll x){
  a[i]=x;
  m[i/B]=INT_MAX;
  for(int j=i-i%B;j<i-i%B+B;j++)
    m[i/B]=min(m[i/B],a[j]);
}

ll find(ll s,ll t){
  ll res=INT_MAX;

  for(int i=s/B+1;i<t/B;i++){
    res=min(res,m[i]);
  }
  
  for(int i=s;i<min(s-s%B+B,t+1);i++)res=min(res,a[i]);
  for(int i=max(s,t-t%B);i<=t;i++)res=min(res,a[i]);

  return res;
}

int main(void){
  int n,q;

  cin >> n >> q;

  fill(m,m+max_n/B,INT_MAX);
  fill(a,a+max_n,INT_MAX);

  ll com,x,y;
  for(int i=0;i<q;i++){
    cin >> com >> x >> y;
    
    if(com==0)update(x,y);
    else cout << find(x,y) << endl;
  }
  
  return 0;
}