题号:NC21118
时间限制:C/C++/Rust/Pascal 5秒,其他语言10秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld
题目描述
小睿睿的n个妹纸排成一排,每个妹纸有一个颜值val[i]。有m个询问,对于每一个询问,小睿睿想知道区间[L,R]颜值最高而编号最小的妹纸是哪一个
对于妹纸们的颜值val[i],其生成函数为:
void generate_array(int n,int seed)
{
unsigned x = seed;
for (int i=1;i<=n;++i)
{
x ^= x << 13;
x ^= x >> 17;
x ^= x << 5;
val[i]=x%100;
}
}
对于每一组询问,区间[L,R]的生成函数为:
void generate_ask(int n,int m,int seedx,int seedy)
{
unsigned x=seedx,y=seedy;
for (int i=1;i<=m;++i)
{
x ^= x << 13;
x ^= x >> 17;
x ^= x << 5;
y ^= y << 13;
y ^= y >> 17;
y ^= y << 5;
L=(x^lastans)%n+1,R=(y^lastans)%n+1;
if (L>R)swap(L,R);
//解决询问
}
}
其中lastans为上个询问的答案,对于第一个询问,lastans为0
输入描述:
第1行2个整数n,m,分别表示序列长度和询问次数
第2行3个整数seed,seedx,seedy,意义如题所示
输出描述:
一行一个整数,表示所有询问的答案的异或和
示例1
说明
生成序列:
7 11 47 53 3 7 63 36 55 55
各组询问及答案:
询问:4 6
该询问答案:4
询问:2 6
该询问答案:4
询问:2 2
该询问答案:2
询问:4 8
该询问答案:7
询问:1 9
该询问答案:7
所有询问的答案的异或和:2
备注:
对于30%的数据,n,m<=1000
对于50%的数据,m<=1000000
对于100%的数据,n<=100000,m<=10000000,seedx,seedy,seed<=1000