max
题目描述
小h 的男朋友送给小h 一个长度为nn的序列，并且刁难小h 要她找出其中mm个区间的最大值。
小h 不会做，于是向你求助。
输入
为了避免输入数据过大，本题使用如下方法进行输入：
第一行两个数n,mn,m。其中保证n=2k,k∈Nn=2k,k∈N。
第二行三个数，分别表示gen,p1,p2gen,p1,p2。
接下来生成nn个数，表示长度为nn的序列。
接下来生成2m2m个数，每次两个，分别表示mm个区间的左右端点。若第一个数大于第二个数，则交换这两个数。
生成一个数的方法为调用number() 函数，其返回值为当前生成的数：
int gen, p1, p2;
int number( ){
gen = (1LL * gen * p1 ) ^ p2;
return (gen & (n - 1 )) + 1;
}
下发文件中将包含示例程序以便理解输入格式。
输出
为了避免输出数据过大，本题使用如下方法进行输出：
设ansiansi为第ii个区间的最大值，你只需要输出一个数：
n∑i=1ansi×pn−i+11 mod p2∑i=1nansi×p1n−i+1 mod p2
下发文件中将包含示例程序以便理解输出格式。
样例输入
<span style="color:#333333"><span style="color:#333333">输入样例1
4 5
32 17 19
输入样例2
8388608 8000000
95 1071 1989</span></span>样例输出
<span style="color:#333333"><span style="color:#333333">输出样例1
17
输出样例2
153</span></span>提示
本题共十个数据，n,mn,m的范围如下表：
|
数据点 |
nn |
mm |
|
1 |
8 |
8 |
|
2 |
64 |
50 |
|
3 |
128 |
100 |
|
4 |
1024 |
1000 |
|
5 |
4096 |
4800 |
|
6 |
65536 |
65000 |
|
7 |
262144 |
260000 |
|
8 |
1048576 |
1000000 |
|
9 |
8388608 |
7000000 |
|
10 |
8388608 |
8000000 |
来源
solution
好暴力的题
正常线段树需要卡卡常
zkw线段树：hahaha
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int n, m;
int gen, p1, p2;
int number() {
gen = (1LL * gen * p1) ^ p2;
return (gen & (n - 1)) + 1;
}
const int Maxn = 1e7 + 5;
int a[Maxn],l[Maxn],r[Maxn],ans[Maxn],tr[Maxn*8],flag[Maxn];
int M;
int main()
{
scanf("%d%d", &n, &m);
scanf("%d%d%d", &gen, &p1, &p2);
for(M=1;M<=n;M<<=1);
for (int i=1;i<=n;i++){
a[i]=number();tr[M+i]=a[i];
}
for(int i=M;i;i--)tr[i]=max(tr[i<<1],tr[i<<1|1]);
for (int i=1;i<=m;i++) {
l[i]=number(),r[i]=number();
if (l[i]>r[i]) swap(l[i], r[i]);
}
int len,x,aa=0;
for(int i=1;i<=m;i++){
l[i]--,r[i]++;
aa=0;
for(int s=l[i]+M,t=r[i]+M;s^t^1;s>>=1,t>>=1){
if(~s&1)aa=max(aa,tr[s^1]);//s lson
if(t&1)aa=max(aa,tr[t^1]);//t rson
}
ans[i]=aa;
}
int sum = 0;
for (int i = 1; i <= m; ++i)
(sum += 1LL * ans[i] * p1 % p2) %= p2;
printf("%d
",sum);
return 0;
}