回『原創/不分類題庫』
b494: 史蒂芙的修羅道
標籤 : RMQ

通過比率 : 57% (4 人 / 7 人 ) (非即時)
評分方式: Tolerant , 記憶體限制: 512 MB
不公開 測資點 1 (20%): 3.0s , <1K
不公開 測資點 2 (20%): 1.0s , <1K
不公開 測資點 3 (20%): 1.0s , <1K
不公開 測資點 4 (20%): 1.0s , <1K
不公開 測資點 5 (20%): 1.0s , <1K
最近更新 : 2017-03-09 11:02

內容 :

背景

史蒂芙被王國政務工作忙昏頭,每次都要求效率的極限,即使不會玩遊戲,只要把政務工作處理到極致,想必這就是另一種人生價值。

題目描述 

回顧一個經典問題區間極大極小值詢問 RMQ,她收到下面這一份代碼

#include <bits/stdc++.h>
using namespace std;

unsigned int seed = 0;
unsigned int p_random() {return seed = (seed*9301+49297);}

unsigned int A[5000005];
int main() {
int N, M, S, x, y;
unsigned int hash = 0;
scanf("%d %d %d", &N, &M, &S);
seed = S;
for (int i = 1; i <= N; i++)
A[i] = p_random();
for (int i = 0; i < M; i++) {
x = p_random()%N+1, y = p_random()%N+1;
if (x > y) swap(x, y);
unsigned int max_val = A[x];
for (int j = x; j <= y; j++)
max_val = max(max_val, A[j]);
hash ^= max_val;
}
printf("%lu\n", hash);
return 0;
}

「給定 $N$ 個整數、$M$ 個詢問操作、$S$ 為亂數種子,接著產生 $N$ 個數字,對於接下來 $M$ 個詢問,每一個詢問兩個整數,輸出區間內的最大值。」這對曾經的史蒂芙而言,用過 Segment Tree、Sparse Table、Unrolled Linked List 解決過,時間、空間複雜度都非常優秀。

現在的工作就是加速這一份代碼。

輸入說明 :

只有一組測資,每一組測資只包含三個整數 $N, \; M, \; S$。

輸出說明 :

對於每組測資輸出一行一個整數。

範例輸入 : help
若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
8 5 10
範例輸出:
4049919279
提示 :

按照上述代碼,產生 8 個整數的序列如下

A[1 ... 8] =
142307, 1323646704, 1861772865, 3336296486, 4049919279, 1436077356, 3902214189, 202056986

接著詢問 5 個區間最大值,分別詢問 [1, 4], [2, 7], [5, 8], [3, 6], [1, 4] 答案分別為 33336296486, 4049919279, 40449192779, 4044919279, 3336296486,最後輸出 5 個答案的 XOR 結果。

  • 期望解法的時間複雜度為$O(N + M)$、空間複雜度 $O(N + M)$

 

標籤:
RMQ
出處:
(管理:morris1028)

本題狀況 本題討論 排行