hdu1823（二维线段树模板题）

朴灿烈づ我的快乐病毒、 2021-12-23 07:43 268阅读 0赞

## [hdu1823][] ##

### 题意 ###

单点更新，求二维区间最值。

### 分析 ###

二维线段树模板题。  
二维线段树实际上就是树套树，即每个结点都要再建一颗线段树，维护对应的信息。  
一般一维线段树是切割某一可变区间直到满足所要查询区间，求最值、求和等，二维就是先切割第一维的区间，再去切割第二维的区间。

### code ###

#include<bits/stdc++.h>
    using namespace std;
    #define lson l, m, rt << 1
    #define rson m + 1, r, rt << 1 | 1
    int n, s[1005][4005];
    void subBuild(int xrt, int l, int r, int rt) {
        s[xrt][rt] = -1;
        if(l != r) {
            int m = l + r >> 1;
            subBuild(xrt, lson);
            subBuild(xrt, rson);
        }
    }
    void build(int l, int r, int rt) {
        subBuild(rt, 0, n, 1);
        if(l != r) {
            int m = l + r >> 1;
            build(lson);
            build(rson);
        }
    }
    void subUpdate(int xrt, int y, int c, int l, int r, int rt) {
        if(l == r && l == y) s[xrt][rt] = max(s[xrt][rt], c);
        else {
            int m = l + r >> 1;
            if(y <= m) subUpdate(xrt, y, c, lson);
            else subUpdate(xrt, y, c, rson);
            s[xrt][rt] = max(s[xrt][rt << 1], s[xrt][rt << 1 | 1]);
        }
    }
    void update(int x, int y, int c, int l, int r, int rt) {
        subUpdate(rt, y, c, 0, n, 1);
        if(l != r) {
            int m = l + r >> 1;
            if(x <= m) update(x, y, c, lson);
            else update(x, y, c, rson);
        }
    }
    int subQuery(int xrt, int yl, int yr, int l, int r, int rt) {
        if(yl <= l && r <= yr) return s[xrt][rt];
        else {
            int m = l + r >> 1;
            int res = -1;
            if(yl <= m) res = subQuery(xrt, yl, yr, lson);
            if(yr > m) res = max(res, subQuery(xrt, yl, yr, rson));
            return res;
        }
    }
    int query(int xl, int xr, int yl, int yr, int l, int r, int rt) {
        if(xl <= l && r <= xr) return subQuery(rt, yl, yr, 0, n, 1);
        else {
            int m = l + r >> 1;
            int res = -1;
            if(xl <= m) res = query(xl, xr, yl, yr, lson);
            if(xr > m) res = max(res, query(xl, xr, yl, yr, rson));
            return res;
        }
    }
    int main() {
        int t;
        while(scanf("%d", &t) && t) {
            n = 1000;
            build(100, 200, 1);
            while(t--) {
                char ch[2];
                int a, b;
                double c, d;
                scanf("%s", ch);
                if(ch[0] == 'I') {
                    scanf("%d%lf%lf", &a, &c, &d);
                    update(a, c * 10, d * 10, 100, 200, 1);
                } else {
                    scanf("%d%d%lf%lf", &a, &b, &c, &d);
                    int cc = c * 10, dd = d * 10;
                    if(a > b) swap(a, b);
                    if(cc > dd) swap(cc, dd);
                    int ans = query(a, b, cc, dd, 100, 200, 1);
                    if(ans == -1) printf("-1\n");
                    else printf("%.1f\n", ans / 10.0);
                }
            }
        }
        return 0;
    }

转载于:https://www.cnblogs.com/ftae/p/7739512.html

[hdu1823]: https://vjudge.net/problem/HDU-1823