hdu 1754 I Hate It(가장 기본 적 인 선분 트 리)
Time Limit: 9000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 9465 Accepted Submission(s): 3534
Problem Description
많은 학교 에서 비교 하 는 습관 이 유행한다.선생님 들 은 모모 에서 모모 까지 점수 가 가장 높 은 것 이 얼마 인지 묻 는 것 을 좋아한다.
이것 은 많은 학생 들 로 하여 금 매우 반감 을 가지 게 한다.
네가 좋아 하 든 안 좋아 하 든 지금 네가 해 야 할 일 은 바로 선생님 의 요구 에 따라 프로그램 을 써 서 선생님 의 질문 을 모 의 하 는 것 이다.물론 선생님 은 어떤 학우 의 성적 을 갱신 해 야 할 때 가 있다.
Input
이 문 제 는 여러 그룹의 테스트 를 포함 하고 있 습 니 다.파일 이 끝 날 때 까지 처리 하 십시오.
각 테스트 의 첫 줄 에는 두 개의 정수 N 과 M(0
두 번 째 줄 은 N 개의 정 수 를 포함 하고 이 N 명의 학생 들 의 초기 성적 을 대표 하 며 그 중에서 i 의 수 는 ID 가 i 인 학생 들 의 성적 을 대표 한다.
다음은 M 줄.줄 마다 하나의 문자 C('Q'또는'U'만 가 져 오기)와 두 개의 정수 A,B 가 있 습 니 다.
C 가'Q'일 때 이것 은 질문 조작 이 라 고 표시 했다.ID 가 A 에서 B(A,B 포함)까지 의 학생 중에서 성적 이 가장 높 은 것 은 얼마 인지 물 었 다.
C 가'U'일 때 는 ID 가 A 인 학생 의 성적 을 B 로 변경 하 라 는 업데이트 작업 이 라 고 밝 혔 다.
Output
매번 문의 조작 에 대해 한 줄 에서 최고 성적 을 출력 합 니 다.
Sample Input
5 6
1 2 3 4 5
Q 1 5
U 3 6
Q 3 4
Q 4 5
U 2 9
Q 1 5
Sample Output
5
6
5
9
이 문제 의 대의:한 줄 의 수 를 드 리 겠 습 니 다.그 중 한 구간 의 최대 치 는 얼마 입 니까?뚜렷 한 선분 트 리,가장 기본 적 이 고 가장 기본 적 인 선분 트 리 는 선분 트 리 의 건설,업데이트,질문 세 가지 함 수 를 직접 사용 합 니 다.
링크:http://acm.hdu.edu.cn/showproblem.php?pid=1754
코드:
#include <iostream>
#include <stdio.h>
#include <cstring>
using namespace std;
struct node
{
int left, right, mid;
int maxn;
}w[4*200005];
int val[200005];
int creat(int a, int b, int r) //
{
if(a == b)
{
w[r].left = w[r].right = a;
w[r].maxn = val[a];
return w[r].maxn;
}
w[r].left = a;
w[r].right = b;
w[r].mid = (a+b)/2;
w[r].maxn = max(creat(a, w[r].mid, 2*r), creat(w[r].mid+1, b, 2*r+1));
return w[r].maxn;
}
void update(int n, int m, int r) //
{
if(w[r].left == n && w[r].right == n)
{
w[r].maxn = m;
return;
}
if(n > w[r].mid)
{
update(n, m, 2*r+1);
w[r].maxn = max(w[2*r].maxn, w[2*r+1].maxn);
}
else
{
update(n, m, 2*r);
w[r].maxn = max(w[2*r].maxn, w[2*r+1].maxn);
}
}
int query(int a, int b, int r) //
{
if(w[r].left == a && w[r].right == b)
{
return w[r].maxn;
}
else if(a > w[r].mid)
{
return query(a, b, 2*r+1);
}
else if(b <= w[r].mid)
{
return query(a, b, 2*r);
}
else
{
return max(query(a, w[r].mid, 2*r), query(w[r].mid+1, b, 2*r+1));
}
}
int main()
{
char sh;
int i, t, n, x, y;
while(scanf("%d %d", &n, &t) != EOF)
{
for(i = 1; i <= n; i++)
{
scanf("%d", &val[i]);
}
creat(1, n, 1);
while(t--)
{
cin>>sh;
scanf("%d %d", &x, &y);
if(sh == 'Q')
{
printf("%d
", query(x, y, 1));
}
else if(sh == 'U')
{
update(x, y, 1);
}
}
}
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에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
