解法

线段树套线段树模板题，也可以用二维线段树写，但听说很麻烦。
代码

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <string>
#include <queue>
#include <stack>
#include <map>
#include <vector>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug_in  freopen("in.txt","r",stdin)
#define debug_out freopen("out.txt","w",stdout);
#define pb push_back
#define all(x) x.begin(),x.end()
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pii;
const ll maxn = 1e6+10;
const ll maxM = 1e6+10;
const ll inf = 1e8;
const ll inf2 = 1e17;

template<class T>void read(T &x){
    T s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    x = s*w;
}
template<class H, class... T> void read(H& h, T&... t) {
    read(h);
    read(t...);
}

template <typename ... T>
void DummyWrapper(T... t){}

template <class T>
T unpacker(const T& t){
    cout<<' '<<t;
    return t;
}
template <typename T, typename... Args>
void pt(const T& t, const Args& ... data){
    cout << t;
    DummyWrapper(unpacker(data)...);
    cout << '\n';
}

//--------------------------------------------

int M;
struct seg
{
    #define lson u<<1
    #define rson u<<1|1

    struct sub_node{
        int l,r,mx;
    };
    struct node{
        int l,r;
        sub_node sub_tr[1010*4];
    }tr[210*4];

    void build_sub(int l,int r,int id,int u = 1){
        tr[id].sub_tr[u] = {l,r,-1};
        if(l == r) return ;
        int mid = (l+r)>>1;
        build_sub(l,mid,id,lson);
        build_sub(mid+1,r,id,rson);
    }
    void build(int l,int r,int sl,int sr,int u = 1){
        tr[u] = {l,r};
        build_sub(sl,sr,u);
        if(l == r) return ;
        int mid = (l+r)>>1;
        build(l,mid,sl,sr,lson);
        build(mid+1,r,sl,sr,rson);
    }
    void pushup_sub(int id,int u){
        tr[id].sub_tr[u].mx = max(tr[id].sub_tr[lson].mx , tr[id].sub_tr[rson].mx);
    }
    void modify_sub(int idx,int v,int id,int u = 1){
        sub_node &tr2 = tr[id].sub_tr[u];
        if(tr2.l == idx && tr2.r == idx){
            tr2.mx =  max(tr2.mx,v);
            return ;
        }else{
            int mid = (tr2.l + tr2.r)>>1;
            if(idx<=mid) modify_sub(idx,v,id,lson);
            else modify_sub(idx,v,id,rson);
            pushup_sub(id,u);
        }
    }
    void modify(int idx1,int idx2,int v,int u = 1){
        modify_sub(idx2,v,u);
        if(tr[u].l == tr[u].r) return ;
        int mid = (tr[u].l + tr[u].r)>>1;
        if(idx1 <= mid) modify(idx1,idx2,v,lson);
        else modify(idx1,idx2,v,rson);
    }
    int query_sub(int l,int r,int id,int u = 1){
        sub_node &tr2 = tr[id].sub_tr[u];
        if(l<= tr2.l && tr2.r <= r){
            return tr[id].sub_tr[u].mx;
        }else{
            int mid = (tr2.l + tr2.r)>>1;
            if(r<= mid) return query_sub(l,r,id,lson);
            else if(l > mid) return query_sub(l,r,id,rson);
            else return max(query_sub(l,r,id,lson),query_sub(l,r,id,rson));
        }
    }

    int query(int l,int r,int sl,int sr,int u = 1){
        if(l<= tr[u].l && tr[u].r <= r){
            return query_sub(sl,sr,u);
        }else{
            int mid = (tr[u].l + tr[u].r)>>1;
            if(r<=mid) return query(l,r,sl,sr,lson);
            else if(l>mid) return query(l,r,sl,sr,rson);
            else return max(query(l,r,sl,sr,lson), query(l,r,sl,sr,rson));
        }
    }
}seg;
int main(){
   // debug_in;

    while(scanf("%d",&M)){
        if(M == 0) break;
        seg.build(100,200,0,1000);
        for(int i = 1;i<=M;i++){
            char op;scanf(" %c",&op);
            if(op == 'I'){
                int h;double a,b;
                read(h);
                scanf("%lf %lf",&a,&b);
                seg.modify(h,int(a*10),int(b*10));
            }else{
                int h1,h2;double l,r;
                read(h1,h2);
                scanf("%lf %lf",&l,&r);
                if(h1 > h2) swap(h1,h2);
                if(l > r) swap(l,r);
                int ans = seg.query(h1,h2,int(l*10),int(r*10));
                if(ans == -1) puts("-1");
                else printf("%.1f\n",(double)ans/10);
            }
        }
    }



    return 0;
}
Luck and Love HDU - 1823 【线段树套线段树】【模板】

解法

代码
