HDU 1823 Luck and Love 二维线段树 / 矩形树

2024-04-23 20:32
文章标签 二维 hdu 线段 矩形 love luck 1823

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

题意：
本题有多个测试数据，第一个数字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）所有输入的浮点数，均只有一位小数。

题解：
注意浮点数的处理，一般来说可以离散化，或者化作整数处理。
二维线段树，第一维度的每一个节点都包含第二维度的一颗线段树。这种方式对于更高的维度就不是适用了。这时可用矩形树。

#include <iostream>
using namespace std;
#define N 270
#define M 2100
int lch ( int x ) { return x * 2; }
int rch ( int x ) { return x * 2 + 1; }
int max ( int x, int y ) { return x > y ? x : y; }
struct sonNode
{
int l, r, val;
void getlr ( int tl, int tr )
{
l = tl; r = tr;
}
};
struct parentNode
{
int l, r;
sonNode son[M];
void getlr ( int tl, int tr ) 
{
l = tl; r = tr;
}    
};
parentNode node[N];
void sub_build ( int f, int u, int l, int r )
{
node[f].son[u].getlr ( l, r );
node[f].son[u].val = -1;
if ( l == r ) return;
int mid = ( l + r ) / 2;
sub_build ( f, lch(u), l, mid );
sub_build ( f, rch(u), mid+1, r );
}
void build ( int f, int l1, int r1, int l2, int r2 )
{
node[f].getlr ( l1, r1 );
sub_build ( f, 1, l2, r2 );
if ( l1 == r1 ) return;
int mid = ( l1 + r1 ) / 2;
build ( lch(f), l1, mid, l2, r2 );
build ( rch(f), mid+1, r1, l2, r2 );
}
void sub_update ( int f, int u, int pos2, int val )
{
if ( u > M ) return;   /* 此条件不可忽略 */
node[f].son[u].val = max ( node[f].son[u].val, val );
if ( node[f].son[u].l == pos2 && node[f].son[u].r == pos2 )
{
node[f].son[u].val = max ( node[f].son[u].val, val );
return;
}
int mid = ( node[f].son[u].l + node[f].son[u].r ) / 2;
if ( pos2 <= mid )
sub_update ( f, lch(u), pos2, val );
else
sub_update ( f, rch(u), pos2, val );
}
void update ( int f, int pos1, int pos2, int val )
{
if ( f > N ) return;
sub_update ( f, 1, pos2, val );
if ( node[f].l == node[f].r ) return;
int mid = ( node[f].l + node[f].r ) / 2;
if ( pos1 <= mid )
update ( lch(f), pos1, pos2, val );
else
update ( rch(f), pos1, pos2, val );
}
int sub_query ( int f, int u, int l2, int r2 )
{    
if ( u > M ) return -1;  // !!!
if ( node[f].son[u].l == l2 && node[f].son[u].r == r2 )
return node[f].son[u].val;
int mid = ( node[f].son[u].l + node[f].son[u].r ) / 2;
if ( r2 <= mid )
return sub_query ( f, lch(u), l2, r2 );
else if ( l2 > mid )
return sub_query ( f, rch(u), l2, r2 );
else
return max ( sub_query(f,lch(u),l2,mid), sub_query(f,rch(u),mid+1,r2) );
}
int query ( int f, int l1, int r1, int l2, int r2 )
{
if ( f > N ) return -1;   //!!!
if ( node[f].l == l1 && node[f].r == r1 )
return sub_query ( f, 1, l2, r2 );
int mid = ( node[f].l + node[f].r ) / 2;
if ( r1 <= mid )
return query ( lch(f), l1, r1, l2, r2 );
else if ( l1 > mid )
return query ( rch(f), l1, r1, l2, r2 );
else
return max ( query(lch(f),l1,mid,l2,r2), query(rch(f),mid+1,r1,l2,r2) );
}
int main ()
{
char ch[3];
int m, h, hl, hr, ans;
double a, l, al, ar;
//freopen("a.txt","r",stdin);
while ( scanf("%d",&m) != EOF && m )
{
memset(node,0,sizeof(node));
build ( 1, 100, 200, 0, 1000 );
while ( m-- )
{    
scanf("%s",ch);
if ( ch[0] == 'I' )
{
scanf("%d%lf%lf", &h, &a, &l );
update ( 1, h, (int)(a*10), (int)(l*10) );
}
else
{
scanf("%d%d%lf%lf", &hl, &hr, &al, &ar);
if ( hl > hr ) swap ( hl, hr );
if ( al > ar ) swap ( al, ar );
ans = query ( 1, hl, hr, (int)(al*10), (int)(ar*10) );
if ( ans < 0 ) printf("-1\n");
else printf("%.1lf\n", ans/10.0 );
}
}
}
return 0;
}



下面是我用矩形树写的，老是超内存，自己不太会优化，没办法了。算学习下算法，就不纠结它了。

