hdu - 1823 - Luck and Love（线段树）

本文主要是介绍hdu - 1823 - Luck and Love（线段树），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：Wiskey招女友，每个女生看其身高、活泼度和缘分值。现在执行两种操作，1、I，加入一位女生的身高，活泼度和缘分值；2、Q，查询身高在H1, H2之间，活泼度在A1, A2之间的女生的最高缘分值。

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1823

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

现在要查身高限一个区间，活泼度限一个区间，是一个二维的情景。。将线段树扩至二维。。时间复杂度：O(N+M*log(N)^2)。。

——>>坑1：G++的BUG。。。。以G++提交数次皆WA。。改交C++即过。。有朋友指出是代码触发了未定义行为，也有朋友说是因为G++的O2 BUG。。

——>>坑2：题目中说是1位小数，那么，处理方法用scanf("%d.%d", &A1, &A2)，再进行A1 * 10 + A2，会比用scanf("%lf", &A)，再进行(int)(A * 10)更精确（自己测下0.0到0.9就可以发现）。。可是，用第一种处理方式却会WA，偏偏要用第二种不那么精确的处理方式才会AC。。

第一道二维线段树题目，做到想哭了。。

#include <cstdio>
#include <algorithm>using namespace std;#define lc (o<<1)
#define rc ((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, lc, L, M);build_A(O, rc, 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(lc, L, M);build_H(rc, 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, lc, L, M, A, D);else Insert_A(O, rc, M+1, R, A, D);mmax[O][o] = 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 == R) return;int M = (L + R) >> 1;if(H <= M) Insert(lc, L, M, H, A, D);else Insert(rc, 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, lc, L, M, A1, A2);if(A2 > M) Max2 = query_A(O, rc, 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(lc, L, M, H1, H2, A1, A2);if(H2 > M) Max2 = query(rc, 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, A1, A2, D, D1, D2;
//                scanf("%d %d.%d %d.%d", &H, &A1, &A2, &D1, &D2);
//                A = A1 * 10 + A2;
//                D = D1 * 10 + D2;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, A[6];
//                scanf("%d %d %d.%d %d.%d", &H1, &H2, A+2, A+3, A+4, A+5);
//                A[0] = A[2] * 10 + A[3];
//                A[1] = A[4] * 10 + A[5];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);
//                if(A[0] > A[1]) swap(A[0], A[1]);
//                int ret = query(1, 100, 200, H1, H2, A[0], A[1]);int ret = query(1, 100, 200, H1, H2, A1, A2);ret != -1 ? printf("%.1f\n", ret/10.0) : puts("-1");}}}return 0;
}

这篇关于hdu - 1823 - Luck and Love（线段树）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---