F. Yet Another Problem About Pairs Satisfying an Inequality

思路（来源于官方题解）

观察题目中的不等式 $a_i < i < a_j < j$ 。可以发现，对于数组中的任意元素，只要不符合 $a_x < x$ ，那就绝对不会和任何的元素组成一个合法的数对。所以我们可以直接跳过不符合 $a_x < x$ 的元素。

我们可以把这个不等式拆成三个部分 $a_i < i, i < a_j$ 和 $a_j < j$ 。

那对于所有符合 $a_x < x$ 的元素，第一个和最后一个不等式已经满足了，只要找到满足 $i < a_j$ 的元素，就可以构成一个合法数对了。

我们设 $a$ 去掉不满足 $a_x < x$ 的数组为 $b$ （听起来有点奇怪，但是 $b$ 中的每个元素的下标是跟 $a$ 一样的）。

比如我们说数组中的一个元素有值和下标两个属性，并且用这样的方式标记： $(val, id)$ ，那么如果 $a$ 数组是：

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

那去掉所有 $val >= id$ 的，就能得到 $b$ :

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

那只要我们对于每个 $b_j$ 找到所有符合的 $i$ ，就可以解决本题。

其中不难发现 $i$ 是单调递增的，所以可以使用二分来找最大的，小于 $b_j$ 的 $i$ 。那么 $b$ 中所有 $id$ 小于 $i$ 的元素（以及 $i$ 自身）都可以跟 $a_j$ 构成一个合法数对。

除了二分法，我们还可以用树状数组来找到 $b$ 中所有 $id$ 小于一个特定值的元素的数量。

具体来说，我们可以用树状数组维护一个前缀和数组，然后遍历 $b$ 中的元素，每次都做 upd(id) 的操作。也就是使查询所有大于等于 $id$ 的数时，查到的值都增加 $1$ 。

这样，在树状数组中查询某个 $b_j - 1$ 的时候，就会返回比 $b_j$ 小的所有 $i$ 了。

当然，用差分的方法，也可以得到和树状数组相同的前缀和数组。而且本题不需要我们在得到这个前缀和数组后做别的更新，所以差分可以用 $\operatorname{O}(n)$ 的复杂度解决本题。

代码

复杂度： $\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; // 前文所说的 b 数组，但是只储存了下标
                           // 因为我们只需要找最大的，小于 b_i 的下标 j
        for (int i = 1; i <= n; i++) {
            if (a[i] >= i) continue; // 不符合就直接跳过
            
            // 这里可能算是一个优化吧，可以发现 valid 中的下标 i 都是小于 j 的
            // 我们并没有把全部的 b 的下标都塞进 valid 中，因为 a[i] < i < a[j] < j
            // 所以只有 i < j 才可能符合。
            ans += (ll)(lower_bound(valid.begin(), valid.end(), a[i]) -
                        valid.begin());
            // lower_bound 会找到 valid 中第一个大于等于 a[i] 的元素。
            // 那么这个元素**之前**的全部是可用的。一个区间的长度为 r - l + 1
            // 因为只有这个元素之前的才是可用的，所以这个 1 我们就不加了
            valid.push_back(i);
        }
        cout << ans << '\n';
    }
}

G. Good Key, Bad Key

思路（来源于官方题解）

我们能发现，对于所有的盒子，交错的使用好钥匙和坏钥匙总是更加不合算的。

并且，连续的，在前面的盒子使用好钥匙会更合算。（或者说使用好钥匙作为前缀）。

假设我们在一个好钥匙之前使用了一个坏钥匙，那么我们获得的收益是：

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

但如果先使用好钥匙，后使用坏钥匙，获得的收益是：

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

很明显，先使用好钥匙更合算。

更直观一点的解释是，不管先使用哪种钥匙，都会减去 $k$ 的收益，但是如果先使用坏钥匙，我们会把两个盒子的收益减半，但如果先使用好钥匙，就只会把一个盒子的收益减半。

所以我们只会在最后的部分使用坏钥匙，在某些 $k$ 比较大的情况下，可能相比减去 $k$ ，把 $a_i$ 减半更合算。

所以只需要枚举一个使用好钥匙和坏钥匙的分割点，在这个点前面全部使用好钥匙，后面全部使用坏钥匙。

我们设这个分割点为 $x$ 。

那么在分割点 $x$ 后面使用坏钥匙，每个盒子的收益就会变成：

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

能发现这个 $2^i$ 会增长的很快，在某个点之后， $a_i$ 就会变成 $0$ 。那么在这个点之后我们就没必要再计算了。

因为最大的 $a_i$ 为 $10^9$ ，所以 $log_2(10^9) \approx 30$ 之后就没必要计算了。（或者你可以想，一直右移一个数，那么过了某个点整个数的二进制形式就没有 $1$ 了）。

代码

#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 是使用好钥匙获得的收益
        for (int i = -1; i < n; i++) {
            if (i != -1) psum += (ll)(a[i] - k);
            ll cur = psum;
            // 枚举 i 这个分割点
            for (int j = i + 1; j < min(n, i + 32); j++) {
                // 过了 i + 32 就没必要继续计算了
                int bkval = a[j];
                bkval >>= (j - i);  // i + 1 要 / 2, i + 2 要 / 4 ...
                cur += bkval;
            }
            ans = max(ans, cur);
        }
        cout << ans << endl;
    }
}