题解 | 【模板】二分

#include <bits/stdc++.h>
using namespace std;

inline int read(){
    int s =  0,w =  1;char c=  getchar();
    while(!isdigit(c)) w = c  =='-' ? -w :w,c = getchar();
    while(isdigit(c)) s  =  (s<<3) + (s<<1) + c - '0',c = getchar();
    return s * w;
}

inline void out(int x){
    if(x<0) putchar('-'),x =  -x;
    char s[40];int top  =   0;
    do{s[top++]=x%10+'0',x/=10;}while(x);
    while(top) putchar(s[--top]);
    puts("");
}

const int N  =  1e5 + 10;
int n,q,a[N];

int main(){
    n  = read(),q = read();
    for(int i =   0;i<n;a[i++]=read());
    while(q--){
        int op,L,R,x;
        op  = read(),L= read(),R = read(),x = read();
        R--;
        if(op==1){
            //找到第一个大于等于x的
            int l  =  L-1,r =  R+1;
            while(l+1<r){
                int m  =  l + r >> 1;
                if(a[m]>=x) r =  m;
                else l  =  m;
            }
            out(r<=R?a[r]:-1);
        }
        else if(op==2){
            //找到第一个大于x的
            int l  =  L-1,r =  R+1;
            while(l+1<r){
                int m  =   l + r >> 1;
                if(a[m]>x) r =   m;
                else l  =  m;
            }
            out(r<=R?a[r]:-1);
        }
        else if(op==3){
            //找到最后一个小于x的
            int l  =  L-1,r =  R+1;
            while(l+1<r){
                int m  =  l  + r >> 1;
                if(a[m]<x)  l  =   m;
                else r  =  m;
            }
            out(l>=L?a[l]:-1);
        }
        else{
            //找到最后一个小于等于x的
            int l  =  L-1,r =  R+1;
            while(l+1<r){
                int m  =  l + r >> 1;
                if(a[m]<=x) l   =  m;
                else r =   m;
            }
            out(l>=L?a[l]:-1);
        }
    }

    return 0;
}