HDU 1823 Luck and Love 2 차원 선분 트 리(나무 커버 트 리)
6056 단어 데이터 구조
Luck and Love
Time Limit: 10000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 5460 Accepted Submission(s): 1364
Problem Description
세상 에서 가장 먼 거 리 는 하늘 끝 과 바다 끝 을 사이 에 두 고 있 는 것 이 아니다.
내 가 니 앞에서
사랑 한 다 는 걸 넌 몰라
―― 장 소 현
얼마 전에 와 이 스 키 에 게 결혼 공 고 를 했 습 니 다.예물 이 500 만 원 에 달 했 습 니 다.세상 에,그런데 천문학 적 인 숫자 가 나 왔 습 니 다.얼마나 많은 MM 이 몰 려 들 었 는 지 모 르 겠 습 니 다.그 러 자 골목 에 사람들 이 몰 려 바닥 을 쓸 어 버 린 아 줌 마 까지 몰 려 들 었 습 니 다.
인원 이 너무 많아 와 이 즈 키 는 정 신 없 이 통계 작성 을 모두 메 이 플 아 이 스 잎 에 맡 기 고 혼자 집 으로 달 려 가 쉬 었 다.단풍 과 얼음 잎 이 바 쁘 기 짝 이 없다.그 가 처리 해 야 할 일 은 두 가지 가 있다.하 나 는 MM 의 신청 을 받 아야 하 는 것 이 고,다른 하 나 는 Wiskey 가 요구 에 부 합 된 MM 에서 인연 의 최고 치 를 찾 아 주 는 것 이다.
Input
이 문 제 는 여러 개의 테스트 데이터 가 있 는데 첫 번 째 숫자 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）
모든 입력 한 부동 소수점 은 한 소수 만 있 습 니 다.
Output
매번 질문 작업 에 대해 한 줄 에서 인연 의 최고 치 를 출력 하고 작은 수 를 유지 합 니 다.
찾 을 수 없 는 질문,출력-1.
Sample Input
8 I 160 50.5 60.0 I 165 30.0 80.5 I 166 10.0 50.0 I 170 80.5 77.5 Q 150 166 10.0 60.0 Q 166 177 10.0 50.0 I 166 40.0 99.9 Q 166 177 10.0 50.0 0
Sample Output
80.5 50.0 99.9
Author
威士忌
Source
HDOJ 2007 Summer Exercise（3）- Hold by Wiskey
二维线段树入门题。
第一维是高度，第二维是活泼度。
//171MS 5900K
#include
#include
#define M 1007
#define eps 1e-4
using namespace std;
char s[7];
struct Sub_Tree
{
int left,right,ans;
int mid(){return (left+right)>>1;}
};
struct Tree
{
int left,right;
int mid(){return (left+right)>>1;}
Sub_Tree subtree[4*M];
}tree[M];
void build_subtree(int l,int r,int i,int fa)
{
tree[fa].subtree[i].left=l;
tree[fa].subtree[i].right=r;
tree[fa].subtree[i].ans=-1;
if(l==r)return;
int mid=(l+r)>>1;
build_subtree(l,mid,i<<1,fa);
build_subtree(mid+1,r,i<<1|1,fa);
}
void build(int l,int r,int i)
{
tree[i].left=l;tree[i].right=r;
build_subtree(0,1000,1,i);
if(l==r)return;
int mid=(l+r)>>1;
build(l,mid,i<<1);
build(mid+1,r,i<<1|1);
}
void up(int i,int fa)
{
tree[fa].subtree[i].ans=max(tree[fa].subtree[i<<1].ans,tree[fa].subtree[i<<1|1].ans);
}
void update_subtree(int a,int l,int i,int fa)
{
if(tree[fa].subtree[i].left==tree[fa].subtree[i].right)
{
tree[fa].subtree[i].ans=max(tree[fa].subtree[i].ans,l);
return;
}
int mid=tree[fa].subtree[i].mid();
if(a<=mid)update_subtree(a,l,i<<1,fa);
else update_subtree(a,l,i<<1|1,fa);
up(i,fa);
}
void update(int h,int a,int l,int i)
{
update_subtree(a,l,1,i);
if(tree[i].left==tree[i].right)return;
int mid=tree[i].mid();
if(h<=mid)update(h,a,l,i<<1);
else update(h,a,l,i<<1|1);
}
int query_subtree(int a1,int a2,int i,int fa)
{
if(tree[fa].subtree[i].left>=a1&&tree[fa].subtree[i].right<=a2)return tree[fa].subtree[i].ans;
int mid=tree[fa].subtree[i].mid();
int maxx=-1;
if(a1<=mid)maxx=max(maxx,query_subtree(a1,a2,i<<1,fa));
if(mid=h1&&tree[i].right<=h2)return query_subtree(a1,a2,1,i);
int mid=tree[i].mid();
int maxx=-1;
if(h1<=mid)maxx=max(maxx,query(h1,h2,a1,a2,i<<1));
if(midh2)swap(h1,h2);
if(a1>a2)swap(a1,a2);
int maxx=query(h1,h2,int(a1*10),int(a2*10),1);
if(maxx<0)printf("-1
");
else printf("%.1f
",maxx/10.0);
}
}
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
