背景

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

題目描述 

回顧一個經典問題區間極大極小值詢問 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 解決過，時間、空間複雜度都非常優秀。

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