二维线段树，用的树套树，在第一维每个节点上再建一个线段树，代码量加倍。
code:
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <iomanip>
#include <bitset>
#include <list>
#include <ctime>
using namespace std ;
#define SET(arr, what) memset(arr, what, sizeof(arr))
#define FF(i, a) for(i=0; i<a; i++)
#define SD(a) scanf("%d", &a)
#define SSD(a, b) scanf("%d%d", &a, &b)
#define SF(a) scanf("%lf", &a)
#define SS(a) scanf("%s", a)
#define SLD(a) scanf("%lld", &a)
#define PF(a) printf("%d\n", a)
#define PPF(a, b) printf("%d %d\n", a, b)
#define SZ(arr) (int)a.size()
#define SWAP(a,b) a=a xor b;b= a xor b;a=a xor b;
#define read freopen("in.txt", "r", stdin)
#define write freopen("out.txt", "w", stdout)
#define MAX 1<<30
#define ESP 1e-5
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
template<class T> inline T sqr(T a){return a*a;}
template<class T> inline void AMin(T &a,T b){if(a>b)a=b;}
template<class T> inline void AMax(T &a,T b){if(a<b)a=b;}
template<class T> inline T Min(T a,T b){return a>b?b:a;}
template<class T> inline T Max(T a,T b){return a>b?a:b;}
const int maxn = 50010 ;
struct sub_seg{
int l, r, v ;
} ;
struct seg{
int l, r ;
sub_seg st[1010<<2] ;
}tt[110<<2] ;
void sub_build(sub_seg st[], int l, int r, int rt){
st[rt].l = l, st[rt].r = r ;
st[rt].v = -1 ;
if(l==r) return ;
int m = (l + r) >> 1 ;
sub_build(st, lson) ;
sub_build(st, rson) ;
}
void build(int l, int r, int rt){
sub_build(tt[rt].st, 1, 1000, 1) ;
tt[rt].l = l, tt[rt].r = r ;
if(l==r) return ;
int m = (l + r) >> 1 ;
build(lson) ;
build(rson) ;
}
void sub_update(sub_seg st[], int a, int l, int rt){
if(st[rt].l==st[rt].r){
st[rt].v = Max(st[rt].v, l) ;
return ;
}
int m = (st[rt].l + st[rt].r) >> 1 ;
if(a<=m) sub_update(st, a, l, rt<<1) ;
else sub_update(st, a, l, rt<<1|1) ;
st[rt].v = Max(st[rt<<1].v, st[rt<<1|1].v) ;
}
void update(int h, int a, int l, int rt){
sub_update(tt[rt].st, a, l, 1) ;
if(tt[rt].r==tt[rt].l) return ;
int m = (tt[rt].l + tt[rt].r) >> 1 ;
if(h<=m) update(h, a, l, rt<<1) ;
else update(h, a, l, rt<<1|1) ;
}
int sub_query(sub_seg st[], int l, int r, int rt){
if(l<=st[rt].l&&r>=st[rt].r)
return st[rt].v ;
int m = (st[rt].l + st[rt].r) >> 1 ;
int ret = -1 ;
if(l<=m) ret = Max(ret, sub_query(st, l, r, rt<<1)) ;
if(r>m) ret = Max(ret, sub_query(st, l, r, rt<<1|1)) ;
return ret ;
}
int query(int l, int r, int rt, int l1, int r1){
if(l<=tt[rt].l&&tt[rt].r<=r)
return sub_query(tt[rt].st, l1, r1, 1) ;
int m = (tt[rt].l+tt[rt].r) >> 1 ;
int ret = -1 ;
if(l<=m) ret = Max(ret, query(l, r, rt<<1, l1, r1)) ;
if(m<r) ret = Max(ret, query(l, r, rt<<1|1, l1, r1)) ;
return ret ;
}
int main(){
int n, i, j, h1, h2, ans ;
double a1, a2, l ;
char c ;
while(SD(n)&&n){
build(100, 200, 1) ;
while(n--){
getchar() ;
c = getchar() ;
if(c=='I'){
SD(h1) ;scanf("%lf%lf", &a1, &l) ;
update(h1, (int)(a1*10.0), (int)(l*10.0), 1) ;
}
else{
SSD(h1, h2) ;scanf("%lf%lf", &a1, &a2) ;
if(h1>h2) swap(h1, h2) ;
if(a1>a2) swap(a1, a2) ;
ans = query(h1, h2, 1, (int)(a1*10.0), (int)(a2*10.0)) ;
if(ans<0) PF(-1) ;
else printf("%.1lf\n", (double)ans/10.0) ;
}
}
}
return 0 ;}