西邮 问题 C: 给你一个666

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node
{
    int pos,v;
}s[50010];
int n,t;
bool cmp(node d,node f)
{
    if(d.v!=f.v) return d.v<f.v;
    else return d.pos<f.pos;
}
map<pair<int,int>,pair<int,int> >m;
void mul(int l,int r,int &x,int &y)
{
    int a1=0,a2=0,b1=0,b2=0,tx,ty;
    a1=l>>3;
    a2=l-(a1<<3);
    b1=r>>3;
    b2=r-(b1<<3);
    tx=a2*b1,ty=a1*b2;
    x=min(tx,ty)*l;
    if(x<1||x>n) x=1;
    y=max(tx,ty)*r;
    if(y<1||y>n) y=n;
}
int main()
{
    cin>>n>>t;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&s[i].v);
        s[i].pos=i;
    }
    sort(s+1,s+1+n,cmp);
    for(int i=0;i<1<<7;i++)
    {
        for(int j=i;j<1<<7;j++)
        {
            int x,y;
            mul(i,j,x,y);
            int p,q;
            for(int ii=1;ii<=n;ii++)
            {
                if(s[ii].pos>=x&&s[ii].pos<=y)
                {
                    p=s[ii].v;
                    break;
                }
            }
            for(int ii=n;ii>=1;ii--)
            {
                if(s[ii].pos>=x&&s[ii].pos<=y)
                {
                    q=s[ii].v;
                    break;
                }
            }
            m[make_pair(i,j)]=make_pair(q,p);
        }
    }
    while(t--)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        if(x>y) swap(x,y);
        printf("%d %d\n",m[make_pair(x,y)].first,m[make_pair(x,y)].second);
    }
    return 0;
}