The content below was generated entirely by machine translation. Please verify its accuracy. If anything is unclear, consult the Chinese source version.

F. Yet Another Problem About Pairs Satisfying an Inequality

Approach (from the Official Solution)

Observe the inequality $a_i < i < a_j < j$ in the problem. We can see that, for any element in the array, if it does not satisfy $a_x < x$ , then it can never form a valid pair with any element. Therefore, we can directly skip elements that do not satisfy $a_x < x$ .

We can split this inequality into three parts: $a_i < i$ , $i < a_j$ , and $a_j < j$ .

For all elements satisfying $a_x < x$ , the first and last inequalities are already satisfied. We only need to find elements satisfying $i < a_j$ to form a valid pair.

Let $b$ be the array obtained by removing from $a$ the elements that do not satisfy $a_x < x$ (this sounds a little strange, but the index of every element in $b$ is the same as it was in $a$ ).

For example, suppose an element in the array has two properties, value and index, and we denote it as $(val, id)$ . If array $a$ is:

$a = (1, 1) \ (1, 2)\ (2, 3)\ (3, 4)\ (8, 5)\ (2, 6)\ (1, 7)\ (4, 8)\\$

then removing all elements with $val >= id$ gives $b$ :

$b = (1, 2)\ (2, 3)\ (3, 4)\ (2, 6)\ (1, 7)\ (4, 8)\\$

Then we can solve the problem by finding all valid $i$ for every $b_j$ .

It is not difficult to see that $i$ increases monotonically, so binary search can be used to find the largest $i$ smaller than $b_j$ . Every element in $b$ whose $id$ is smaller than $i$ (as well as $i$ itself) can form a valid pair with $a_j$ .

In addition to binary search, we can use a Fenwick tree to find the number of elements in $b$ whose $id$ is smaller than a particular value.

Specifically, we can use a Fenwick tree to maintain a prefix-sum array and then traverse the elements in $b$ , performing upd(id) each time. This makes the value found when querying every number greater than or equal to $id$ increase by $1$ .

Thus, querying $b_j - 1$ in the Fenwick tree returns all $i$ smaller than $b_j$ .

Of course, a difference-array method can also produce the same prefix-sum array as the Fenwick tree. This problem does not require any further updates after obtaining the prefix-sum array, so a difference array can solve the problem in $\operatorname{O}(n)$ time.

Code

Complexity: $\operatorname{O}(n \log n)$

#include <bits/stdc++.h>
using namespace std;
#define ll long long
// author: ttzytt (ttzytt.com)
// ref: https://codeforces.com/blog/entry/104786
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin>>n;
        int a[n + 1];
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        ll ans = 0;
        vector<int> valid; // The array b described above, but storing only indices,
                           // because we only need to find the largest index j smaller than b_i.
        for (int i = 1; i <= n; i++) {
            if (a[i] >= i) continue; // Skip it directly if it does not satisfy the condition.
            
            // This may count as an optimization. We can see that every index i in valid is smaller than j.
            // We do not put all indices of b into valid, because a[i] < i < a[j] < j,
            // so the condition can only hold when i < j.
            ans += (ll)(lower_bound(valid.begin(), valid.end(), a[i]) -
                        valid.begin());
            // lower_bound finds the first element in valid that is greater than or equal to a[i].
            // Therefore, every element **before** it can be used. The length of an interval is r - l + 1.
            // Since only the elements before it can be used, we do not add this 1.
            valid.push_back(i);
        }
        cout << ans << '\n';
    }
}

G. Good Key, Bad Key

Approach (from the Official Solution)

We can see that alternating between good keys and bad keys for all boxes is always less worthwhile.

Moreover, using good keys consecutively on the earlier boxes is more worthwhile. (In other words, use good keys on a prefix.)

Suppose we use a bad key before a good key. Then the profit we obtain is:

$\lfloor \frac{a_i}{2} \rfloor + (\lfloor \frac{a_{i + 1}}{2} \rfloor - k)$

But if we first use a good key and then a bad key, the profit is:

$(a_i - k) + \lfloor \frac{a_{i + 1}}{2} \rfloor$

Clearly, using the good key first is more worthwhile.

A more intuitive explanation is that regardless of which key is used first, $k$ is subtracted from the profit. However, if we use the bad key first, the profits of two boxes are halved, whereas if we use the good key first, only the profit of one box is halved.

Therefore, we only use bad keys in the final part. In some cases where $k$ is relatively large, halving $a_i$ may be more worthwhile than subtracting $k$ .

Thus, we only need to enumerate a dividing point between the use of good and bad keys. Use good keys before this point and bad keys after it.

Let this dividing point be $x$ .

When bad keys are used after the dividing point $x$ , the profit from each box becomes:

$a_{x + i} = \lfloor a_{x + i} \div 2^{i} \rfloor$

We can see that this $2^i$ grows very quickly, and beyond some point $a_i$ becomes $0$ . There is no need to continue calculating beyond that point.

Because the maximum $a_i$ is $10^9$ , there is no need to calculate after $log_2(10^9) \approx 30$ . (Alternatively, consider continually shifting a number to the right; after some point, its entire binary representation contains no $1$ s.)

Code

#include <bits/stdc++.h>
using namespace std;
#define ll long long
// author: ttzytt (ttzytt.com)
// ref: https://codeforces.com/blog/entry/104786
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        ll psum = 0, ans = 0;
        // psum is the profit obtained by using good keys.
        for (int i = -1; i < n; i++) {
            if (i != -1) psum += (ll)(a[i] - k);
            ll cur = psum;
            // Enumerate i as the dividing point.
            for (int j = i + 1; j < min(n, i + 32); j++) {
                // There is no need to continue calculating beyond i + 32.
                int bkval = a[j];
                bkval >>= (j - i);  // i + 1 is divided by 2, i + 2 is divided by 4, ...
                cur += bkval;
            }
            ans = max(ans, cur);
        }
        cout << ans << endl;
    }
}