Luck and Love
Time Limit: 10000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5282 Accepted Submission(s): 1324
Input
本题有多个测试数据，第一个数字M，表示接下来有连续的M个操作，当M＝0时处理中止。
接下来是一个操作符C。
当操作符为‘I’时，表示有一个MM报名，后面接着一个整数，H表示身高，两个浮点数，A表示活泼度，L表示缘分值。 （100<=H<=200， 0.0<=A，L<=100.0）
当操作符为‘Q’时，后面接着四个浮点数，H1，H2表示身高区间，A1，A2表示活泼度区间，输出符合身高和活泼度要求的MM中的缘分最高值。 （100<=H1，H2<=200， 0.0<=A1，A2<=100.0）
所有输入的浮点数，均只有一位小数。
Output
对于每一次询问操作，在一行里面输出缘分最高值，保留一位小数。
对查找不到的询问，输出-1。
Sample Input
8
I 160 50.5 60.0
I 165 30.0 80.5
I 166 10.0 50.0
I 170 80.5 77.5
Q 150 166 10.0 60.0
Q 166 177 10.0 50.0
I 166 40.0 99.9
Q 166 177 10.0 50.0
0
Sample Output
80.5
50.0
99.9
二维线段树
两种板子（都是C++ AC, G++ WA 。。。。。）
#include <cstdio>
#include <algorithm>
using namespace std;
#define lson (o<<1)
#define rson ((o<<1)|1)
const int maxh = 100 + 10;
const int maxa = 1000 + 10;
int mmax[maxh<<2][maxa<<2];
void build_A(int O, int o, int L, int R) { //活泼度建树
mmax[O][o] = -1;
if(L == R) return;
int M = (L + R) >> 1;
build_A(O, lson, L, M);
build_A(O, rson, M+1, R);
}
void build_H(int o, int L, int R) { //身高建树
build_A(o, 1, 0, 1000);
if(L == R) return;
int M = (L + R) >> 1;
build_H(lson, L, M);
build_H(rson, M+1, R);
}
void Insert_A(int O, int o, int L, int R, int A, int D) { //根据活泼度建树
if(L == R) {
mmax[O][o] = max(mmax[O][o], D);
return;
}
int M = (L + R) >> 1;
if(A <= M) Insert_A(O, lson, L, M, A, D);
else Insert_A(O, rson, M+1, R, A, D);
mmax[O][o] = max(mmax[O][lson], mmax[O][rson]);
}
void Insert(int o, int L, int R, int H, int A, int D) {
Insert_A(o, 1, 0, 1000, A, D);
if(L == R) return;
int M = (L + R) >> 1;
if(H <= M) Insert(lson, L, M, H, A, D);
else Insert(rson, M+1, R, H, A, D);
}
int query_A(int O, int o, int L, int R, int A1, int A2) { //根据活泼度查询
if(A1 <= L && R <= A2) return mmax[O][o];
int M = (L + R) >> 1;
int Max1 = -1, Max2 = -1;
if(A1 <= M) Max1 = query_A(O, lson, L, M, A1, A2);
if(A2 > M) Max2 = query_A(O, rson, M+1, R, A1, A2);
return (Max1 > Max2) ? Max1 : Max2;
}
int query(int o, int L, int R, int H1, int H2, int A1, int A2) {
if(H1 <= L && R <= H2) return query_A(o, 1, 0, 1000, A1, A2);
int M = (L + R) >> 1;
int Max1 = -1, Max2 = -1;
if(H1 <= M) Max1 = query(lson, L, M, H1, H2, A1, A2);
if(H2 > M) Max2 = query(rson, M+1, R, H1, H2, A1, A2);
return (Max1 > Max2) ? Max1 : Max2;
}
int main() {
int M;
char op;
while(scanf("%d", &M) == 1 && M) {
build_H(1, 100, 200);
for(int i = 0; i < M; i++) {
getchar();
op = getchar();
if(op == 'I') {
int H, A, D;
double AA, DD;
scanf("%d%lf%lf", &H, &AA, &DD);
A = (int)(AA * 10);
D = (int)(DD * 10);
Insert(1, 100, 200, H, A, D);
} else {
int H1, H2, A1, A2;
double AA, BB;
scanf("%d%d%lf%lf", &H1, &H2, &AA, &BB);
A1 = (int)(AA * 10);
A2 = (int)(BB * 10);
if(A1 > A2) swap(A1, A2);
if(H1 > H2) swap(H1, H2);
int ret = query(1, 100, 200, H1, H2, A1, A2);
ret != -1 ? printf("%.1f\n", ret/10.0) : puts("-1");
}
}
}
return 0;
}
#include<cstdio>
#include<cstring>
#include<algorithm>
#define lson rt<<1
#define rson lson|1
using namespace std;
const int inf = 0x3f;
const int N = 200;
const int M = 1000;
double ans;
struct IntervalTree2D {
double Max[N*4+10][M*4+10], v;
int n, m, hleaf, Hrt, h, h1, h2, a, a1, a2;
void query1D(int rt, int A1, int A2) {
if(a1<=A1 && A2<=a2) {
ans = max(ans, Max[Hrt][rt]);
return ;
}
int mid = (A1 + A2)/2;
if(mid>=a1)
query1D(lson, A1, mid);
if(mid<a2)
query1D(rson, mid+1, A2);
}
void query2D(int rt, int H1, int H2) {
if(h1<=H1 && H2<=h2) {
Hrt = rt;
query1D(1, 0, m);
return ;
}
int mid = (H1 + H2)/2;
if(mid>=h1)
query2D(lson, H1, mid);
if(mid<h2)
query2D(rson, mid+1, H2);
}
void modify1D(int rt, int A1, int A2) {
if(A1==A2) {
if(hleaf==1) {
Max[Hrt][rt] = max(v, Max[Hrt][rt]);
return ;
}
Max[Hrt][rt] = max(Max[Hrt<<1][rt], Max[Hrt<<1|1][rt]);
return ;
}
int mid = (A1 + A2)/2;
if(mid>= a)
modify1D(lson, A1, mid);
else
modify1D(rson, mid+1, A2);
Max[Hrt][rt] = max(Max[Hrt][lson], Max[Hrt][rson]);
}
void modify2D(int rt, int H1, int H2) {
if(H1 == H2) {
Hrt = rt;
hleaf = 1;
modify1D(1, 0, m);
return ;
}
int mid = (H1+H2)/2;
if(mid>=h)
modify2D(lson, H1, mid);
else
modify2D(rson, mid+1, H2);
Hrt = rt;
hleaf = 0;
modify1D(1, 0, m);
}
void query() {
ans = -inf;
query2D(1, 100, n);
}
void modify() {
modify2D(1, 100, n);
}
void clear() {
for(int i=0; i<=N*4+5; ++i)
for(int j=0; j<=1000*4+5; ++j)
Max[i][j] = -inf;
}
};
IntervalTree2D t;
int main() {
int n;
while(~scanf("%d",&n)&&n) {
t.clear();
t.n = 200;
t.m = 1000;
while(n--) {
char ch;
scanf(" %c", &ch);
int h, hh;
double a, aa;
if(ch=='I') {
scanf("%d%lf%lf", &h, &a, &aa);
t.h = h;
t.a = int(a*10);
t.v = aa;
t.modify();
} else {
scanf("%d%d%lf%lf", &h, &hh, &a, &aa);
if(h>hh) swap(h, hh);
if(a>aa) swap(a, aa);
t.h1 = h;
t.h2 = hh;
t.a1 = int(a*10);
t.a2 = int(aa*10);
t.query();
if(ans < 0)
printf("-1\n");
else
printf("%.1f\n", ans);
}
}
}
return 0;
}