定义一个6位二进制数上的运算 @ : a@b=(c,d)。其中 c = a的高3位b的低3位 ; d = a的低3位b的高3位。例如 010 001 @ 011 001 = (010001 , 001011) = (21,13) = (2,3) 。 给出了两个操作数a和b，以及一个数列 x1,x2,x3 ... xn。假设a@b的结果(c,d),数列在区间 [ min(c,d)*min(a,b) ,max(c,d)*max(a,b) ]上的最小值和最大值。如果上述区间上的最大值和最小值可以代表666的程度，请你每组操作数都要计算出这两个最值。
输入格式:
第一行输入两个正整数 n,q,分别表示数列数字的个数和询问个数.其中1<=n<=50 000，1<=q<=100 000。 第二行输入n个非负整数,表示数列中的元素x1,x2 ... xn, 每个元素都在int类型的范围内。 接下来q行,每行给出一对非负整数，a，b，其意义见题面。本题保证所有的a和b均为6位无符号整数。
输出格式:
对于每个询问,输出一对整数,分别表示目标区间上的最大值和最小值.每个询问的结果单独占一行。 请不要输出多余的空行。
输入样例:
1. 12 1 2. 5 2 3 4 5 6 7 8 1 6 5 1 3. 1 8
输出样例:
8 2
注意:
min(x,y)表示x和y的最小值, max(x,y)表示x和y的最大值.区间下标从1开始。 样例： 数列在区间[1,8]上的所有元素为{5 2 3 4 5 6 7 8}，最大值为8，最小值为2。 若左边界越界则取1，若右边界越界则取n。
思路：先预处理所有可能的答案，然后直接查表
时间复杂度：4096 * 4096 + 100000
#include<bits/stdc++.h> using namespace std; const int N = 1e6 + 10,inf = 0x3f3f3f3f; const int M = 4096 + 10; int maxx[M][M],minn[M][M]; int f[N],n; void check(int a,int b,int &l,int &r) { int a1,a2,b1,b2; a1 = a >> 3;//a的高3位 a2 = a - (a1 << 3);//a的低3位 b1 = b >> 3;//b的高三位 b2 = b - (b1 << 3);//b的低三位 l = a1 * b2;//c r = a2 * b1;//d if(l > r) swap(l,r); l *= min(a,b); r *= max(a,b); if(l < 1 || l > n) l = 1; if(r < 1 || r > n) r = n; } int find_max(int l,int r) { int maxc = -1; for(int i=l;i<=r;i++) maxc = max(maxc,f[i]); return maxc; } int find_min(int l,int r) { int minc = inf; for(int i=l;i<=r;i++) minc = min(minc,f[i]); return minc; } int main() { int q,l,r; cin>>n>>q; for(int i=1;i<=n;i++) scanf("%d",&f[i]); for(int i=0;i<=64;i++)//预处理 { for(int j=0;j<=64;j++) { check(i,j,l,r); maxx[l][r] = find_max(l,r); minn[l][r] = find_min(l,r); } } int a,b; while(q -- ) { scanf("%d%d",&a,&b); check(a,b,l,r); printf("%d %d\n",maxx[l][r],minn[l][r]); } return 0; }
