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

下发文件中将包含示例程序以便理解输出格式。

 

样例输入

输入样例14 532 17 19输入样例28388608 800000095 1071 1989

样例输出

输出样例117输出样例2153

提示

 

本题共十个数据，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
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          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\n",sum); return 0;}