hdu1823LuckandLove（线段树）

题意&＃xff1a;Wiskey招女友&＃xff0c;每一个女生看其身高、活泼度和缘分值。如今运行两种操作&＃xff0c;1、I。增加一位女生的身高。活泼度和缘分值&＃xff1b;2、Q&＃xff0c;查询身高在H1, H2之间&＃xff0c;活泼度在A1, A2之间的女生的最高缘分值。

题目链接&＃xff1a;http://acm.hdu.edu.cn/showproblem.php?pid&＃61;1823

——>>查询某个区间的最值&＃xff0c;若是一维&＃xff0c;可用RMQ解法。。也可用线段树解法。。

如今要查身高限一个区间。活泼度限一个区间&＃xff0c;是一个二维的情景。

。将线段树扩至二维。。时间复杂度&＃xff1a;O(N&＃43;M*log(N)^2)。。

——>>坑1&＃xff1a;G&＃43;&＃43;的BUG。。。

。以G&＃43;&＃43;提交数次皆WA。

。

改交C&＃43;&＃43;即过。。有朋友指出是代码触发了没有定义行为&＃xff0c;也有朋友说是由于G&＃43;&＃43;的O2 BUG。

。

——>>坑2&＃xff1a;题目中说是1位小数。那么。处理方法用scanf("%d.%d", &A1, &A2)。再进行A1 * 10 &＃43; A2&＃xff0c;会比用scanf("%lf", &A)&＃xff0c;再进行(int)(A * 10)更精确&＃xff08;自己測下0.0到0.9就能够发现&＃xff09;。。但是&＃xff0c;用第一种处理方式却会WA&＃xff0c;偏偏要用另外一种不那么精确的处理方式才会AC。。

第一道二维线段树题目&＃xff0c;做到想哭了。

。

#include
#include using namespace std;#define lc (o<<1)
#define rc ((o<<1)|1)const int maxh &＃61; 100 &＃43; 10;
const int maxa &＃61; 1000 &＃43; 10;
int mmax[maxh<<2][maxa<<2];void build_A(int O, int o, int L, int R) { //活泼度建树mmax[O][o] &＃61; -1;if(L &＃61;&＃61; R) return;int M &＃61; (L &＃43; R) >> 1;build_A(O, lc, L, M);build_A(O, rc, M&＃43;1, R);
}void build_H(int o, int L, int R) { //身高建树build_A(o, 1, 0, 1000);if(L &＃61;&＃61; R) return;int M &＃61; (L &＃43; R) >> 1;build_H(lc, L, M);build_H(rc, M&＃43;1, R);
}void Insert_A(int O, int o, int L, int R, int A, int D) { //依据活泼度建树if(L &＃61;&＃61; R) {mmax[O][o] &＃61; max(mmax[O][o], D);return;}int M &＃61; (L &＃43; R) >> 1;if(A <&＃61; M) Insert_A(O, lc, L, M, A, D);else Insert_A(O, rc, M&＃43;1, R, A, D);mmax[O][o] &＃61; max(mmax[O][lc], mmax[O][rc]);
}void Insert(int o, int L, int R, int H, int A, int D) {Insert_A(o, 1, 0, 1000, A, D);if(L &＃61;&＃61; R) return;int M &＃61; (L &＃43; R) >> 1;if(H <&＃61; M) Insert(lc, L, M, H, A, D);else Insert(rc, M&＃43;1, R, H, A, D);
}int query_A(int O, int o, int L, int R, int A1, int A2) { //依据活泼度查询if(A1 <&＃61; L && R <&＃61; A2) return mmax[O][o];int M &＃61; (L &＃43; R) >> 1;int Max1 &＃61; -1, Max2 &＃61; -1;if(A1 <&＃61; M) Max1 &＃61; query_A(O, lc, L, M, A1, A2);if(A2 > M) Max2 &＃61; query_A(O, rc, M&＃43;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 <&＃61; L && R <&＃61; H2) return query_A(o, 1, 0, 1000, A1, A2);int M &＃61; (L &＃43; R) >> 1;int Max1 &＃61; -1, Max2 &＃61; -1;if(H1 <&＃61; M) Max1 &＃61; query(lc, L, M, H1, H2, A1, A2);if(H2 > M) Max2 &＃61; query(rc, M&＃43;1, R, H1, H2, A1, A2);return (Max1 > Max2) ?

Max1 : Max2; } int main() { int M; char op; while(scanf("%d", &M) &＃61;&＃61; 1 && M) { build_H(1, 100, 200); for(int i &＃61; 0; i A2) swap(A1, A2); if(H1 > H2) swap(H1, H2); // if(A[0] > A[1]) swap(A[0], A[1]); // int ret &＃61; query(1, 100, 200, H1, H2, A[0], A[1]); int ret &＃61; query(1, 100, 200, H1, H2, A1, A2); ret !&＃61; -1 ?

printf("%.1f\n", ret/10.0) : puts("-1"); } } } return 0; }