1 struct RMQ 2 { 3 int log2[N],mi[N][25]; 4 void init(int n) 5 { 6 for(int i = 0; i <= n; i ++)log2[i] = (i == 0 ? -1 : log2[i >> 1] + 1); 7 for(int j = 1; j < log2[n]; j ++) 8 for(int i = 1; i + (1 << j) <= n + 1; i ++) 9 mi[i][j] = std::min(mi[i][j - 1], mi[i + (1 << j - 1)][j - 1]); 10 } 11 int query(int ql, int qr) 12 { 13 int k = log2[qr - ql + 1]; 14 return std::min(mi[ql][k], mi[qr - (1 << k) + 1][k]); 15 } 16 } rmq;