Minimum and Maximum - 题目 - Infinity Online Judge

题目描述

给定长度为 $n$ 的序列 $[a_1,a_2,\dots ,a_n]$。

$m$ 次询问，每次给出四个正整数 $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]\ (1\le l\le r\le n)$ 满足 $a_l,a_{l+1},\dots,a_r$ 中的最大值属于 $[L_1,R_1]$、最小值属于 $[L_2,R_2]$。

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

输入格式

第一行两个正整数 $n,m$。

接下来一行 $n$ 个正整数 $a_1\sim a_n$。

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

输出格式

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

样例 #1

样例输入 #1

5 5
2 4 1 3 5
1 5 1145141919810

样例输出 #1

样例 #2

样例输入 #2

10 20000000
1 3 4 10 5 5 2 7 10 7
1 10 23333333333333333

样例输出 #2

548722417

提示

样例 1 解释

五次询问的 $(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)$，答案分别为 $15,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;
}

数据范围

本题有四个子任务，时间限制 $5$ 秒。

所有数据均满足：$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}$。

子任务 $1$（$5$ 分）：$n,m,a_i,q\le 10$。
子任务 $2$（$20$ 分）：$n\le 10^4$。
子任务 $3$（$20$ 分）：$a_i,q\le 10$。
子任务 $4$（$55$ 分）：无特殊限制。

Infinity Online Judge

InfOJ

InfOJ Beginner Round 3

D. Minimum and Maximum