# 20010. Offline Range Maximum Query

## Problem Description

• $1 \le N, \; M \le 10^7$
• $-2^{31}\le a_i \le 2^{31} - 1$
• $0 \le l_i, \; r_i \lt N$

• void* preprocessing(int N, int32_t A[])
輸入結束後，將長度為 $N$ 的陣列 $A$，在前處理步驟後，回傳資料結構的資訊。
• void offline_query(void* tool, int M, int32_t Q[][2], int32_t R[]);:
呼叫完前處理後，將詢問區間傳入給離線詢問的函數，並將答案寫於陣列 $R$ 中。
• void destroy(void *tool);:
釋放資料結構的空間。

### main.cpp (debug version)

12345678910111213141516171819202122232425262728293031#include "RMQ.h" #include <cstdio>#include <cstdlib>#include <cstring>#include <cassert> using namespace std;const int MAXN = 1<<24;const int MAXQ = 1<<24;int main() {    static int32_t A[MAXN];    static int32_t Q[MAXQ][2];    int n, m;    assert(scanf("%d%d", &n, &m) == 2);    for (int i = 0; i < n; i++)        assert(scanf("%d", &A[i]) == 1);    for (int i = 0; i < m; i++)        assert(scanf("%d%d", &Q[i][0], &Q[i][1]) == 2);     {        int32_t *R = (int32_t *) malloc(sizeof(int32_t)*m);        void *tool = preprocessing(n, A);        offline_query(tool, m, Q, R);        for (int i = 0; i < m; i++)            printf("%d\n", R[i]);        free(R);        destroy(tool);    }    return 0;}


### RMQ.h

#ifndef __RMQ_H#define __RMQ_H #include <cstdint>void* preprocessing(int N, int32_t A[]);void offline_query(void *tool, int M, int32_t Q[][2], int32_t R[]);void destroy(void *tool);#endif


### RMQ.cpp (Naive)

#include "RMQ.h"#include <cstdlib>#include <cstring> struct Naive {    int32_t *A;};static inline int32_t max(int32_t x, int32_t y) {    return x > y ? x : y;}void* preprocessing(int N, int32_t A[]) {    Naive *tool = (Naive*) malloc(sizeof(Naive));    tool->A = (int32_t *) malloc(sizeof(int32_t) * N);    memcpy(tool->A, A, sizeof(int32_t)*N);    return tool;}void offline_query(void *tool, int M, int32_t Q[][2], int32_t R[]) {    Naive *t = (Naive*) tool;    for (int i = 0; i < M; i++) {        int32_t l = Q[i][0], r = Q[i][1];        int32_t mx = t->A[l];        for (int j = l+1; j <= r; j++)            mx = max(mx, t->A[j]);        R[i] = mx;    }}void destroy(void *tool) {    Naive *t = (Naive*) tool;    free(t->A);    free(t);}


## Sample Input (debug version)

5 310 30 50 20 400 40 13 4


## Sample Output (debug version)

503040


## 編譯參數

TARGET=main DSA=RMQ.o CFLAG=-Wall -std=c++11 -O2CXX=g++ all: $(TARGET) main: main.cpp$(DSA)        $(CXX)$(CFLAG) $^ -o$@ %.o: %.cpp        $(CXX)$(CFLAG) $^ -c clean: rm$(TARGET) *.o