b494: 史蒂芙的修羅道
標籤 : RMQ
通過比率 : 76% (16 人 / 21 人 ) (非即時)
評分方式:
Tolerant

最近更新 : 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$。

  • $ 1 \le N, M \le 5000000$
  • $0 \le S \le 2147483647$
輸出說明

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

範例輸入
8 5 10
範例輸出
4049919279
測資資訊:
記憶體限制: 512 MB
不公開 測資點#0 (20%): 3.0s , <1K
不公開 測資點#1 (20%): 1.0s , <1K
不公開 測資點#2 (20%): 1.0s , <1K
不公開 測資點#3 (20%): 1.0s , <1K
不公開 測資點#4 (20%): 1.0s , <1K
提示 :

按照上述代碼,產生 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 (碼畜)
]
編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」