Luck and Love
Time Limit: 10000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 2438 Accepted Submission(s): 627
Problem Description
世界上上最远的距离不是相隔天涯海角 而是我在你面前 可你却不知道我爱你 ―― 张小娴 前段日子，枫冰叶子给Wiskey做了个征婚启事，聘礼达到500万哦，天哪，可是天文数字了啊，不知多少MM蜂拥而至，顿时万人空巷，连扫地的大妈都来凑热闹来了。―_―||| 由于人数太多，Wiskey实在忙不过来，就把统计的事情全交给了枫冰叶子，自己跑回家休息去了。这可够枫冰叶子忙的了，他要处理的有两类事情，一是得接受MM的报名，二是要帮Wiskey查找符合要求的MM中缘分最高值。
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
由于判定的时候有两个限制条件，所以用到了二维线段树来解析这一问题，这里题目中的描述有点问题，后面的H1，H2应该是整型，不然高度如果乘以个10的话，每次创建的就是1000 * 1000 的二维线段了，速度就会很慢了。对于活跃度，肯定是要乘以10的，因为这样才能应用二分来暴力求解了。前面把build()函数放在while( M-- ) 里面那叫错的一个惨啊。这里写了个可以支持重载的输入外挂。
代码如下：
#include#include #include #define LSON p << 1 #define RSON p << 1 | 1 #define Max(x, y) (x) > (y) ? (x) : (y) #define H_TO(x) (x) -100 #define A_TO(x) (int)((x) * 10) #define MID(x, y) (x) + (y) >> 1 #define TWO(x, y) (x) + (y) << 1 using namespace std; void CinInt( int &t ) { char f = 1, c; while( c = getchar(), c < '0' || c > '9' || c == '-' ) { if( c == '-' ) f = -1; } t = c - '0'; while( c = getchar(), c >= '0' && c <= '9' ) t = t * 10 + c -'0'; t = t * f; } void CinStr( char *s ) { int p = -1; char c; while( c = getchar(), c == ' ' || c == '\n' ) ; s[++p] = c; while( c = getchar(), c != ' ' && c != '\n' ) s[++p] = c; s[++p] = '\0'; } void CinDou( double &d ) { d = 0; long long t = 0; int bit = 0; char c; while( c = getchar(), ( c < '0' || c > '9' ) && c != '.' ) ; if( c != '.' ) { t = c - '0'; while( c = getchar(), c >= '0' && c <= '9' && c != '.' ) t = t * 10 + c - '0'; } if( c == '.' ) { while( c = getchar(), c >= '0' && c <= '9' ) { d = d * 10 + c - '0'; bit++; } } while( bit-- ) d /= 10; d += t; } struct node { short l, r, max; }; struct Node { short l, r; node y[2600]; }N[260]; void y_build( node *rt, int p, int l, int r ) { rt[p].l = l, rt[p].r = r, rt[p].max = -1; if( r - l == 1 ) return; int m = MID( l, r ); y_build( rt, LSON, l, m ); y_build( rt, RSON, m, r ); } void build( int p, int l, int r ) { y_build( N[p].y, 1, 0, 1001 ); N[p].l = l, N[p].r = r; if( r - l == 1 ) return; int m = MID( l, r ); build( LSON, l, m ); build( RSON, m, r ); } void y_modify( node *rt, int p, int l, int r, int L ) { rt[p].max = Max( rt[p].max, L ); if( rt[p].r - rt[p].l == 1 ) return; int m = MID( rt[p].l, rt[p].r ); if( m >= r ) y_modify( rt, LSON, l, r, L ); else y_modify( rt, RSON, l, r, L ); } void modify( int p, int l, int r, int l2, int r2, int L ) { y_modify( N[p].y, 1, l2, r2, L ); if( N[p].r - N[p].l == 1 ) return; int m = MID( N[p].l, N[p].r ); if( m >= r ) modify( LSON, l, r, l2, r2, L ); else modify( RSON, l, r, l2, r2, L ); } int y_cal( node *rt, int p, int l, int r ) { if( rt[p].l == l && rt[p].r == r ) { return rt[p].max; } int m = MID( rt[p].l, rt[p].r ); if( m >= r ) return y_cal( rt, LSON, l, r ); else if( m <= l ) return y_cal( rt, RSON, l, r ); else { int a = y_cal( rt, LSON, l, m ); int b = y_cal( rt, RSON, m, r ); return Max( a, b ); } } int cal( int p, int l, int r, int l2, int r2 ) { if( N[p].l == l && N[p].r == r ) { return y_cal( N[p].y, 1, l2, r2 ); } int m = MID( N[p].l, N[p].r ); if( m >= r ) return cal( LSON, l, r, l2, r2 ); else if( m <= l ) return cal( RSON, l, r, l2, r2 ); else { int a = cal( LSON, l, m, l2, r2 ); int b = cal( RSON, m, r, l2, r2 ); return Max( a, b ); } } int main() { int M; while( scanf( "%d", &M ), M ) { build( 1, 0, 101 ); while( M-- ) { char op[5]; scanf( "%s", op ); switch( op[0] ) { case 'I': { int H; double A, L; CinInt( H ), CinDou( A ), CinDou( L ); modify( 1, H_TO(H), H_TO(H) + 1, A_TO(A), A_TO(A) + 1, A_TO(L) ); break; } case 'Q': { int H1, H2; double A1, A2; CinInt( H1 ), CinInt( H2 ), CinDou( A1 ), CinDou( A2 ); if( H1 > H2 ) { int t = H1; H1 = H2; H2 = t; } if( A1 - A2 > 1e-6 ) { double t = A1; A1 = A2; A2 = t; } int ans = cal( 1, H_TO( H1 ), H_TO( H2 ) + 1, A_TO( A1 ), A_TO( A2 ) + 1 ); printf( ans == -1 ? "-1\n" : "%.1lf\n", ans / 10.0 ); } } } } return 0; }