#include "secret.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e3 + 5;
// 保持原始数组
int arr[MAX_N];
// log2(MAXN)
const int LOG = 10;
int mask[MAX_N]; // 记录每个位置的区间信息
int dat[LOG][MAX_N]; // 存储预处理的最小值数据
// X X X X X X X X 3 * 2 = 6
// X X X X X X X X 1 * 4 = 4
// X X X X X X X X 0 * 8 = 0
// (n / 2 - 1) * 2 n - 2
// (n / 4 - 1) * 4 n - 4
// (n / 8 - 1) * 8 n - 8
// nlgn - (2 + 4 + 8 + ... + 2 ^ i) 2 ^ i <= n的最大值
// nlgn - (2 ^ (i + 1) - 2) = nlgn - 2 ^ (i + 1) + 2
// nlgn - 2 * n + 2（不会超过8000）
// 8 * 3 - (2 + 4 + 8) = 10
void preprocess(int L, int R, int level) {
// 区间只有1个元素，不用计算
if (L == R) {
return;
}
// 找到区间中间索引
int mid = (L + R) / 2;
// 预处理求dat（i到mid的最小值）
// 从mid向左计算
dat[level][mid] = arr[mid];
for (int i = mid - 1; i >= L; i--) {
dat[level][i] = Secret(arr[i], dat[level][i + 1]);
}
// 预处理求right（mid+1到r的最小值）
// 从mid+1向右计算
dat[level][mid + 1] = arr[mid + 1];
for (int i = mid + 2; i <= R; i++) {
dat[level][i] = Secret(dat[level][i - 1], arr[i]);
}
// 更新右半部分的mask标记
for (int i = mid + 1; i <= R; i++) {
mask[i] ^= (1 << level);
}
// 递归处理左右子区间
preprocess(L, mid, level + 1);
preprocess(mid + 1, R, level + 1);
}
// 末尾连续0的个数
int count_trailing_zeros(int x) {
// 特殊处理0的情况
if (x == 0) {
return 32;
}
int count = 0;
// 检查最低位是否为0
while ((x & 1) == 0) {
count++;
// 右移一位
x >>= 1;
}
return count;
}
void Init(int N, int A[]) {
for (int i = 0; i < N; ++i) {
arr[i] = A[i];
}
preprocess(0, N - 1, 0);
}
int Query(int L, int R) {
// 只有一个元素
if (L == R) {
return arr[L];
}
// 计算mask的差异位数，确定查询层级
// __builtin_ctz
// diff_bits就是L和R，第一次被划分到两个区域的层级
int diff_bits = count_trailing_zeros(mask[L] ^ mask[R]);
return Secret(dat[diff_bits][L], dat[diff_bits][R]);
}
