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][21];
- ll andValue(ll l, ll r) {
- ll indx = 0;
- for (ll j = 20; j >= 0; j--) {
- if (cnt[r][j]-cnt[l-1][j] == r-l+1) indx += (1LL << j);
- }
- return indx;
- }
- bool valid(ll l, ll r, ll j) {
- return (cnt[r][j] - cnt[l-1][j] == r-l+1);
- }
- 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;
- else cnt[i][j] = 0;
- }
- for (ll j = 20; j >= 0; j--) cnt[i][j] += cnt[i-1][j];
- }
- while (q--) {
- ll l, r; cin >> l >> r;
- ll ans = andValue(l, r-1) + andValue(r, r);
- for (ll j = 0; j <= 20; j++) {
- if (arr[l] & (1LL << j)) {
- ll low = l, high = r-1, indx = l;
- while (low <= high) {
- ll mid = low + (high-low) / 2;
- if (valid(l, mid, j)) {
- low = mid+1;
- indx = mid;
- }
- else high = mid-1;
- }
- ans = max(ans, andValue(l, indx) + andValue(indx+1, r));
- }
- }
- cout << ans << "\n";
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
