P3865 【 템 플 릿 】 ST 표

P3865 【 템 플 릿 】ST 표 제출 54.70k 를 통 해 21.82k 시간 제한 800 ms 메모리 제한 125.00 MB 제출 정 답 을 수집 문제 제공 자 한 스 버그 난이도 보급 / 향상 - 역사 점수 100 제출 기록 보기 문제 풀이 태그 O2 최적화 고성능 토론 판 관련 토론 추천 문제 전개 제목 배경 ST 표 고전 문제 - 정적 구간 최대 값
최대 데이터 기한 은 0.8s 에 불과 하 며 데이터 강도 가 낮 지 않 습 니 다. 매번 조회 의 복잡 도 는 O (1) O (1) 임 을 보증 하 십시오.더 높 은 시간 복잡 도 알고리즘 을 사용 하면 통과 할 수 없다.
코드 시간 복잡 도가 정확 하 다 고 생각 하지만 TLE 는 빠 른 읽 기 를 시도 할 수 있 습 니 다.
inline int read () {int x = 0, f = 1; char ch = getchar (); while (! isdigit (ch) {if (ch = '-') f = - 1; ch = getchar ();} while (isdigit (ch) {x = x10 + ch - 48; ch = getchar ();} return xf;} 제목 설명 은 NN 길이 의 수열 과 MM 번 의 질문 을 주 고 모든 질문 구간 내 숫자의 최대 치 를 구 합 니 다.
입력 형식 첫 줄 은 두 개의 정수 N, MN, M 을 포함 하고 각각 수열 의 길이 와 질문 의 개 수 를 표시 합 니 다.
두 번 째 줄 은 NN 개의 정수 (a ia i 로 기록) 를 포함 하고 수열 의 ii 항 을 차례대로 표시 합 니 다.
다음 MM 줄, 줄 당 두 개의 정수 l 포함i, r_il i, r i 는 조회 구간 을 [l i, r i] [l i, r i] 로 표시 합 니 다.
출력 형식 출력 은 MM 줄 을 포함 하고 줄 마다 정 수 를 포함 하 며 매번 문의 한 결 과 를 순서대로 표시 합 니 다.
입 출력 샘플 입 출력

#include
#include
#include
#include
#include
#include
using namespace std;
const int maxn=100005;
const int inf=0x3f3f3f3f;
inline int read(){
     
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)){
     
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
     
        x=x*10+ch-48;
        ch=getchar();
    }
    return x*f;
}
int lg[maxn],st[maxn][20];
int query(int l,int r){
     
    int k=lg[r-l+1]-1;
    return max(st[l][k],st[r-(1<<k)+1][k]);
}
int main(){
     
  int n,m;
 n=read();
 m=read();
  for(int i=1;i<=n;i++){
     
        st[i][0]=read();
  }
  for(int i=1;i<20;i++){
     
      for(int j=1;(1<<i)+j-1<=n;j++){
     
      st[j][i]=max(st[j][i-1],st[j+(1<<(i-1))][i-1]);
      }
  }
  for(int i=1;i<=n;i++){
     
      lg[i]=lg[i-1]+((1<<lg[i-1])==i);
  }
  for(int i=0;i<m;i++){
     
      int l,r;
   l=read();
 r=read();
      printf("%d
",query(l,r));
  }
  return 0;
}

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

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

[POI 2010] PIL - Pilots (BZOJ 2096)

단조 로 운 대열 낙 곡 제목 전송 문 BZOJ 제목 전송 문 물 을 젓다 두 바늘 로 밀어 서 단조 로 운 대기 열 유지 최대 최소 값 입 니 다. 코드:...

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

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

P3865 【 템 플 릿 】 ST 표

좋은 웹페이지 즐겨찾기