F. Yet Another Problem About Pairs Satisfying an Inequality

思路(来源于官方题解)

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

我们可以把这个不等式拆成三个部分 ai<i,i<aja_i < i, i < a_jaj<ja_j < j

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

我们设 aa 去掉不满足 ax<xa_x < x 的数组为 bb (听起来有点奇怪,但是 bb 中的每个元素的下标是跟 aa 一样的)。

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

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

那去掉所有 val>=idval >= id 的,就能得到 bb:

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

那只要我们对于每个 bjb_j 找到所有符合的 ii,就可以解决本题。

其中不难发现 ii 是单调递增的,所以可以使用二分来找最大的,小于 bjb_jii。那么 bb 中所有 idid 小于 ii 的元素(以及 ii 自身)都可以跟 aja_j 构成一个合法数对。

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

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

这样,在树状数组中查询某个 bj1b_j - 1 的时候,就会返回比 bjb_j 小的所有 ii 了。

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

代码

复杂度:O(nlogn)\operatorname{O}(n \log n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#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

思路(来源于官方题解)

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

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

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

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

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

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

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

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

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

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

我们设这个分割点为 xx

那么在分割点 xx 后面使用坏钥匙,每个盒子的收益就会变成:

ax+i=ax+i÷2ia_{x + i} = \lfloor a_{x + i} \div 2^{i} \rfloor

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

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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#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;
}
}