Background

Due to Luogu limitations, the testdata for this problem has been reduced. For the full set of testdata, please go to InfOJ.

Problem Description

Given a sequence of length $n$, $[a_1,a_2,\dots ,a_n]$.

There are $m$ queries. Each query gives four positive integers $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)$. You need to count how many intervals $[l,r]\ (1\le l\le r\le n)$ satisfy that, among $a_l,a_{l+1},\dots,a_r$, the maximum value lies in $[L_1,R_1]$ and the minimum value lies in $[L_2,R_2]$.

The number of queries is very large, so the queries are generated inside the program. Please read the code in the Hint section by yourself.

Input Format

The first line contains two positive integers $n,m$.

The next line contains $n$ positive integers $a_1\sim a_n$.

The next line contains three positive integers $p,q,seed$, which are the parameters of the data generator. You do not need to understand the detailed running process of the data generator. You only need to know that if the queries are generated correctly, then $L_1,R_1,L_2,R_2\in [p,q]$ must hold.

Output Format

Let the answer to the $i$-th query be $ans_i$. Output one line with one integer, the value of $\operatorname{xor}_{i=1}^m (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

Hint

Explanation for Sample 1

For the five queries, $(L_1,R_1,L_2,R_2)$ are respectively $(1,5,1,5),(1,2,2,4),(3,4,2,2),(2,4,2,2),(2,5,2,5)$, and the answers are respectively $15,1,1,2,6$.

Output $(1\times 15)\ \mathrm{xor}\ (2\times 1)\ \mathrm{xor}\ (3\times 1)\ \mathrm{xor}\ (4\times 2)\ \mathrm{xor}\ (5\times 6)=24$.

Sample Program

Below is the sample program we provide. You can directly write your program based on it.

#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;//read 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){
	//pass l1,r1,l2,r2 as parameters to get one query
	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 stores your answer*/;
		xorsum^=ans*i;
	}
	cout<<xorsum;
}

Constraints

This problem has four subtasks. Subtask 1 has a time limit of $0.5$ seconds, and the other subtasks have a time limit of $5$ seconds.

All testdata satisfies: $1\le n\le 10^5$，$1\le m\le 2\times 10^7$，$1\le a_i\le 4000$，$1\le p\lt q\le 4000$，$0\le seed\lt 2^{64}$.

• Subtask $1$ ($5$ points): $n,m,a_i,q\le 10$.
• Subtask $2$ ($20$ points): $n\le 10^4$.
• Subtask $3$ ($20$ points): $a_i,q\le 10$.
• Subtask $4$ ($55$ points): No special constraints.

Translated by ChatGPT 5