C++14(g++5.4) 解法, 执行用时: 1708ms, 内存消耗: 9084K, 提交时间: 2019-03-21 17:48:18

#include<cstdio>
#include<iostream>
using namespace std;
int value[100005]={0},n,m,seed,seedx,seedy,st[500005][20]={0},lo[100005];
int ans,lastans;
void get_array()
{
	unsigned x=seed;
	for (int i=1;i<=n;i++)
	{
		x^=x<<13;
		x^=x>>17;
		x^=x<<5;
		value[i]=x%100;
		x%=1ll<<40;
	}
}
int ask(int l,int r)
{
	int len=r-l+1;
	if (value[st[l][lo[len]]]>=value[st[r-(1<<lo[len])+1][lo[len]]]) return st[l][lo[len]];else return st[r-(1<<lo[len])+1][lo[len]];
}
void get_st()
{
	for (int i=1;i<=n;i++) st[i][0]=i;
	for (int i=1;i<=lo[n];i++) for (int j=1;j<=n;j++) if (value[st[j][i-1]]>=value[st[j+(1<<(i-1))][i-1]]) st[j][i]=st[j][i-1];else st[j][i]=st[j+(1<<(i-1))][i-1];
}
void get_ask()
{
	unsigned x=seedx,y=seedy;
	int l,r,temp;
	for (int i=1;i<=m;i++)
	{
		x^=x<<13;
		x^=x>>17;
		x^=x<<5;
		x%=1ll<<40;
		y^=y<<13;
		y^=y>>17;
		y^=y<<5;
		y%=1ll<<40;
		l=(x^lastans)%n+1;
		r=(y^lastans)%n+1;
		if (l>r)
		{
			temp=l;
			l=r;
			r=temp;
		}
		lastans=ask(l,r);
		ans^=lastans;
	}
}
int main()
{
	scanf("%d%d%d%d%d",&n,&m,&seed,&seedx,&seedy);
	for (int i=0;i<20;i++) for (int j=(1<<i);j<(1<<(i+1))&&j<=n;j++) lo[j]=i;
	get_array();
	get_st();
	get_ask();
	printf("%d",ans);
}

C++11(clang++ 3.9) 解法, 执行用时: 638ms, 内存消耗: 7148K, 提交时间: 2019-02-26 21:53:46

#include<bits/stdc++.h>
#define REP(i, a, b) for(unsigned i(a); i <= (b); ++i)
const int N(1e5 + 5);
unsigned w[N], st[18][N];
inline unsigned get(unsigned i, unsigned j){
    if(w[i] == w[j])return i < j ? i : j;
    return w[i] > w[j] ? i : j;
}
int main(){
    unsigned n, m, a, b, c;
    scanf("%u%u%u%u%u", &n, &m, &a, &b, &c);
    REP(i, 1, n){
        a ^= a << 13, a ^= a >> 17, a ^= a << 5;
        st[0][i] = i, w[i] = a % 100;
    }
    REP(i, 1, 17)REP(j, 1 << i, n)st[i][j] = get(st[i - 1][j], st[i - 1][j - (1 << i - 1)]);
    unsigned ans = 0, res = 0;
    while(m--){
        b ^= b << 13;
        b ^= b >> 17;
        b ^= b << 5;
        c ^= c << 13;
        c ^= c >> 17;
        c ^= c << 5;
        unsigned l = (b ^ ans) % n + 1, r = (c ^ ans) % n + 1, k;
        if(l > r)std::swap(l, r);
        k = std::__lg(r - l + 1);
        res ^= ans = get(st[k][r], st[k][l + (1 << k) - 1]);
    }
    std::cout << res;
    return 0;
}