hdu 1754 I Hate It(검색 구간 최 값)

I Hate It
Time Limit: 9000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 45348 Accepted Submission(s): 17792
Problem Description
많은 학교 에서 비교 하 는 습관 이 유행한다.선생님 들 은 모모 에서 모모 까지 점수 가 가장 높 은 것 이 얼마 인지 묻 는 것 을 좋아한다.
이것 은 많은 학생 들 로 하여 금 매우 반감 을 가지 게 한다.
네가 좋아 하 든 안 좋아 하 든 지금 네가 해 야 할 일 은 바로 선생님 의 요구 에 따라 프로그램 을 써 서 선생님 의 질문 을 모 의 하 는 것 이다.물론 선생님 은 어떤 학우 의 성적 을 갱신 해 야 할 때 가 있다.

Input
이 문 제 는 여러 그룹의 테스트 를 포함 하고 있 습 니 다.파일 이 끝 날 때 까지 처리 하 십시오.
각 테스트 의 첫 줄 에는 두 개의 정수 N 과 M(0학생 ID 번 호 는 각각 1 번 에서 N 번 으로 매 겨 진다.
두 번 째 줄 은 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

Sample Output


   
   
   
   
    
    
    
    5
6
5
9


   
   
   
   
   
   
   
   

   
   
   
   
   
   
   
   
    
    
    
      ：
   
   
   
   
   
   
   
   
    
    
    
    #include<cstdio>
#include<cstring>
#define INF 1<<30
using namespace std;

struct node
{
    int l,r,x;
    node(){}
    node(int a,int b,int c):l(a),r(b),x(c){}
};

node a[800000];
int ans;

int max(int x,int y)
{
    return x>y?x:y;
}

void build(int l,int r,int i)
{
    a[i]=node(l,r,0);
    if(a[i].l==a[i].r)
        return;
    int mid=(a[i].l+a[i].r)/2;
    build(l,mid,2*i);
    build(mid+1,r,2*i+1);
}

void update(int p,int x,int i)
{
    if(a[i].l==a[i].r&&a[i].r==p)
    {
        a[i].x=x;
        return;
    }
    int mid=(a[i].l+a[i].r)/2;
    if(p<=mid)
        update(p,x,2*i);
    else
        update(p,x,2*i+1);
    a[i].x=max(a[2*i].x,a[2*i+1].x);
}

void query(int l,int r,int i)
{
    if(a[i].l==l&&a[i].r==r)
    {
        ans=max(a[i].x,ans);
        return;
    }
    int mid=(a[i].l+a[i].r)/2;
    if(r<=mid)
        query(l,r,2*i);
    else if(l>=mid+1)
        query(l,r,2*i+1);
    else
    {
        query(l,mid,2*i);
        query(mid+1,r,2*i+1);
    }

}

int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)==2)
    {
        build(1,n,1);
        for(int i=1;i<=n;i++)
        {
            int x;
            scanf("%d",&x);
            update(i,x,1);
        }
        char c;
        getchar();
        for(int i=0;i<m;i++)
        {
            int xx,yy;
            scanf("%c%d%d%*c",&c,&xx,&yy);
            if(c=='U')
            {
                update(xx,yy,1);
            }
            if(c=='Q')
            {
                ans=-INF;
                query(xx,yy,1);
                printf("%d
",ans);
            }
        }
    }
    return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

HDU - 1166 - 적병 포진 (나무형 수조 또는 선분 수)

C 국 의 앙 숙 A 국 은 그동안 군사훈련 을 하고 있 었 기 때문에 C 국 간첩 두목 인 데 릭 과 그의 수하 인 티 디 는 또 바 빠 지기 시작 했다.A 국 가 는 해안선 을 따라 직선 으로 N 개 공병 캠프 ...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

hdu 1754 I Hate It(검색 구간 최 값)

좋은 웹페이지 즐겨찾기