#include <algorithm>
#include <cmath>
#include <iostream>
using namespace  std;
#define N 200000
#define eps 0.00001
double bset[N];
int n, size, cnt, tol;
struct tree
{
int son[4];
int x1, y1, x2, y2;
double love;
} node[N*4];
struct operation
{
int kind;
double h1, h2, a1, a2, love;
} oper[N];
double max ( double a, double b )
{
return a > b ? a : b;
}
int bfind ( double key )
{
int l = 1, r = cnt;
while ( l <= r )
{
int mid = ( l + r ) / 2;
if ( fabs(bset[mid]-key) < eps )
return mid;
if ( bset[mid] > key )
r = mid - 1;
else
l = mid + 1;
}
return -1;
}
bool cross( int u, int x1, int y1, int x2, int y2 ) //判断两矩形是否相交
{
int x3 = node[u].x1;
int y3 = node[u].y1;
int x4 = node[u].x2;
int y4 = node[u].y2;
if ( y2 < y3 || y4 < y1 || x4 < x1 || x2 < x3)
return false;
return true;
}
void build ( int x1, int y1, int x2, int y2 ) 
{
int u = ++tol; /* tol 表示节点编号 */
node[u].love = -1.0;
node[u].x1 = x1; node[u].y1 = y1;
node[u].x2 = x2; node[u].y2 = y2;
if ( x1 == x2 && y1 == y2 )
return;
int midx = ( x1 + x2 ) / 2;
int midy = ( y1 + y2 ) / 2;
if ( x1 <= midx && y1 <= midy )   /* 左下方子矩形 */
{
node[u].son[0] = tol + 1;
build ( x1, y1, midx, midy ); 
}
else node[u].son[0] = 0;
if ( midx + 1 <= x2 && midy + 1 <= y2 ) /* 右上方子矩形 */
{
node[u].son[1] = tol + 1;
build ( midx+1, midy+1, x2, y2 ); 
}
else node[u].son[1] = 0;
if ( x1 <= midx && midy + 1 <= y2 ) /*左上方*/
{
node[u].son[2] = tol + 1;
build ( x1, midy + 1, midx, y2 ); 
}
else node[u].son[2] = 0;
if ( midx + 1 <= x2 && y1 <= midy ) /* 右下方 */
{
node[u].son[3] = tol + 1;
build ( midx + 1, y1, x2, midy ); 
}
else node[u].son[3] = 0;
}
void update ( int u, int x, int y, double val )
{
if ( node[u].x1 == node[u].x2 && node[u].y1 == node[u].y2 )
{
node[u].love = max ( node[u].love, val );
return;
}
int midx = ( node[u].x1 + node[u].x2 ) / 2;
int midy = ( node[u].y1 + node[u].y2 ) / 2;
if ( x <= midx )
{
if ( y <= midy )
update ( node[u].son[0], x, y, val );
else
update ( node[u].son[2], x, y, val );
}
else
{
if ( y <= midy )
update ( node[u].son[3], x, y, val );
else
update ( node[u].son[1], x, y, val );
}
double temp = -1;
for ( int i = 0; i < 4; ++i )
temp = max ( temp, node[node[u].son[i]].love );
node[u].love = temp;
}
double query ( int u, int x1, int y1, int x2, int y2 )
{
if ( ! cross(u,x1,y1,x2,y2)  || node[u].love < 0 )
return -1.0;
if ( x1 <= node[u].x1 && y1 <= node[u].y1 && node[u].x2 <= x2 && node[u].y2 <= y2 )
return node[u].love;
double temp = -1.0;
for ( int i = 0; i < 4; ++i )
temp = max ( temp, query ( node[u].son[i], x1, y1, x2, y2) );
return temp;
}
int main ()
{
char ch[3];
int i;
//freopen("a.txt","r",stdin);
while ( scanf("%d",&n) != EOF && n )
{
size = 0;
memset(bset,0,sizeof(bset));
memset(node,0,sizeof(node));
memset(oper,0,sizeof(oper));
for ( i = 1; i <= n; ++i )
{
scanf("%s",ch);
if ( ch[0] == 'I' )
{
oper[i].kind = 0;
scanf("%lf%lf%lf", &oper[i].h1, &oper[i].a1, &oper[i].love );
bset[++size] = oper[i].h1;
bset[++size] = oper[i].a1;
}
else
{
oper[i].kind = 1;
scanf("%lf%lf%lf%lf", &oper[i].h1, &oper[i].h2, &oper[i].a1, &oper[i].a2 );
bset[++size] = oper[i].h1;
bset[++size] = oper[i].h2;
bset[++size] = oper[i].a1;
bset[++size] = oper[i].a2;
}
}
sort ( bset+1, bset+size+1 );
for ( cnt = i = 1; i <= size; ++i ) /* 离散化 */
{
if ( bset[cnt] != bset[i] )
bset[++cnt] = bset[i];
}
tol = 0;
build ( 1, 1, cnt, cnt ); 
for ( i = 1; i <= n; ++i )
{
if ( oper[i].kind == 0 )
{
int x = bfind ( oper[i].h1 );
int y = bfind ( oper[i].a1 );
update ( 1, x, y, oper[i].love );
}
else
{
int x1 = bfind ( oper[i].h1 );
int x2 = bfind ( oper[i].h2 );
int y1 = bfind ( oper[i].a1 );
int y2 = bfind ( oper[i].a2 );
if ( x1 > x2 ) swap(x1,x2);
if ( y1 > y2 ) swap(y1,y2);
double ans =  query ( 1, x1, y1, x2, y2 );
if ( ans < 0 )
printf("-1\n");
else
printf ("%.1lf\n", ans );
}
}
}
return 0;
}


