20009. Incremental Suffix Maximum/Minimum Query (ISMQ)

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

題目描述

增長後綴最大值查找 (Incremental Suffix Maximum Query, ISMQ) 屬於區間極值查找 (Range Maximum Query, RMQ) 的一種變型。一開始陣列為空,位置編號從 0 開始,主要支持三種操作:

  • Init N : 初始化數據結構,預期插入最多 $N$ 個元素
  • Append V : 插入一個元素 $V$ 至陣列尾端
  • Query L : 查詢位置 $L$ 到陣列尾端之間的最大值

現在你只需要實作以上三個函數,將透過下述 main.cpp 檢測效能。

main.cpp

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>
#include "ISMQ.h"
 
using namespace std;
 
static uint32_t seed = 0;
static uint32_t p_func(uint32_t x) {return x*9301+49297;}
static uint32_t p_random() {return seed = p_func(seed);}
 
// #define _DEBUG
int main() {
    int N, M, S, MOD;
    assert(scanf("%d %d %d %d", &N, &M, &S, &MOD) == 4);
 
    seed = S;
 
    uint32_t hash = 0;
#ifdef _DEBUG
    static int D[1048576];
#endif
    for (int it = 0; it < M; it++) {
        init_ISMQ(N);
        for (int i = 0; i < N; i++) {
            // step 1: append value to array $A$
            {
                uint32_t V = p_random()%MOD;
                append_ISMQ(V);
#ifdef _DEBUG
                D[i] = V;
#endif
            }
            // step 2: query suffix maximum in $A\lbrack L, i]$
            {
                int L = p_random()%(i+1);
                uint32_t ans = query_ISMQ(L);
                hash ^= ans;
#ifdef _DEBUG
                printf("max(A[%2d, %2d]) = %u\n", L, i, ans);
#endif
            }
        }
    }
 
#ifdef _DEBUG
    printf("[");
    for (int i = 0; i < N; i++)
        printf("%2u%c", D[i], i == N-1 ? ']' : ' ');
    puts("");
#endif
 
    printf("%X\n", hash);
    return 0;
}

ISMQ.h

1
2
3
4
5
6
7
8
9
#ifndef _ISMQ_H
#define _ISMQ_H
#include <stdint.h>
 
void init_ISMQ(int N);
void append_ISMQ(uint32_t V);
uint32_t query_ISMQ(uint32_t L);
 
#endif

ISMQ.cpp (example)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include "ISMQ.h"
#include <algorithm>
using namespace std;
 
int index;
uint32_t A[1048576];
void init_ISMQ(int N) {
    index = 0;
}
void append_ISMQ(uint32_t V) {
    A[index] = V;
    index++;
}
uint32_t query_ISMQ(uint32_t L) {
    uint32_t ret = 0;
    for (int i = L; i < index; i++)
        ret = max(ret, A[i]);
    return ret;
}

輸入格式

只有一組測資,測資一行包含四個整數 $N, \; M, \; S, \text{MOD}$

  • $N \le 2^{24}$
  • $M \le 10^4$
  • $S \lt 2^{31}$
  • $\text{MOD} \lt 2^{31}$

範例輸入

16 1 17 20

範例輸出

1C

範例解釋

max(A[ 0,  0]) = 14
max(A[ 1,  1]) = 16
max(A[ 0,  2]) = 16
max(A[ 1,  3]) = 16
max(A[ 4,  4]) = 14
max(A[ 5,  5]) = 0
max(A[ 5,  6]) = 2
max(A[ 1,  7]) = 16
max(A[ 1,  8]) = 16
max(A[ 5,  9]) = 14
max(A[ 8, 10]) = 18
max(A[ 1, 11]) = 18
max(A[ 5, 12]) = 18
max(A[ 9, 13]) = 18
max(A[10, 14]) = 18
max(A[ 1, 15]) = 18
[14 16 14 12 14  0  2  8 14  8 18 16  6 16  6 16]

Discussion