链接: https://ac.nowcoder.com/acm/contest/371/B
小睿睿的 n 个妹纸排成一排, 每个妹纸有一个颜值 val[i]. 有 m 个询问, 对于每一个询问, 小睿睿想知道区间 [L,R] 颜值最高而编号最小的妹纸是哪一个
对于妹纸们的颜值 val[i], 其生成函数为:
- void generate_array(int n,int seed)
- {
- unsigned x = seed;
- for (int i=1;i<=n;++i)
- {
- x ^= x <<13;
- x ^= x>> 17;
- x ^= x <<5;
- val[i]=x%100;
- }
- }
对于每一组询问, 区间 [L,R] 的生成函数为:
- void generate_ask(int n,int m,int seedx,int seedy)
- {
- unsigned x=seedx,y=seedy;
- for (int i=1;i<=m;++i)
- {
- x ^= x << 13;
- x ^= x>> 17;
- x ^= x <<5;
- y ^= y << 13;
- y ^= y>> 17;
- y ^= y <<5;
- L=(x^lastans)%n+1,R=(y^lastans)%n+1;
- if (L>R)swap(L,R);
- // 解决询问
- }
- }
其中 lastans 为上个询问的答案, 对于第一个询问, lastans 为 0
输入描述:
第 1 行 2 个整数 n,m, 分别表示序列长度和询问次数
第 2 行 3 个整数 seed,seedx,seedy, 意义如题所示
输出描述:
一行一个整数, 表示所有询问的答案的异或和
示例 1
输入
10 5 3 5 7
输出
2
思路: 裸的 ST
- #include <cstdio>
- #include <map>
- #include <iostream>
- #include<cstring>
- #include<bits/stdc++.h>
- #define ll long long int
- #define M 6
- using namespace std;
- inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
- inline ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
- int moth[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
- int dir[4][2]={1,0 ,0,1 ,-1,0 ,0,-1};
- int dirs[8][2]={1,0 ,0,1 ,-1,0 ,0,-1, -1,-1 ,-1,1 ,1,-1 ,1,1};
- const int inf=0x3f3f3f3f;
- const ll mod=1e9+7;
- int val[100007];
- int f[100007][20];
- int L,R,lastans,ans;
- void generate_array(int n,int seed)
- {
- unsigned x = seed;
- for (int i=1;i<=n;++i)
- {
- x ^= x <<13;
- x ^= x>> 17;
- x ^= x <<5;
- val[i]=x%100;
- }
- }
- int maxn(int i,int j){
- if(val[i]>val[j]) return i;
- else if(val[i]<val[j]) return j;
- else return i>j?j:i;
- }
- void preST(int len){
- for(int i=1;i<=len;i++) f[i][0]=i;
- int k=log(len)/log(2)+1;
- for(int j=1;j<k;j++)
- for(int i=1;i<=(len-(1<<j)+1);i++)
- f[i][j]=maxn(f[i][j-1],f[i+(1<<(j-1))][j-1]);
- }
- int queryST(int l,int r){
- int k=log(r-l+1)/log(2);
- return maxn(f[l][k],f[r-(1<<k)+1][k]);
- }
- void generate_ask(int n,int m,int seedx,int seedy)
- {
- unsigned x=seedx,y=seedy;
- for (int i=1;i<=m;++i)
- {
- x ^= x <<13;
- x ^= x>> 17;
- x ^= x <<5;
- y ^= y << 13;
- y ^= y>> 17;
- y ^= y <<5;
- L=(x^lastans)%n+1,R=(y^lastans)%n+1;
- if (L>R)swap(L,R);
- // cout<<L<<" "<<R<<endl;
- lastans=queryST(L,R);
- // cout<<lastans<<endl;
- ans^=lastans;
- }
- cout<<ans<<endl;
- }
- int main(){
- iOS::sync_with_stdio(false);
- int seed,seedx,seedy;
- int n,m;
- while(cin>>n>>m){
- cin>>seed>>seedx>>seedy;
- generate_array(n,seed);
- lastans=0;
- int tt=m;
- ans=0;
- preST(n);
- generate_ask(n,tt,seedx,seedy);
- }
- }
牛客 OI 周赛 7 - 提高组 B 小睿睿的询问(ST 打表)
来源: http://www.bubuko.com/infodetail-2964782.html