CF920F SUM and REPLACE

传送门

Solution

对于 $1\le a_i \le 10^6$，不超过 6 次操作可将一个 $a_i$ 变为 $1$ 或 $2$。有 $O(n\log n)$ 的方法预处理出 $1\sim 10^6$ 的正约数个数。

对于操作 1，暴力修改该区间。当 $a_i=1$ 或 $a_i=2$ 时，视 $a_i$ 不可用。设 $F_i$ 表示点 $i$ 左边最近的可用点（包括 $i$ 自己）。初始化 $F_i=i$。当 $i$ 不可用后，令 $F_i=find(i-1)$，其中函数 $find()$ 为并查集的查找函数。这样就实现了类似链表的遍历和删除操作，总共的修改次数不超过 $6n$，可以接受。用树状数组维护区间和，暴力修改时直接更新。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll N = 3e5 + 10;

ll n, m, a[N], mp[1000010], fa[N], tr[N];

ll find(ll x) {return fa[x] == x ? x : fa[x] = find(fa[x]);}

ll lowbit(ll x) {return x & -x;}

void add(ll x, ll c) 
{
    for (; x <= n; x += lowbit(x))
        tr[x] += c;
}

ll query(ll x)
{
    ll res = 0;
    for (; x > 0; x -= lowbit(x))
        res += tr[x];
    return res;
}

int main()
{
    for (int i = 1; i <= 1e6; i++)
        for (int j = i; j <= 1e6; j += i)
            mp[j]++;
    scanf("%lld%lld", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
        add(i, a[i]);
        fa[i] = i;
        if (a[i] == 1 || a[i] == 2) 
            fa[i]--;
    }
    while (m--) {
        ll opt, l, r;
        scanf("%lld%lld%lld", &opt, &l, &r);
        if (opt == 1) {
            ll p = find(r);
            while (p >= l) {
                add(p, -a[p]);
                a[p] = mp[a[p]];
                add(p, a[p]);
                if (a[p] == 1 || a[p] == 2)
                    fa[p] = find(p - 1);
                p = find(p - 1);
            }
        } else 
            printf("%lld\n", query(r) - query(l - 1));
    }
    return 0;
}