这篇关于HDU 1823 Luck and Love 二维线段树 / 矩形树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/929809。

相关文章

poj2576(二维背包)

poj2576(二维背包)

题意：n个人分成两组，两组人数只差小于1 ， 并且体重只差最小 对于人数要求恰好装满，对于体重要求尽量多，一开始没做出来，看了下解题，按照自己的感觉写，然后a了 状态转移方程：dp[i][j] = max(dp[i][j],dp[i-1][j-c[k]]+c[k]);其中i表示人数，j表示背包容量，k表示输入的体重的 代码如下： #include<iostream>#include<
阅读更多...
hdu2159（二维背包）

hdu2159（二维背包）

这是我的第一道二维背包题，没想到自己一下子就A了，但是代码写的比较乱，下面的代码是我有重新修改的 状态转移：dp[i][j] = max(dp[i][j], dp[i-1][j-c[z]]+v[z]); 其中dp[i][j]表示，打了i个怪物，消耗j的耐力值，所得到的最大经验值 代码如下： #include<iostream>#include<algorithm>#include<
阅读更多...
poj3468(线段树成段更新模板题)

poj3468(线段树成段更新模板题)

题意：包括两个操作：1、将[a.b]上的数字加上v；2、查询区间[a,b]上的和 下面的介绍是下解题思路： 首先介绍  lazy－tag思想：用一个变量记录每一个线段树节点的变化值，当这部分线段的一致性被破坏我们就将这个变化值传递给子区间，大大增加了线段树的效率。 比如现在需要对[a,b]区间值进行加c操作，那么就从根节点[1,n]开始调用update函数进行操作，如果刚好执行到一个子节点，
阅读更多...
hdu1394(线段树点更新的应用)

hdu1394(线段树点更新的应用)

题意：求一个序列经过一定的操作得到的序列的最小逆序数 这题会用到逆序数的一个性质，在0到n-1这些数字组成的乱序排列，将第一个数字A移到最后一位，得到的逆序数为res-a+(n-a-1) 知道上面的知识点后，可以用暴力来解 代码如下： #include<iostream>#include<algorithm>#include<cstring>#include<stack>#in
阅读更多...
hdu1689(线段树成段更新)

hdu1689(线段树成段更新)

两种操作：1、set区间[a,b]上数字为v；2、查询[ 1 , n ]上的sum 代码如下： #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdl
阅读更多...
usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心： 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数，若返回值为正，qsort 函数判定a>b ；为负，a<b；为0，a==b； int milkcmp(const void *va,c
阅读更多...
poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大，用原来的O（n^2）会爆。 小白上的O(n^2)解法代码：TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO
阅读更多...
hdu 2093 考试排名（sscanf）

hdu 2093 考试排名（sscanf）

模拟题。 直接从教程里拉解析。 因为表格里的数据格式不统一。有时候有"()"，有时候又没有。而它也不会给我们提示。 这种情况下，就只能它它们统一看作字符串来处理了。现在就请出我们的主角sscanf()! sscanf 语法: #include int sscanf( const char *buffer, const char *format, ... ); 函数sscanf()和
阅读更多...
hdu 2602 and poj 3624(01背包)

hdu 2602 and poj 3624(01背包)

01背包的模板题。 hdu2602代码： #include<stdio.h>#include<string.h>const int MaxN = 1001;int max(int a, int b){return a > b ? a : b;}int w[MaxN];int v[MaxN];int dp[MaxN];int main(){int T;int N, V;s
阅读更多...
hdu 1754 I Hate It（线段树，单点更新，区间最值）

hdu 1754 I Hate It（线段树，单点更新，区间最值）

题意是求一个线段中的最大数。 线段树的模板题，试用了一下交大的模板。效率有点略低。 代码： #include <stdio.h>#include <string.h>#define TREE_SIZE (1 << (20))//const int TREE_SIZE = 200000 + 10;int max(int a, int b){return a > b ? a :
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2