20010. Offline Range Maximum Query

I'm a slow walker, but I never walk backwards.

Problem Description

給予長度為 $N$ 的陣列 $A$,元素 $a_0, a_1, \cdots, a_{N-2}, a_{N-1}$ 皆為有號 32-bit 整數,接下來給定 $M$ 組詢問 $l_i, \; r_i$,對於任一組詢問 $l_i \; r_i$,找出區間最大值 $V_i = \max_{l_i \le j \le r_i} a_j$。

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

為解決 IO 效能上的不一致性,你只需要撰寫三個函數

  • 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)

測試用的主程式,採用 standard IO 方便 debug。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#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

支援 RMQ 的操作

#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)

暴力作法-每次詢問 $O(n)$,請修改一下結構加速運算。

#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);
}

Input Format (debug version)

只有一組測資,第一行包含兩個整數 $N, \; M$,表示長度為 $N$ 的陣列、$M$ 組詢問。接著,第二行包含 $N$ 個元素 $a_0, a_1, \cdots, a_{N-2}, a_{N-1}$,分別以空白格開。接著有 $M$ 行,第 $i$ 上包含兩個整數 $l_i, r_i$ 為詢問的區間索引。

Output Format (debug version)

對於每組詢問,依序輸出答案。

Sample Input (debug version)

5 3
10 30 50 20 40
0 4
0 1
3 4

Sample Output (debug version)

50
30
40

編譯參數

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

Discussion