낙 곡 3865 (구간 최 값 ST 표 RMQ 템 플 릿)
1602 단어 데이터 구조
이것 은 ST 표 고전 문제 인 정적 구간 최대 값 입 니 다.
최대 데이터 기한 은 0.8s 에 불과 하고 데이터 강도 가 낮 지 않 습 니 다. 매번 조회 의 복잡 도 는 O (1) O (1) O (1) O (1) O (1) 임 을 보증 하 십시오.
제목 설명
N N N 길이 의 수열 을 지정 하고 M M M 에 게 물 어 볼 때마다 구간 내 숫자의 최대 치 를 구 합 니 다.
입력 형식
첫 번 째 줄 은 두 개의 정수 N, M N, M N, M 을 포함 하고 각각 수열 의 길이 와 질문 의 개 수 를 나타 낸다.
두 번 째 줄 은 N N N 개의 정수 (ai a i ai 로 기록) 를 포함 하고 수열 의 ii 항목 을 순서대로 표시 합 니 다.
다음 M M M 줄 은 줄 마다 두 개의 정수 li, ril 를 포함 합 니 다.i, r_i li, ri 는 조회 구간 이 [li, ri] [l i, r i] [li, ri] 임 을 나타 낸다.
출력 형식
출력 은 MM M 줄 을 포함 하고 줄 마다 정 수 를 포함 하 며 매번 문의 한 결 과 를 순서대로 표시 합 니 다.
입 출력 샘플
입력 \ # 1 복사
8 8
9 3 1 7 5 6 0 8
1 6
1 5
2 7
2 6
1 8
4 8
3 7
1 8출력 \ # 1 복사
9
9
7
7
9
8
7
9설명 / 제시
30% 의 데이터 에 대한 만족: 1 ≤ N, M ≤ 10 1 \ \ leq N, M \ \ leq 10 1 ≤ N, M ≤ 10
70% 의 데이터 에 만족: 1 ≤ N, M ≤ 105 1 \ \ leq N, M \ \ leq {10} ^ 5 1 ≤ N, M ≤ 105
100% 데이터 에 대한 만족: 1 ≤ N ≤ 105, 1 ≤ M ≤ 106, ai 8712 ° [0, 109], 1 ≤ li ≤ ri ≤ N 1 \ \ \ leq N \ \ \ leq {10} ^ 5, 1 \ \ leq M \ \ \ leq {10} ^ 6, ai \in [0, {10}^9], 1 \leq l_i \leq r_i \leq N 1≤N≤105,1≤M≤106,ai∈[0,109],1≤li≤ri≤N
템 플 릿:
#include
using namespace std;
const int N=1e5+10;
int n,m;
int a[N];
int f[N][20];///f[i][j] i 2^j ， 【i,i+(1< 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 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에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
