CF EDU164-E-数论分块

link：https://codeforces.com/contest/1954/problem/E

有一排怪物，第 \(i\) 只有 \(a_i\) 的血，每次攻击可以选择在 \(i\) 处放一个技能，技能会一直向左/右以相同的 \(k\) 点伤害扩散，直至遇到边界或已经死亡的怪物。问最少需要放几次技能？
需要对所有 \(k\) 回答答案。
\(n,a_i\leq 10^5\).

这种对于所有 xxx 值回答的问题，恐怕都要先把原问题做一个转换，使其可以快速回答.

这里我们不失一般性地考察 \(k=1\) 的情况，考虑这样的特殊性并不是突然冒出来的动机，而是首先要注意任意一般的 \(k\) 都可以转换为 \(k=1\) 的情形（无非是伤害变大 \(k\) 倍，把 \(a_i\to \lceil a_i/k\rceil\) 就好了），如果没有意识到这样一个特殊性和一般性之间的辩证关系，恐怕是比较难入手。

而对于 \(k=1\) 的情况：置 \(a_0\) 为 \(0\)，则答案应该是 \(\sum_{i=1}^n \max(0,a_i-a_{i-1})\)，这个答案应该容易get到——想象 \(a\) 长成若干个山峰的样子，肯定是先把最小值消掉，然后 \(a\) 被分成多个块，每个块内继续消除。想象从 \(a\) 的最左爬到最右，影响答案的是一个个大大小小的山峰，这些山峰从低处到高处意味着需要操作，而高处回到低处则只是顺带消除掉。

那么最后要计算的答案就是 \(\sum_{i=1}^n \max(0,\lceil \frac{a_i}{k}\rceil-\lceil \frac{a_{i-1}}{k}\rceil)\) ，而我们知道 \(\lceil a/k\lceil =\lfloor (a+k-1)/k\rfloor =1+\lfloor (a-1)/k\rfloor\)，因此和下取整的除法分块一样，对每个 \(a_i-1\) 来说有 \(\Theta(\sqrt a_i)\) 个 \(k\) 的值可能使其发生变化，预处理出这些 \(k\)，然后计算答案。

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
// #define endl '\n'
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=1e5+5;
int n,a[N],b[N];
vector<int> val_k[N],pos[N];
int main(){
    fastio;
    cin>>n;
    int mx=0;
    rep(i,1,n){
        cin>>a[i];
        mx=max(mx,a[i]);
        pos[a[i]-1].push_back(i);
    }

    rep(m,1,1e5){
        for(int i=1,pos;i<=m;i=pos+1){
            pos=min(m,m/(m/i));
            val_k[pos+1].push_back(m);
        }
    }
    ll S=0;
    rep(i,1,n){
        b[i]=max(0,a[i]-a[i-1]);
        S+=b[i];
    }
    cout<<S;
    rep(k,2,mx){   
        for(auto v:val_k[k]){
            for(auto p:pos[v]){
                if(p==1){
                    S-=b[1];
                    b[1]=max(0,(a[1]-1)/k+1);
                    S+=b[1];
                }else{
                    S-=b[p];
                    b[p]=max(0,(a[p]-1)/k-(a[p-1]-1)/k);
                    S+=b[p];
                }

                if(p==n)continue;

                S-=b[p+1];
                b[p+1]=max(0,(a[p+1]-1)/k-(a[p]-1)/k);
                S+=b[p+1];
            }
        }
        cout<<' '<<S;
    }
    return 0;
}