CSES - Shared codeLink to this code:
https://cses.fi/paste/71175676a82d3351271ec5/
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include "bits/stdc++.h"
using namespace std;
constexpr int N = 2e5 + 10;
int arr[N], ST[32][2 * N], bt[N],n,q,inf;
long long val[32][N];
int get_bit(int x) {
return x ? 1 + get_bit(x / 2) : 0 ;
}
int query(int l, int r, int b) {
int res = inf;
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l&1) res = min(ST[b][l++], res);
if (r&1) res = min(ST[b][--r], res);
}
return res;
}
int32_t main()
{
ios::sync_with_stdio(0);cin.tie(0);
cin >> n >> q;
for(int i = 0 ; i < n; i++) {
cin >> arr[i];
val[bt[i] = get_bit(arr[i])][i] = arr[i];
}
for(int b = 1 ; b < 31 ; b++) {
memset(ST[b], 0x3f,sizeof ST[b]);
for(int i = 1 ; i < N; i++) {
val[b][i] += val[b][i-1];
}
}
inf = ST[1][0];
for(int i = 0 ; i < n; i++) {
ST[bt[i]][n + i] = arr[i];
}
for(int b = 1 ; b < 31; b++) {
for(int i = n - 1; i ; i--) {
ST[b][i] = min(ST[b][i << 1] , ST[b][i << 1 | 1]);
}
}
while(q--) {
int l,r; cin >> l >> r;
l--;r--;
long long ans = 1;
for(int b = 1 ; b < 31; b++) {
int rmn = query(l,r+1,b);
if(rmn == inf) continue;
long long rsm = val[b][r] - (l ? val[b][l-1] : 0);
if(ans >= rmn) ans += rsm;
else break;
}
cout << ans << "\n";
}
}