Let $g(i)$ be $f(L, i)$, consider each bit separately:
If this bit is $0$, then after every subsequent $and$ it remains $0$.
If this bit is $1$, either it remains 1 after every subsequent $and$, or there exists a certain $and$ after which the result is $0$, and it remains $0$ thereafter. Thus, $g$ is a monotonically decreasing function. Binary search, $O(m\log^2)$.
There is another method, preprocess and find out for each bit the position where it changes from $1$ to $0$. For each query, start looping from the highest bit, time complexity $O(n\log + m\log)$
// compile: make data
// run: ./data < data.in
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#ifdef LOCAL
#include <debug/codeforces.h>
#define debug(x...) _debug_print(#x, x);
#define Debug(x...) _debug_print_format(#x, x);
std::ifstream terminal("/dev/tty");
#define PP cerr<<"\033[1;30mpause...\e[0m",terminal.ignore();
#else
#define debug(x...)
#define Debug(x...)
#define PP
#endif
template<typename...Args> void print_(Args...args){((cout<<args<<" "),...)<<endl;}
#define rep(i,a,b) for(int i=(a);i<(int)(b);++i)
#define sz(v) ((int)(v).size())
#define print(...) print_(__VA_ARGS__);
#define FIND(a, x) ((find(a.begin(),a.end(),(x))!=a.end())?1:0)
#define cmin(x,...) x=min({(x),__VA_ARGS__})
#define cmax(x,...) x=max({(x),__VA_ARGS__})
#define INTMAX (int)(9223372036854775807)
#define INF (int)(1152921504606846976)
#define NaN (int)(0x8b88e1d0595d51d1)
#define double long double
#define int long long
#define uint unsigned long long
#define MAXN 200010
int tonum(vector<int> &v, int off) {
int ans = 0;
for (int i = 0; i < sz(v); i++) {
if (v[i] >= off) ans += (1 << i);
}
return ans;
}
int bs(vector<vector<int>> &dp, int l, int r, int k) {
int ans = -1;
int L = l;
while (l <= r) {
vector<int> offset(32, 0);
int mid = (l + r) / 2;
rep(i, 0, 32) offset[i] = dp[mid][i] - dp[L-1][i];
int num = tonum(offset, mid-L+1);
// debug(l, mid, r, num)
if (num >= k) ans = mid, l = mid + 1;
else r = mid - 1;
}
return ans;
}
void solve() {
int n; cin >> n;
vector<bitset<32>> a(n+1);
rep(i, 1, n+1) {
int t; cin >> t;
a[i] = t;
}
vector<vector<int>> dp(n+1, vector<int>(32, 0));
rep(i, 1, n+1) {
rep(j, 0, 32) {
dp[i][j] = dp[i-1][j] + a[i][j];
}
}
int q; cin >> q;
// vector<int> offset(32, 0);
// rep(i, 0, 32) offset[i] = dp[3][i] - dp[0][i];
// int num = tonum(offset, 3);
// debug(num)
while (q--) {
int l, k; cin >> l >> k;
int idx = bs(dp, l, n, k);
cout << idx << " ";
// break;
}
cout << endl;
}
int32_t main() {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
int _; cin >> _;
while (_--) solve();
return 0;
}
Hey guys! Just discovered taiking88.net, and it’s pretty legit. The interface is smooth, and I’m already seeing some action. Definitely worth checking out if you’re looking for a new spot to play. Check it out for yourself: taiking88
Checking out ta28. This one is quite interesting. Would recommend, solid choice for something new. Let me know what you think of the website once you visit it yourself! ta28
Yo, just stumbled onto vin88win. It’s pretty slick and has more stuff than I expected. Definitely worth a look if you’re checking out different sources. Just sayin’: vin88win
It’s great seeing platforms prioritize player well-being alongside entertainment! Recognizing patterns is key to healthy habits. Exploring options like kkkkph777 game, with its focus on balance, seems like a positive step for Filipino players. Remember to play responsibly!
Just checked out welcometos666. Looks like a fun place to chill and try your luck. Hope it’s as good as it sounds! Click here to check it out: welcometos666
Heard about the Wild Bandito demo. Gonna give it a spin and see what all the hype is about. Hoping for some big wins! Check out the demo here: wild bandito demo
Anyone had any luck over at win5677? Thinking about throwing some cash their way. Let me know what you think! Find out more here: win5677
Excellent algorithmic analysis! The binary search approach for monotonic functions is brilliant. This bit-level optimization technique reminds me of reward tiering systems I’ve designed – efficient mathematical modeling that scales beautifully. Similar to how jljl13 vip programs optimize player segments through strategic thresholds. Your preprocessing method is particularly elegant for handling multiple queries efficiently.
Just found my 10-minute escape! Spentime’s instant GCash deposits make this perfect for busy parents. Check out spentime link to try the live dealer games now before I need to feed the kids again!