题解 | #小红的零#

F. 小红的零

感觉这道题非常好，比赛的时候差一口气没写出来，但是思路是对的，所以还是非常可惜。

思路

首先我们需要知道的是，一个子数组 $[l,r]$ 的权值应该是 $a[l],...,a[r]$ 所有元素的因子 $2$ 个数 $cnt_2$ 与因子 $5$ 个数 $cnt_5$ 的较小值。假设 $f_2[i]$ 是子数组 $[1,i]$ 中所有元素的因子 $2$ 总数量， $f_5[i]$ 是子数组 $[1,i]$ 中所有元素的因子 $5$ 总数量，则子数组 $[1,i]$ 的权值应该为 $min(f_2[i],f_5[i])$ 。对于任意的子数组 $[l,r]$ ，权值之就应该是 $min(f_2[r]-f_2[l-1],f_5[r]-f_5[l-1])$ 。

此时我们就可以得到一个 $O(n^2)$ 的解法，枚举子数组的左右端点计算所有子数组的权值累加起来即可。比赛的时候就这样跑了一次，过了 $66.67\%$ 的数据，后来的优化比较复杂，没能写完。

线段树优化

很明显本题在遍历到某个子数组结尾 $a[r]$ 时，需要把以 $a[r]$ 结尾的所有子数组权值和都得到。那么我们该如何计算贡献呢？此时子数组的左端点可以是 $[1,r-1]$ ：

如果 $f_2[r]-f_2[x] \leq f_5[r]-f_5[x]$ ，那么就累加所有满足这个不等式的 $x$ 对答案的贡献，即 $y \times f_2[r]-\Sigma_xf_2[x]$ ，其中 $y$ 为满足这个不等式的 $x$ 个数。
互补地，则有 $f_2[r]-f_2[x] \gt f_5[r]-f_5[x]$ ，此时的贡献就应该是 $y \times f_5[r]-\Sigma_xf_5[x]$ 。

对于情况 $1$ ，我们对不等式移项就发现 $f_5[x]-f_2[x] \leq f_5[r]-f_2[r]$ ，这就清晰很多了，可以以 $f_5[i]-f_2[i]$ 为索引开线段树，来计算上述两种情况贡献中的 $y$ 以及求和 $\Sigma$ 的结果。这里我写得比较复杂，开了 $4$ 棵线段树，其实还可以化简，只是对模板的变形会比较多。

注意

考虑到 $f_5[i]-f_2[i]$ 的值可能比较大，而且不一定非负，所以需要先对其做离散化再开线段树。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <unordered_map>

using namespace std;
typedef long long LL;

const int N = 100010;
int n, a[N];
LL f2[N], f5[N];

class SegmentTree {
public:
    LL arr[N];      // 初始数组
    struct Tag {
        int add;
        Tag() {
            add = 0;
        }
    };
    struct Info {
        int l, r;
        LL sum, minimum, maximum;
        Tag lazy;
        Info() {}
        Info(int left, int right, int val): l(left), r(right), sum(val) {}
    } tr[N<<2];
    
    explicit SegmentTree() {}
    
    void build(int u, int l, int r) {
        if(l == r) {
            tr[u] = Info(l, r, arr[l]);
            return;
        }
        int mid = (l + r) >> 1;
        build(lc(u), l, mid);
        build(rc(u), mid + 1, r);
        pushup(u);
    }
    
    void modify(int l, int r, int d) {
        modify(1, l, r, d);
    }
    
    Info query(int l, int r) {
        return query(1, l, r);
    }
    
private:
    int lc(int u) { 
        return u<<1;
    }
    
    int rc(int u) {
        return u<<1|1;
    }
    
    void pushup(int u) {
        tr[u] = merge(tr[lc(u)], tr[rc(u)]);
    }
    
    void pushdown(int u) {
        if(not_null(tr[u].lazy)) {
            down(u);
            clear_lazy(tr[u].lazy);      // 标记下传后要清空
        }
    }
    
    void modify(int u, int l, int r, LL d) {
        if(l <= tr[u].l && tr[u].r <= r) {
            set(u, d);
            return;
        }
        pushdown(u);
        int mid = (tr[u].l + tr[u].r) >> 1;
        if(mid >= l) modify(lc(u), l, r, d);
        if(mid < r) modify(rc(u), l, r, d);
        pushup(u);
    }
    
