科技の代码库

\(O(n)-O(1)\) RMQ

#define cin Fastio::cin
#define cout Fastio::cout
#define endl Fastio::endl
int n,q,tp,stk[64];
long long a[100000008],st[1562506][21];
unsigned long long val[100000008];
int ask(int l,int r)
{if(l>r)return 0;int d=__lg(r-l+1);return max(st[l][d],st[r-(1<<d)+1][d]); 
}
int query(int l,int r){return a[l+__builtin_ctz(val[r]>>l)];}
int main()
{cin>>n>>q;for(int i=0;i<n;i++){cin>>a[i];st[i>>6][0]=(i&63)?(val[i]=val[i-1],max(st[i>>6][0],a[i])):(val[i]=0,tp=-1,a[i]);while((~tp)&&a[stk[tp]]<a[i]){val[i]^=(1ull<<stk[tp]);tp--;}stk[++tp]=i;val[i]|=(1ull<<i);}for(int i=1;i<21;i++)for(int j=1;j<=(n>>6)-(1<<i)+1;j++)st[j][i]=max(st[j][i-1],st[j+(1<<(i-1))][i-1]);for(int i=1,l,r;i<=q;i++){cin>>l>>r;l--;r--;cout<<(((l^r)>>6)?max(ask((l>>6)+1,(r>>6)-1),max(query(l,((l>>6)+1)<<6),query(r>>6<<6,r))):query(l,r))<<'\n';}
}