cf622c

liu_zheng · 2025-08-02 17:39:24 · 个人记录

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
int a[maxn];
int lg[maxn];
int fmax1[maxn][25];
int fmin1[maxn][25]; 
int x[maxn];
int maxx[maxn];
int minn[maxn];
int n,m;
void q1(){
    for(int i=1;i<=n;i++){
        fmax1[i][0]=i;
    }
    for(int i=2;i<=n;i++){
        lg[i]=lg[i/2]+1;
    }
    for(int j=1;(1<<j)<=n;j++){
        for(int i=1;i+(1<<j)-1<=n;i++){
            if(a[fmax1[i][j-1]]<=a[fmax1[i+(1<<(j-1))][j-1]]){
                fmax1[i][j]=fmax1[i+(1<<(j-1))][j-1];
            }else fmax1[i][j]=fmax1[i][j-1];
        }
    }
    return ;
}
void q2(){
    for(int i=1;i<=n;i++){
        fmin1[i][0]=i;
    }
    for(int i=2;i<=n;i++){
        lg[i]=lg[i/2]+1;
    }
    for(int j=1;(1<<j)<=n;j++){
        for(int i=1;i+(1<<j)-1<=n;i++){
            if(a[fmin1[i][j-1]]<=a[fmin1[i+(1<<(j-1))][j-1]]){
                fmin1[i][j]=fmin1[i+(1<<(j-1))][j-1];
            }else fmin1[i][j]=fmin1[i][j-1];
        }
    }
    return ;
}
int out(int l,int r,int shu){
    int len=r-l+1;
    int k=lg[len];
    int ansmax=0,ansmin=0;
    if(a[fmax1[l][k]]<=a[fmax1[r-(1<<k)+1][k]]){
        ansmax=fmax1[r-(1<<k)+1][k];
    }
    else ansmax=fmax1[l][k];

    if(a[fmin1[l][k]]<=a[fmin1[r-(1<<k)+1][k]]){
        ansmin=fmin1[r-(1<<k)+1][k];
    }
    else ansmin=fmin1[l][k];

//  max(fmax1[l][k]],fmax1[r-(1<<k)+1][k]);
//  min(fmin11[l][k],fmin1[r-(1<<k)+1][k]);
    if(a[ansmax]==shu&&a[ansmin]==shu)return -1;
    else if(a[ansmax]==shu)return ansmin;
    else return ansmax;

}
int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    q1();
    q2();
    for(int i=1;i<=m;i++){
        int l,r;
        cin>>l>>r>>x[i];
        cout<<out(l,r,x[i])<<endl;
    }

    return 0;
}