怎么让客户做网站,手机网站如何优化,电子个人简历手机版免费,口碑营销案例题干#xff1a;
链接#xff1a;https://ac.nowcoder.com/acm/contest/371/B 来源#xff1a;牛客网
小睿睿的n个妹纸排成一排#xff0c;每个妹纸有一个颜值val[i]。有m个询问#xff0c;对于每一个询问#xff0c;小睿睿想知道区间[L,R]颜值最高而编号最小的妹纸是…题干
链接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 i1;in;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 xseedx,yseedy;for (int i1;im;i){x ^ x 13;x ^ x 17;x ^ x 5;y ^ y 13;y ^ y 17;y ^ y 5;L(x^lastans)%n1,R(y^lastans)%n1;if (LR)swap(L,R);//解决询问}
} 其中lastans为上个询问的答案对于第一个询问lastans为0
输入描述:
第1行2个整数n,m分别表示序列长度和询问次数第2行3个整数seed,seedx,seedy意义如题所示
输出描述:
一行一个整数表示所有询问的答案的异或和
示例1
输入
复制
10 5
3 5 7
输出
复制
2
说明
生成序列7 11 47 53 3 7 63 36 55 55各组询问及答案询问4 6该询问答案4询问2 6该询问答案4询问2 2该询问答案2询问4 8该询问答案7询问1 9该询问答案7所有询问的答案的异或和2
示例2
输入
复制
100000 10000000
1 2 3
输出
复制
5042
备注:
对于30%的数据n,m1000对于50%的数据m1000000对于100%的数据n100000,m10000000,seedx,seedy,seed1000
解题报告 跟一般的ST表不同这里的ST表不是维护一个最大值而是维护最大值所对应的下标因为题目中说要维护的答案是下标如果有多个最大值的话返回左边的下标。而通过ST表的原理我们不难得出结论对于下标也同样可以维护。
AC代码
#includecstdio
#includeassert.h
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includectime
#includestring
#includecmath
#includecstring
#define ll long long
#define fi first
#define se second
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX 6e5 6;
int lastans 0;
int seed,seedx,seedy,n,m;
int val[MAX],Log[MAX];
int dp[MAX][25];
void generate_array(int n,int seed) {unsigned x seed;for (int i1; in; i) {x ^ x 13;x ^ x 17;x ^ x 5;val[i]x%100;}
}
inline int fff(int x,int y) {if(val[x] val[y]) return y;if(val[x] val[y]) return x;return xy ? x : y;
}
int cal(int l,int r) {int k Log[r-l1];return fff(dp[l][k],dp[r- (1k) 1][k]);
}
int generate_ask(int n,int m,int seedx,int seedy) {unsigned xseedx,yseedy;int L,R;int ans 0;for (int i1; im; i) {x ^ x 13;x ^ x 17;x ^ x 5;y ^ y 13;y ^ y 17;y ^ y 5;L(x^lastans)%n1,R(y^lastans)%n1;if (LR)swap(L,R);//解决询问lastans cal(L,R);ans ^ lastans ;}return ans;
}
void init() {for(int i 1; in; i) dp[i][0] i;for(int j 1; (1j) n; j) {for(int i 1; in; i) {//枚举数字dp[i][j] fff(dp[i][j-1],dp[i(1(j-1))][j-1]);}}//找到小于等于i的那个二进制for(int i 1; in; i) {int k 0;while((1(k1)) i) k;Log[i] k;}}
int main()
{cinnmseedseedxseedy;int ST clock();int ans 0;generate_array(n,seed);init();cout generate_ask(n,m,seedx,seedy) endl;return 0 ;
}
