1707E - Replace - CodeForces Solution

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1e5+5;
int n,q,a[N],ql,qr;
int lg[N];ll ans;

inline void read(int &x){
	int f=1;char c;
	for(x=0,c=getchar();c<'0'||c>'9';c=getchar()) if(c=='-') f=-1;
	for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48); x*=f; 
} 
inline int mx(int _x,int _y){return _x>_y?_x:_y;} 
inline int mn(int _x,int _y){return _x<_y?_x:_y;}
inline int ab(int _x){return _x<0?-_x:_x;}
struct REG{int l;int r;};
inline REG operator + (REG A,REG B){return (REG){mn(A.l,B.l),mx(A.r,B.r)};}
REG f[35][17][N];
inline REG qReg(int t,int l,int r){
	if(l>=r) return {1000000,0};
	--r;int k=lg[r-l+1];
	return f[t][k][l]+f[t][k][r-(1<<k)+1];
}
int main(){
	read(n);read(q);
	for(int i=1;i<=n;i++) read(a[i]);
	
	lg[1]=0;for(int i=2;i<=100000;i++) lg[i]=lg[i>>1]+1;
	if(n==1){//Special Case
		for(int i=1;i<=q;i++) puts("0");
		return 0;
	}
	
	for(int i=1;i<n;i++) f[0][0][i]=(REG){mn(a[i],a[i+1]),mx(a[i],a[i+1])};
	for(int j=1;(1<<j)<=n;j++)
		for(int i=1;i+(1<<j)-1<=n;i++)
			f[0][j][i]=f[0][j-1][i]+f[0][j-1][i+(1<<(j-1))];
	for(int t=1;t<=34;t++){
		for(int i=1;i<n;i++) f[t][0][i]=qReg(t-1,f[t-1][0][i].l,f[t-1][0][i].r);
		for(int j=1;(1<<j)<=n;j++)
			for(int i=1;i+(1<<j)-1<=n;i++)
				f[t][j][i]=f[t][j-1][i]+f[t][j-1][i+(1<<(j-1))];
	}
	
	while(q--){
		read(ql);read(qr);
		if(ql==qr){puts("-1");continue;}
		if(ql==1&&qr==n){puts("0");continue;}
		ans=0;
		for(int i=34;i>=0;i--){
			REG Tmp=qReg(i,ql,qr);
			if(Tmp.l!=1||Tmp.r!=n){
				ql=Tmp.l;qr=Tmp.r;
				ans+=(1ll<<i); 
			}
		}
		if(ans==(1ll<<35)-1) puts("-1");
		else printf("%lld\n",ans+1);
	}
	return 0;
}