PROBLEM LINK:
Practice
Div-3 Contest
Div-2 Contest
Div-1 Contest
Author: Evgeny Karpovich
Tester: Felipe Mota
Editorialist: Evgeny Karpovich
DIFFICULTY:
Medium-Hard
PREREQUISITES:
Divide-and-conquer algorithm.
PROBLEM:
It is necessary to calculate the number of array subsegments that the following condition is met:
(A_l \lor A_{l+1} \lor \ldots \lor A_r) \oplus (A_l \land A_{l+1} \land \ldots \land A_r) \geq \max(A_l, A_{l+1}, \ldots, A_r) \,.
QUICK EXPLANATION:
Let’s do divide and conquer algorithm and notice that you can do 2 pointers.
EXPLANATION:
Let’s use Divide-and-conquer algorithm.
Let’s suppose we want to find the answer for the segment of array l \ldots r. Then let’s find the answers for its left half, right half and answers when the bounds of the segment are located in different halves.
We now need to learn how to find the answer when the bounds are in different halves. Let’s fix one of the bounds (at this if the left bound is fixed, then the maximum will be located in the left half; similarly with the right bound).
The solutions for the halves are similar, so let’s consider the left half (i.e. the left bound is fixed). Let’s iterate over all left bounds in descending order and maintain a pointer ptr\_r in the right half so that all right bounds that are less than ptr\_r would satisfy the condition of maximum.
Notice that if we add numbers to the array, the value or \oplus and won’t decrease. Let’s maintain one more pointer ptr\_l such that if we consider all right bounds greater or equal to ptr\_l, they will satisfy the following condition: with the fixed maximum or \oplus and \geq max. The answer for the left bound is equal to ptr\_r - ptr\_l.
Let’s find the complexity of the algorithm. Divide-and-conquer works in O(n \cdot \log n), but the pointer ptr\_l can be moved in two directions. It will not be spent more than O(n \cdot \log MAX(A_i)) operations for its movement, because if or \oplus and in the left half does not change, then the pointer moves to the right only, and if it does change (it will not happen more than O(\log MAX(A_i)) times), then we will move it to the begin in the worst case scenario.
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int const maxn = 1e6 + 5;
ll a[maxn];
ll ans = 0;
ll pref_or[maxn], suff_or[maxn];
ll pref_and[maxn], suff_and[maxn];
ll pref_max[maxn], suff_max[maxn];
void calc(int l, int m, int r) {
ll val_or = a[m], val_and = a[m], mx = a[m];
for (int i = m; i >= l; --i) {
val_or = (val_or|a[i]);
val_and = (val_and&a[i]);
mx = max(mx, a[i]);
suff_or[i] = val_or;
suff_and[i] = val_and;
suff_max[i] = mx;
}
val_or = a[m + 1], val_and = a[m + 1], mx = a[m + 1];
for (int i = m + 1; i <= r; ++i) {
val_or = (val_or|a[i]);
val_and = (val_and&a[i]);
mx = max(mx, a[i]);
pref_or[i] = val_or;
pref_and[i] = val_and;
pref_max[i] = mx;
}
}
void solve(int l, int r) {
if (l == r) {
if (a[l] == 0) {
ans++;
}
return;
}
int m = (r + l) / 2;
calc(l, m, r);
int ptr_l = m + 1, ptr_r = m + 1;
for (int L = m; L >= l; --L) {
while (ptr_r <= r && pref_max[ptr_r] <= suff_max[L]) ptr_r++;
while (ptr_l < ptr_r && ((suff_or[L]|pref_or[ptr_l])^(suff_and[L]&pref_and[ptr_l])) < suff_max[L]) ptr_l++;
while (ptr_l >= m + 2 && ((suff_or[L]|pref_or[ptr_l - 1])^(suff_and[L]&pref_and[ptr_l - 1])) >= suff_max[L]) ptr_l--;
ans += (ll)max(0, ptr_r - ptr_l);
}
ptr_r = m, ptr_l = m;
for (int R = m + 1; R <= r; ++R) {
while (ptr_r >= l && suff_max[ptr_r] < pref_max[R]) ptr_r--;
while (ptr_l > ptr_r && ((pref_or[R]|suff_or[ptr_l])^(pref_and[R]&suff_and[ptr_l])) < pref_max[R]) ptr_l--;
while (ptr_l < m && ((pref_or[R]|suff_or[ptr_l + 1])^(pref_and[R]&suff_and[ptr_l + 1])) >= pref_max[R]) ptr_l++;
ans += (ll)max(0, ptr_l - ptr_r);
}
solve(l, m);
solve(m + 1, r);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, t;
cin >> t;
while (t--) {
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
ans = 0;
solve(1, n);
cout << ans << '\n';
}
return 0;
}