题意:
前段日子，枫冰叶子给Wiskey做了个征婚启事，聘礼达到500万哦，天哪，可是天文数字了啊，不知多少MM蜂拥而至，顿时万人空巷，连扫地的大妈都来凑热闹来了。―_―|||由于人数太多，Wiskey实在忙不过来，就把统计的事情全交给了枫冰叶子，自己跑回家休息去了。
这可够枫冰叶子忙的了，他要处理的有两类事情，一是得接受MM的报名，二是要帮Wiskey查找符合要求的MM中缘分最高值。
题解:
开始想用二维树状数组来水...但发现求最值无法用树状数组维护...树状数组只能求和吧...
那么就用二维线段树了...所以把所有的double转化成整数(只有一位小数..乘以10就好)....二维线段树就是第一维度的每个点又是树...空间非常大...
最值得注意的是update部分...第一层树每进入一个点..就往第二层更新..
WA了好久....因为H的范围搞错了..用作1~100了..结果WA了一个小时....
Program:
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<queue>
#include<stack>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<time.h>
#define ll long long
#define oo 1000000009
#define MAXN 1200
#define pi acos(-1.0)
#define eps 1e-6
using namespace std;
int D[202<<2][1002<<2];
void updateX(int PY,int X,int l,int r,int d,int now)
{
D[now][PY]=max(D[now][PY],d);
if (l==r) return;
int mid=l+r>>1;
if (X<=mid) updateX(PY,X,l,mid,d,now<<1);
else updateX(PY,X,mid+1,r,d,now<<1|1);
}
int queryX(int PY,int XL,int XR,int l,int r,int now)
{
if (XL<=l && XR>=r) return D[now][PY];
int mid=l+r>>1;
int ans=-oo;
if (XL<=mid) ans=max(ans,queryX(PY,XL,XR,l,mid,now<<1));
if (XR>mid) ans=max(ans,queryX(PY,XL,XR,mid+1,r,now<<1|1));
return ans;
}
void update(int X,int Y,int l,int r,int d,int now)
{
updateX(now,X,100,200,d,1);
if (l==r) return;
int mid=l+r>>1;
if (Y<=mid) update(X,Y,l,mid,d,now<<1);
else update(X,Y,mid+1,r,d,now<<1|1);
}
int query(int XL,int XR,int YL,int YR,int l,int r,int now)
{
if (YL<=l && YR>=r) return queryX(now,XL,XR,100,200,1);
int mid=l+r>>1;
int ans=-oo;
if (YL<=mid) ans=max(ans,query(XL,XR,YL,YR,l,mid,now<<1));
if (YR>mid) ans=max(ans,query(XL,XR,YL,YR,mid+1,r,now<<1|1));
return ans;
}
int main()
{
int M,H,A,H1,H2,A1,A2,L;
double t1,t2;
char c;
while (~scanf("%d",&M) && M)
{
memset(D,-1,sizeof(D));
while (M--)
{
do { c=getchar(); } while (c!='I' && c!='Q');
if (c=='I')
{
scanf("%d%lf%lf",&H,&t1,&t2);
A=int((t1+eps)*10),L=int((t2+eps)*10);
update(H,A,0,1000,L,1);
}else
{
scanf("%d%d%lf%lf",&H1,&H2,&t1,&t2);
if (H1>H2) swap(H1,H2);
A1=int((t1+eps)*10),A2=int((t2+eps)*10);
if (A1>A2) swap(A1,A2);
t1=query(H1,H2,A1,A2,0,1000,1);
if (t1<0) printf("-1\n");
else printf("%.1f\n",t1/10.0);
}
}
}
return 0;
}