void init(){ Log[0] = -1; for(int i=1;i<=n;i++)Log[i] = Log[i>>1]+1; for(int i=n;i;i--){ stM[i][0] = stN[i][0] = a[i]; for(int j=1;(i+(1<<j)-1)<=n;j++){ stM[i][j] = max(stM[i][j-1],stM[i+(1<<j-1)][j-1]); stN[i][j] = min(stN[i][j-1],stN[i+(1<<j-1)][j-1]); } } } int queryM(int l,int r){ int k = Log[r-l+1]; return max(stM[l][k],stM[r-(1<<k)+1][k]); } int queryN(int l,int r){ int k = Log[r-l+1]; return min(stN[l][k],stN[r-(1<<k)+1][k]); }
