题解：P13980 数列分块入门 5

MoCaRabbit · 2025-09-06 17:04:17 · 题解

一个数被开 \log \log V 次方就变为 1 或 0 了，我们可以跳过权值为 1 或 0 的数。

这样就是单点修改，区间查询，可以用树状数组。

但是我们如何寻找一个区间内所有不等于 1 的数。

随便都能维护啊，就比如你用 set 维护所有不等于 1 的位置，每次直接用 lower_bound 与 upper_bound 找对应区间，然后暴力删除就行了。

时间复杂度 O(n\log n\log\log V)。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
int t[300010],a[300010];
inline int lowbit(int x){
    return x&-x;
}
inline void update(int x,int v){
    while(x<=n) t[x]+=v,x+=lowbit(x);
}
inline int sum(int x){
    int ans=0;
    while(x) ans+=t[x],x-=lowbit(x);
    return ans;
}
set<int>pos;
signed main() {
    ios::sync_with_stdio(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        update(i,a[i]);
        pos.insert(i);
    }
    m=n;
    while(m--){
        int opt,l,r;
        cin>>opt>>l>>r;
        if(l>r) swap(l,r);
        if(opt==0){
            set<int>::iterator b=pos.lower_bound(l),e=pos.upper_bound(r);
            for(set<int>::iterator it=b;it!=e;){
                int p=*it;
                update(p,-a[p]),a[p]=sqrt(a[p]),update(p,a[p]);
                it++;
                if(a[p]<=1) pos.erase(prev(it));
            }
        }
        if(opt==1){
            cout<<sum(r)-sum(l-1)<<"\n";
        }
    }
    return 0;
}