Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long int ll;
- const ll N = 1e5+7;
- ll arr[N], cnt[N][25];
- ll andValue(ll l, ll r) {
- ll ans = 0;
- for (ll j = 20; j >= 0; j--) {
- if (cnt[r][j]-cnt[l-1][j] == r-l+1) ans += (1LL << j);
- }
- return ans;
- }
- signed main() {
- ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
- ll t = 1; cin >> t;
- while (t--) {
- ll n, q; cin >> n >> q;
- for (ll i = 1; i <= n; i++) {
- cin >> arr[i];
- for (ll j = 20; j >= 0; j--) {
- if (arr[i] & (1LL << j)) cnt[i][j] = 1;
- }
- for (ll j = 20; j >= 0; j--) cnt[i][j] += cnt[i-1][j];
- }
- while (q--) {
- ll l, r; cin >> l >> r;
- ll curr = l, ans = 0;
- while (curr < r) {
- ll low = curr, high = r-1, indx = curr;
- while (low <= high) {
- ll mid = low + (high-low) / 2;
- if (andValue(curr, mid) == andValue(l, curr)) {
- indx = mid;
- low = mid+1;
- }
- else high = mid-1;
- }
- ans = max(ans, andValue(l, indx)+andValue(indx+1, r));
- curr = indx+1;
- }
- cout << ans << "\n";
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
