1068 - School of Killifish

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1068&lang=jp

問題

略

解法

二次元RMQ。
SegmentTreeを入れ子にする。
蟻本を参考にして実装した。
自分はいつもINFを1<<29とかにしているが、今回それだとまずい。
それにしても引数の数・・・。

ソース

const int INF = INT_MAX;

vector<vector<int> > dat;
int R, C;

void update(int r, int c, int a) {
  bool f = 0;
  if (r==0&&c==1) f = 1;
  r += R - 1;
  c += C - 1;
  dat[r][c] = a;
  int cc = c;
  while(cc > 0) {
    cc = (cc-1) / 2;
    dat[r][cc] = min(dat[r][cc*2+1], dat[r][cc*2+2]);
  }
  while(r > 0) {
    r = (r-1) / 2;
    cc = c;
    while(1) {
      dat[r][cc] = min(dat[r*2+1][cc], dat[r*2+2][cc]);
      if (cc == 0) break;
      cc = (cc-1) / 2;
    }
  }
}

int query(int r1, int c1, int r2, int c2, int r, int rl, int rr, int c, int cl, int cr) {
  if (rr<=r1 || r2<=rl || cr<=c1 || c2<=cl) return INF;
  if (r1 <= rl && rr <= r2 && c1 <= cl && cr <= c2) return dat[r][c];
  if (r1 <= rl && rr <= r2) {   // 縦を分割
    int v1 = query(r1,c1,r2,c2,r,rl,rr,c*2+1,cl,(cl+cr)/2);
    int v2 = query(r1,c1,r2,c2,r,rl,rr,c*2+2,(cl+cr)/2, cr);
    return min(v1,v2);
  } else {                      // 横を分割
    int v1 = query(r1,c1,r2,c2,r*2+1,rl,(rl+rr)/2,c,cl,cr);
    int v2 = query(r1,c1,r2,c2,r*2+2,(rl+rr)/2,rr,c,cl,cr);
    return min(v1,v2);
  }
}
int main() {
  int q;
  while(cin >>R>>C>>q, R||C||q) {
    int RR = R, CC = C;
    R = 1; C = 1;
    while(R < RR) R *= 2;
    while(C < CC) C *= 2;
    dat.assign(2*R-1, vector<int>(2*C-1, INF));
    REP(i,RR) REP(j,CC) {
      int a;
      cin >> a;
      update(i,j,a);
    }
    REP(i,q) {
      int r1,c1,r2,c2;
      cin >> r1 >> c1 >> r2 >> c2;
      cout << query(r1,c1,r2+1,c2+1,0,0,R,0,0,C) << endl;
    }
    
  }
}