Codeforces Educational Codeforces Round 164 E. Chain Reaction 【思维、分块、调和级数复杂度】

E. Chain Reaction

题意

有 $n$ 个怪物排成一行，第 $i$ 个怪物的生命值为 $a_i$
当一只怪物的生命值为正数时，它才被认为是活着的

假设你的闪电技能每次能够造成 $k$ 点伤害，你每次可以选择一个怪物攻击，这只怪物会先受到 $k$ 点伤害，并且闪电会向两边传递，直到遇到一只已经死亡的怪物，或者左右端点

现在对于 $\forall k\in [1,max(a_1,a_2,...,a_n)]$，输出击败所有怪物的最小攻击次数

思路

我们先从 $k=1$ 的特例入手，第一次攻击会传播至所有的怪物，我们一直攻击，直到有一只怪物死亡，那么从此刻开始，所有的怪物会被分成若干个互相隔离的子问题，因为闪电无法在不同的隔离快间传递了！
我们继续在其中一个块中操作，继续攻击直到又一只怪物死亡，这个块又被分割成子问题

那么我们可以得出结论：本题不存在最小攻击次数一说，不管如何选择操作对象，最终所需要的总攻击数都是一样的

那么我们可以从 $1$ 号怪物开始攻击，直到它死亡，需要 $a_1$ 次攻击（$k=1$），那么我们继续移动到 $2$ 号怪物，此时有两种情况：

1. $a_2\le a_1$，由于闪电的传递，$2$ 号怪物早已死亡，无需操作
2. $a_2>a_1$，需要额外操作 $a_2-a_1$ 次，补上伤害

后续也是类似情况，就像爬山峰一样，上山过程中才会贡献答案，下山过程不贡献答案

答案即为：$a_1+{\sum }_{i=2}^{n}max(0,a_i-a_{i-1})$

以上是 $k=1$ 的分析，我们在 $O(n)$ 下求出了答案

对于其他的 $k\ge 2$，我们不妨将每个怪物的生命值改为：$\lceil \frac{a_i}{k}\rceil$

也就是这个怪物需要上取整次攻击，答案变为：$\lceil \frac{a_1}{k}\rceil +{\sum }_{i=2}^{n}max(0,\lceil \frac{a_i}{k}\rceil -\lceil \frac{a_{i-1}}{k}\rceil )$

我们提前将 $a_i$ 的系数存储起来，当 $i=1或a_i>a_{i-1}$ 时，$a_i$ 的系数 $+1$；当 $a_i<a_{i+1}$ 时，$a_i$ 的系数 $-1$

最后我们只需要将每个 $a_i$ 对应的系数乘上 $\lceil \frac{a_i}{k}\rceil$ 累加，就是答案

暴力扫描求解复杂度是：$O(kn)$，显然不行，考虑优化：

有两种优化方法，一种是：数论分块，一种是利用调和级数复杂度

1. 数论分块做法，时间复杂度：$O(n\sqrt{A})$
   注意到对于当前的 $k$，$\lceil \frac{a_i}{k}\rceil$ 的取值只有 $O(\sqrt{A})$ 种（$A$ 是 $a_i$ 最大值），这是因为：考虑 $\forall i\le \sqrt{A}，\frac{A}{i}\ge i$，也就是大概 $2\sqrt{A}$ 种取值，我们采用数论分块的做法即可
   具体就是，以 $an{s}_i$ 表示 $k=i$ 的答案，那么对于每个 $a_i$，将它对 $\lceil \frac{a_i}{k}\rceil$ 的取值分割成 $O({\sqrt{a}}_i)$ 块，利用差分来区间统计块内的贡献

#include
#define fore(i,l,r)	for(int i=(int)(l);i<(int)(r);++i)
#define fi first
#define se second
#define endl '\n'
#define ull unsigned long long
#define ALL(v) v.begin(), v.end()
#define Debug(x, ed) std::cerr << #x << " = " << x << ed;

const int INF=0x3f3f3f3f;
const long long INFLL=1e18;

typedef long long ll;

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int n;
    std::cin >> n;
    std::vector<int> a(n + 1, 0);
    fore(i, 1, n + 1) std::cin >> a[i];
    int mx = *max_element(ALL(a));
    std::vector<ll> ans(mx + 5, 0);
    fore(i, 1, n + 1){
        int coef = 0; //coef表示正负
        if(a[i] > a[i - 1]) ++coef;
        if(i + 1 <= n && a[i] < a[i + 1]) --coef;
        int r = a[i];
        ans[r + 1] += coef; //k大于ai的通通上取整取值为1
        while(r > 0){
            ll val = (a[i] + r - 1) / r; //val 表示ai对每个k上取整的系数
            int l = (a[i] + val - 1) / val; //l，r左右边界
            ans[l] += val * coef;
            ans[r + 1] -= val * coef;
            r = l - 1; //下一块
        }
    }

    fore(i, 1, mx + 1){
        ans[i] += ans[i - 1];
        std::cout << ans[i] << ' ';
    }
    return 0;
}
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
35
36
37
38
39
40
41
42
43
44
45

---

2. 调和级数复杂度做法，时间复杂度：$O(n+A\log A)$
   还是同样的，我们先统计每个 $a_i$ 的系数，

注意到：对于当前的 $k$，当 $a_i\in [1,k]$ 时，$\lceil \frac{a_i}{k}\rceil =1$
当 $a_i\in [k+1,2k]$ 时，$\lceil \frac{a_i}{k}\rceil =2$
当 $a_i\in [2k+1,3k]$ 时，$\lceil \frac{a_i}{k}\rceil =3$

那么我们可以将每个 $a_i$ 对当前的 $k$ 的贡献按照 $\lceil \frac{a_i}{k}\rceil$，分成 $k$ 块，

那么对于每个 $k$，我们要计算：$O(\frac{A}{1}+\frac{A}{2}+\frac{A}{3}+...+\frac{A}{A})=O(A\cdot (\frac{1}{1}+\frac{1}{2}+...+\frac{1}{A}))=O(A\log A)$

只需要用前缀和数组预存一下每个 $a_i$ 的系数，即可快速区间查询

#include
#define fore(i,l,r)	for(int i=(int)(l);i<(int)(r);++i)
#define fi first
#define se second
#define endl '\n'
#define ull unsigned long long
#define ALL(v) v.begin(), v.end()
#define Debug(x, ed) std::cerr << #x << " = " << x << ed;

const int INF=0x3f3f3f3f;
const long long INFLL=1e18;

typedef long long ll;

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int n;
    std::cin >> n;
    std::vector<int> a(n + 1, 0);
    fore(i, 1, n + 1) std::cin >> a[i];
    int mx = *max_element(ALL(a));
    std::vector<ll> sum(mx + 5, 0); //前缀和
    fore(i, 1, n + 1){
        int coef = 0; //coef表示正负
        if(a[i] > a[i - 1]) ++coef;
        if(i + 1 <= n && a[i] < a[i + 1]) --coef;
        sum[a[i]] += coef;
    }
    
    fore(i, 2, mx + 1)	sum[i] += sum[i - 1];
    
    fore(k, 1, mx + 1){
    	ll ans = 0;
    	for(int l = 1; l <= mx; l += k){
    		int r = std::min(mx, l + k - 1);
    		ans += (l + k - 1) / k * (sum[r] - sum[l - 1]);
    	}
    	std::cout << ans << ' ';
    }
    
    return 0;
}
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
35
36
37
38
39
40
41
42
43
44