# 20009. Incremental Suffix Maximum/Minimum Query (ISMQ)

## 題目描述

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

### main.cpp

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253#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 _DEBUGint 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

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

12345678910111213141516171819#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 \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]) = 14max(A[ 1,  1]) = 16max(A[ 0,  2]) = 16max(A[ 1,  3]) = 16max(A[ 4,  4]) = 14max(A[ 5,  5]) = 0max(A[ 5,  6]) = 2max(A[ 1,  7]) = 16max(A[ 1,  8]) = 16max(A[ 5,  9]) = 14max(A[ 8, 10]) = 18max(A[ 1, 11]) = 18max(A[ 5, 12]) = 18max(A[ 9, 13]) = 18max(A[10, 14]) = 18max(A[ 1, 15]) = 18[14 16 14 12 14  0  2  8 14  8 18 16  6 16  6 16]