2012-12-01 12:18:25Morris
[ZJ][2DST][zkw] d800. ST版 区间MAX
內容 ：
給一個矩陣T(1,1),T(1,2),....T(N,M)
求T(x1,y1) 到T(x2,y2)的最大值
矩形中的最大元素
輸入說明
：
每組測資輸入的第一行有兩個整數N,M (1≦N,M≦500) ，
接下來會有N行，每行上會有M個代表T(N,M) (0≦T(N,M) ≦2147483647)
再接下來會有一個整數Q(1≦Q≦1000000)，
代表接下來會有Q行詢問的x1,y1,x2,y2(1≦x1≦x2≦N,1≦y1≦y2≦M)。
輸出說明
：
輸出T(x1,y1) 到T(x2,y2)的最大值
範例輸入
：
5 6 7 4 3 7 5 1 3 4 7 1 1 6 0 1 8 3 2 5 1 5 9 5 1 5 8 2 6 6 4 5 10 2 4 5 5 1 4 5 5 1 2 3 5 4 2 5 3 4 4 5 5 2 1 5 4 3 4 5 5 2 2 4 2 2 2 2 5 4 3 4 4
範例輸出 ：
6 7 8 9 6 9 6 5 7 9
提示
：
背景知識：
RMQ ST
segment tree
AC 得了 d798 的程序不一定 AC 得了 d800；
AC 得了 d800 的程序不一定 AC 得了 d798。
也就是说d798和d800不是简单的重复！
出處
：
#include <stdio.h>
#include <string.h>
#define max(x, y) ((x) > (y) ? (x) : (y))
#define min(x, y) ((x) < (y) ? (x) : (y))
struct subTree {
int maxv;
};
struct segmentTree {
subTree subtree[1025];
} mainTree[1025];
int Mmain, Msub;
void subbuild(int k) {
int i;
for(i = 2*Msub-1; i > 0; i--) {
mainTree[k].subtree[i].maxv = 0;
}
}
void build() {
int i;
for(i = 2*Mmain; i > 0; i--) {
subbuild(i);
}
}
void submodify(int k, int y) {
static int s;
for(s = y+Msub; s > 0; s >>= 1) {
mainTree[k].subtree[s].maxv = max(mainTree[k<<1].subtree[s].maxv, mainTree[k<<1|1].subtree[s].maxv);
}
}
void modify(int x, int y, int v) {
static int s, t;
mainTree[x+Mmain].subtree[y+Msub].maxv = v;
t = x+Mmain;
for(s = (y+Msub)>>1; s > 0; s >>= 1) {
mainTree[t].subtree[s].maxv = max(mainTree[t].subtree[s<<1].maxv, mainTree[t].subtree[s<<1|1].maxv);
}
for(s = (x+Mmain)>>1; s > 0; s >>= 1) {
submodify(s, y);
}
}
int ansMax;
void subquery(int k, int lc, int rc) {
static int s, t;
for(s = lc+Msub-1, t = rc+Msub+1; (s^t) != 1;) {
if(~s&1) {
ansMax = max(ansMax, mainTree[k].subtree[s^1].maxv);
}
if(t&1) {
ansMax = max(ansMax, mainTree[k].subtree[t^1].maxv);
}
s >>= 1, t >>= 1;
}
}
void query(int lr, int rr, int lc, int rc) {
static int s, t;
for(s = lr+Mmain-1, t = rr+Mmain+1; (s^t) != 1;) {
if(~s&1) {
subquery(s^1, lc, rc);
}
if(t&1) {
subquery(t^1, lc, rc);
}
s >>= 1, t >>= 1;
}
}
inline int ReadInt(int *x) {
static char c, neg;
while((c = getchar()) < '-') {if(c == EOF) return EOF;}
neg = (c == '-') ? -1 : 1;
*x = (neg == 1) ? c-'0' : 0;
while((c = getchar()) >= '0')
*x = (*x << 3) + (*x << 1) + c-'0';
*x *= neg;
return 1;
}
int main() {
int n, m, q, x, y, v;
int i, j, x1, x2, y1, y2;
while(scanf("%d %d", &n, &m) == 2) {
for(Mmain = 1; Mmain < n+2; Mmain <<= 1);
for(Msub = 1; Msub < m+2; Msub <<= 1);
build();
for(i = 1; i <= n; i++) {
for(j = 1; j <= m; j++) {
ReadInt(&x);
modify(i, j, x);
}
}
scanf("%d", &q);
getchar();
char cmd;
while(q--) {
ReadInt(&x1), ReadInt(&y1), ReadInt(&x2), ReadInt(&y2);
ansMax = 0;
query(x1, x2, y1, y2);
printf("%d\n", ansMax);
}
}
return 0;
}