    Info query(int u, int l, int r) {
        if(l <= tr[u].l && tr[u].r <= r) return tr[u];
        pushdown(u);
        int mid = (tr[u].l + tr[u].r) >> 1;
        if(r <= mid) {
            return query(u<<1, l, r);
        }else if(mid < l) {
            return query(u<<1|1, l, r);
        }else {
            return merge(query(u<<1, l, r), query(u<<1|1, l, r));
        }
    }

    Info merge(const Info& lchild, const Info& rchild) {
        Info info;
        info.l = lchild.l, info.r = rchild.r;
        info.sum = lchild.sum + rchild.sum;
        return info;
    }
    
    // modify操作到不能递归时，设置节点的属性值
    void set(int u, int d) {
        tr[u].sum += d*(tr[u].r - tr[u].l + 1);
        tr[u].lazy.add += d;
        tr[u].minimum += d;
        tr[u].maximum += d;
    }
    
    // 下传标记的规则
    void down(int u) {
        int mid = (tr[u].l + tr[u].r) >> 1;
        tr[lc(u)].lazy.add += tr[u].lazy.add;
        tr[rc(u)].lazy.add += tr[u].lazy.add;
        tr[lc(u)].sum += tr[u].lazy.add*(mid - tr[u].l + 1);
        tr[rc(u)].sum += tr[u].lazy.add*(tr[u].r - mid);
    }
    
    // 判断标记是否为空的规则
    bool not_null(Tag& lazy) {
        return lazy.add != 0;
    }
    
    // 清空标记的规则
    void clear_lazy(Tag& lazy) {
        lazy.add = 0;
    }
};

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    for(int i = 1; i <= n; i++) {
        int x = a[i];
        int two = 0, five = 0;
        while(x % 2 == 0) {
            two++;
            x >>= 1;
        }
        while(x % 5 == 0) {
            five++;
            x /= 5;
        }
        f2[i] = f2[i - 1] + two;
        f5[i] = f5[i - 1] + five;
    }
    vector<LL> vals;
    for(int i = 1; i <= n; i++) {
        vals.push_back(f5[i] - f2[i]);
    }
    vals.push_back(0);
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    int m = vals.size();
    unordered_map<int, int> val2pos;
    for(int i = 0; i < m; i++) {
        val2pos[vals[i]] = i + 1;
    }
    SegmentTree seg_sum2, seg_cnt2, seg_sum5, seg_cnt5;
    memset(seg_sum2.arr, 0, sizeof seg_sum2.arr);
    memset(seg_cnt2.arr, 0, sizeof seg_cnt2.arr);
    memset(seg_sum5.arr, 0, sizeof seg_sum5.arr);
    memset(seg_cnt5.arr, 0, sizeof seg_cnt5.arr);
    seg_sum2.build(1, 1, m);
    seg_cnt2.build(1, 1, m);
    seg_sum5.build(1, 1, m);
    seg_cnt5.build(1, 1, m);
    // 注意要把0先加入计数的线段树
    int idx = val2pos[0];
    seg_cnt2.modify(idx, idx, 1);
    seg_cnt5.modify(idx, idx, 1);
    LL ans = 0;
    for(int r = 1; r <= n; r++) {
        idx = val2pos[f5[r] - f2[r]];
        LL s2 = seg_sum2.query(1, idx).sum;
        LL s5 = idx + 1 <= m? seg_sum5.query(idx + 1, m).sum: 0;
        LL cnt2 = seg_cnt2.query(1, idx).sum;
        LL cnt5 = idx + 1 <= m? seg_cnt5.query(idx + 1, m).sum: 0;
        ans += cnt2*f2[r] - s2;
        ans += cnt5*f5[r] - s5;
        seg_sum2.modify(idx, idx, f2[r]);
        seg_cnt2.modify(idx, idx, 1);
        seg_sum5.modify(idx, idx, f5[r]);
        seg_cnt5.modify(idx, idx, 1);
    }
    printf("%lld\n", ans);
    return 0;
}