Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

[UVA] 11297 - Census

#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, minv;
};
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;
        mainTree[k].subtree[i].minv = 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);
        mainTree[k].subtree[s].minv = min(mainTree[k<<1].subtree[s].minv, mainTree[k<<1|1].subtree[s].minv);
    }
}
void modify(int x, int y, int v) {
    static int s, t;
    mainTree[x+Mmain].subtree[y+Msub].maxv = v;
    mainTree[x+Mmain].subtree[y+Msub].minv = 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);
        mainTree[t].subtree[s].minv = min(mainTree[t].subtree[s<<1].minv, mainTree[t].subtree[s<<1|1].minv);
    }
    for(s = (x+Mmain)>>1; s > 0; s >>= 1) {
        submodify(s, y);
    }
}
int ansMax, ansMin;
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);
            ansMin = min(ansMin, mainTree[k].subtree[s^1].minv);
        }
        if(t&1) {
            ansMax = max(ansMax, mainTree[k].subtree[t^1].maxv);
            ansMin = min(ansMin, mainTree[k].subtree[t^1].minv);
        }
        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--) {
            cmd = getchar();
            if(cmd == 'q') {
                ReadInt(&x1), ReadInt(&y1), ReadInt(&x2), ReadInt(&y2);
                ansMax = 0, ansMin = 0xfffffff;
                query(x1, x2, y1, y2);
                printf("%d %d\n", ansMax, ansMin);
            } else {
                ReadInt(&x), ReadInt(&y), ReadInt(&v);
                modify(x, y, v);
            }
        }
    }
    return 0;
}