낙 곡 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<

좋은 웹페이지 즐겨찾기