二维线段树 HDU 1823最简单的入门题

xiaoz 征婚,首先输入M,表示有M个操作。

借下来M行,对每一行   Ih a l     I 表示有一个MM报名,H是高度, a是活泼度,L是缘分。

或   Q h1 h2 a1 a2    求出身高在h1  h2  活泼度在a1  a2之间的最大缘分值。

 #include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <list>
#include <iomanip>
#include <cstdlib>
#include <sstream>
using namespace std;
typedef long long LL;
const int INF=0x5fffffff;
const double EXP=1e-;
const int MS=; struct active
{
int l,r;
double maxv;
int mid()
{
return (l+r)>>;
}
}; struct node
{
int l,r;
active actives[*MS];
int mid()
{
return (l+r)>>;
}
}nodes[]; void init()
{
for(int i=;i<;i++)
for(int j=;j<*MS;j++)
nodes[i].actives[j].maxv=-;
} void creat_a(int p,int root,int l,int r)
{
nodes[p].actives[root].l=l;
nodes[p].actives[root].r=r;
if(nodes[p].actives[root].l==nodes[p].actives[root].r)
return ;
int mid=(l+r)/;
creat_a(p,root<<,l,mid);
creat_a(p,root<<|,mid+,r);
} void creat(int root,int l,int r)
{
nodes[root].l=l;
nodes[root].r=r;
creat_a(root,,,MS);
if(nodes[root].l==nodes[root].r)
return ;
int mid=(l+r)/;
creat(root<<,l,mid);
creat(root<<|,mid+,r);
} void insert_a(int p,int root,int pos,double value)
{
if(nodes[p].actives[root].maxv<value)
nodes[p].actives[root].maxv=value;
if(nodes[p].actives[root].l==nodes[p].actives[root].r)
return ;
if(pos<=nodes[p].actives[root].mid())
insert_a(p,root<<,pos,value);
else
insert_a(p,root<<|,pos,value);
} void insert(int root,int pos,int value,double s)
{
insert_a(root,,value,s);
if(nodes[root].l==nodes[root].r)
return ;
if(pos<=nodes[root].mid())
insert(root<<,pos,value,s);
else
insert(root<<|,pos,value,s);
} double query_a(int p,int root,int l,int r)
{
double ans=-;
if(nodes[p].actives[root].l>=l&&nodes[p].actives[root].r<=r)
return nodes[p].actives[root].maxv;
if(l<=nodes[p].actives[root].mid())
ans= max(ans,query_a(p,root<<,l,r));
if(r>nodes[p].actives[root].mid())
ans=max(ans,query_a(p,root<<|,l,r));
return ans;
} double query(int root,int l1,int r1,int l2,int r2)
{
double ans=-;
if(nodes[root].l>=l1&&nodes[root].r<=r1)
return query_a(root,,l2,r2);
// 如果是叶子节点会在上一条语句中返回。
if(l1<=nodes[root].mid())
ans=max(ans,query(root<<,l1,r1,l2,r2));
if(r1>nodes[root].mid())
ans=max(ans,query(root<<|,l1,r1,l2,r2));
return ans;
} int main()
{
int n,h1,h2;
double a1,a2,fate;
creat(,,);
while(scanf("%d",&n)==&&n)
{
init();
char cmd[MS];
while(n--)
{
scanf("%s",cmd);
if(cmd[]=='I')
{
scanf("%d %lf %lf",&h1,&a1,&fate); insert(,h1,(int)(a1*+EXP),fate);
}
else
{
scanf("%d %d %lf %lf",&h1,&h2,&a1,&a2);
if(h1>h2)
swap(h1,h2);
if(a1>a2)
swap(a1,a2);
double ans=query(,h1,h2,(int)(a1*+EXP),(int)(a2*+EXP));
if(ans>=)
printf("%.1lf\n",ans);
else
printf("-1\n");
}
}
}
return ;
}
上一篇:PAT (Basic Level) Practise:1002. 写出这个数


下一篇:hadoop-集群管理(1)——配置文件