问题 C: 给你一个666

问题 C: 给你一个666

苍茫大地一剑尽挽破，何处繁华笙歌落。斜倚云端千壶掩寂寞，纵使他人空笑我。

因为输入的两个数a和b都是6位无符号数，所以a和b所有情况一共有2^12=4k种情况，所以枚举所有可能的a和b将对应的最值提前打表求出来，然后询问的时候直接查表就行了。尽管如此，前两遍竟然时间超限！！！？？？最后，把cin，cout换掉就过了。

这是比较一般的思路，如果线段树和树状数组学的比较好的话，可以用线段树求解，但是有坑，所以操作需谨慎。

这里有详解哟：

题目描述

Tongtong非常喜欢用“say 666”的方式来打招呼，因此热爱数学的他找到了一个说666的新方式。Tongtong构造了一个数学上很6的运算。定义一个6位二进制数上的运算 @ : a@b=(c,d)。其中 c = a的高3位*b的低3位 ; d = a的低3位*b的高3位。例如 010 001 @ 011 001 = (010*001 , 001*011) = (2*1,1*3) = (2,3) 。
Tongtong给出了两个操作数a和b。以及一个数列 x1,x2,x3 ... xn ,假设a@b的结果(c,d),Tongtong非常关心数列在区间 [ min(c,d)*min(a,b) ,max(c,d)*max(a,b) ]上的最小值和最大值，Tongtong认为上述区间上的最大值和最小值可以代表666的程度，所以每组操作数都要计算出这两个最值。由于时间紧迫，他需要你来帮助他完成这个工作。

输入

第一行输入两个正整数 n,q,分别表示数列数字的个数和询问个数.其中1<=n<=50 000，1<=q<=100 000。
第二行输入n个非负整数,表示数列中的元素x1,x2 ... xn, 每个元素都在int类型的范围内。
接下来q行,每行给出一对非负整数，a，b，其意义见题面。本题保证所有的a和b均为6位无符号整数。

输出

对于每个询问,输出一对整数,分别表示目标区间上的最大值和最小值.每个询问的结果单独占一行。
请不要输出多余的空行。

样例输入

复制样例数据

12 1
5 2 3 4 5 6 7 8 1 6 5 1
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。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <string>
#include <stack>
#include <queue>
#include <map>
#include <vector>
#include <bitset>
#include <set>
#include <utility>
#include <sstream>
#include <iomanip>
#define inf 1000000007
typedef long long int ll;
using namespace std;
int s[50050],ma[5010][5010],mi[5010][5010];
int n,q,r,l;
void pdl(int &ll){if(ll<1||ll>n)ll=1;
}
void pdr(int &rr){if(rr<1||rr>n)rr=n;
}
void qdqj(int a,int b){int ar,al,br,bl,c,d;ar=a>>3;al=a-(ar<<3);br=b>>3;bl=b-(br<<3);c=ar*bl;d=al*br;if(c>d)swap(c,d);l=c*min(a,b);r=d*max(a,b);pdl(l);pdr(r);
}
int getmax(){int maa=-1;for(int i=l;i<=r;i++)maa=max(maa,s[i]);return maa;
}
int getmin(){int mii=inf;for(int i=l;i<=r;i++)mii=min(mii,s[i]);return mii;
}
int main(){int i,a,b,j,k;scanf("%d%d",&n,&q);//cin>>n>>q;for(i=1;i<=n;i++)scanf("%d",&s[i]);//cin>>s[i];for(j=0;j<=64;j++){for(k=0;k<=64;k++){qdqj(j,k);ma[l][r]=getmax();mi[l][r]=getmin();}}while(q--){scanf("%d%d",&a,&b);//cin>>a>>b;qdqj(a,b);printf("%d %dn",ma[l][r],mi[l][r]);//cout<<ma[l][r]<<' '<<mi[l][r]<<endl;}return 0;
}