#P8911. [RC-06] Minimum and Maximum

[RC-06] Minimum and Maximum

题目背景

受洛谷限制,本题数据有所删减。评测全套数据请到 InfOJ

题目描述

给定长度为 nn 的序列 [a1,a2,,an][a_1,a_2,\dots ,a_n]

mm 次询问,每次给出四个正整数 $L_1,R_1,L_2,R_2\ (1\le L_1\le R_1\le 4000,1\le L_2\le R_2\le 4000)$,问有多少个区间 [l,r] (1lrn)[l,r]\ (1\le l\le r\le n) 满足 al,al+1,,ara_l,a_{l+1},\dots,a_r 中的最大值属于 [L1,R1][L_1,R_1]、最小值属于 [L2,R2][L_2,R_2]

询问次数很大,所以询问是在程序内生成的。请自行阅读提示说明一栏的代码。

输入格式

第一行两个正整数 n,mn,m

接下来一行 nn 个正整数 a1ana_1\sim a_n

接下来一行三个正整数 p,q,seedp,q,seed,为数据生成器的参数。你不需要理解数据生成器具体的运行过程,你只需要知道,如果正确生成了询问的话,一定有 L1,R1,L2,R2[p,q]L_1,R_1,L_2,R_2\in [p,q]

输出格式

设第 ii 个询问的答案为 ansians_i。输出一行一个整数,为 xori=1q(i×ansi)\operatorname{xor}_{i=1}^q (i\times ans_i) 的值。

5 5
2 4 1 3 5
1 5 1145141919810
24
10 20000000
1 3 4 10 5 5 2 7 10 7
1 10 23333333333333333
548722417

提示

样例 1 解释

五次询问的 (L1,R1,L2,R2)(L_1,R_1,L_2,R_2) 分别为 (1,5,1,5),(1,2,2,4),(3,4,2,2),(2,4,2,2),(2,5,2,5)(1,5,1,5),(1,2,2,4),(3,4,2,2),(2,4,2,2),(2,5,2,5),答案分别为 15,1,1,2,615,1,1,2,6

输出 $(1\times 15)\ \mathrm{xor}\ (2\times 1)\ \mathrm{xor}\ (3\times 1)\ \mathrm{xor}\ (4\times 2)\ \mathrm{xor}\ (5\times 6)=24$。

样例程序

下面是我们提供的样例程序,你可以直接以其为基础编写你的程序。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
namespace Generator{
typedef unsigned long long ull;
typedef __uint128_t L;
ull seed;
int p,q;
struct FastMod {
    ull b, m;
    FastMod(ull b) : b(b), m(ull((L(1) << 64) / b)) {}
    ull reduce(ull a) {
        ull q = (ull)((L(m) * a) >> 64);
        ull r = a - q * b; // can be proven that 0 <= r < 2*b
        return r >= b ? r - b : r;
    }
}F(2);
void init(){
	cin>>p>>q>>seed;//读入 p,q,seed 
	assert(p!=q);
	F=FastMod(q-p+1);
}
unsigned long long rd () {
	seed ^= (seed << 13);
	seed ^= (seed >> 7);
	seed ^= (seed << 17);
	return seed;
}
void getlr(int &l1,int &r1,int &l2,int &r2){
	//将 l1,r1,l2,r2 作为参数传入,即可得到一组询问 
	l1=F.reduce(rd())+p;
	r1=F.reduce(rd())+p;
	l2=F.reduce(rd())+p;
	r2=F.reduce(rd())+p;
	if(l1>r1)swap(l1,r1);
	if(l2>r2)swap(l2,r2);
}

}
int n,m,a[100005];
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	Generator::init();
	long long xorsum=0;
	for(int i=1,l1,r1,l2,r2;i<=m;i++){
		Generator::getlr(l1,r1,l2,r2);
		long long ans=/*ans保存你的答案*/;
		xorsum^=ans*i;
	}
	cout<<xorsum;
}

数据范围

本题有四个子任务。子任务一时间限制 0.50.5 秒,其它子任务时间限制 55 秒。

所有数据均满足:1n1051\le n\le 10^51m2×1071\le m\le 2\times 10^71ai40001\le a_i\le 40001p<q40001\le p\lt q\le 40000seed<2640\le seed\lt 2^{64}

  • 子任务 1155 分):n,m,ai,q10n,m,a_i,q\le 10
  • 子任务 222020 分):n104n\le 10^4
  • 子任务 332020 分):ai,q10a_i,q\le 10
  • 子任务 445555 分):无特殊限制。