P4145 上帝造题的七分钟 2 / 花神游历各国
分析
一开始在思考有没有一个数学公式来处理每一个开方的操作
但发现数据的\(\le 10^{12}\)
那么最多开六次就变成1了（突破口）
这样每一个数的有用操作只有6次
其他就全部是1
很显然，我们可以去记录每一段是否全为1
再用线段树、分块或树状数组解决了
由于我才学了分块，所以就用分块吧
代码
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=1e5+10;
int block,n,m,op,l,r,id[maxn];
ll a[maxn],tag[1005],sum[1005];
void ssqrt(int x){
ll res=0;
int L=(x-1)*block+1,R=x*block;
bool flag=true;
for(int i=L;i<=R;i++){
if(a[i]==1){res++;continue;}
a[i]=(ll)floor(sqrt(a[i]));
if(a[i]!=1) flag=false;
res+=a[i];
}
if(flag) tag[x]=1;
sum[x]=res;
}
void change(int l,int r){
//1.左散块
for(int i=l;i<=min(r,id[l]*block);i++)
sum[id[i]]-=a[i],a[i]=(ll)floor(sqrt(a[i])),sum[id[i]]+=a[i];
if(id[l]==id[r]) return ;
//2.中间的整块
for(int i=id[l]+1;i<=id[r]-1;i++)
if(!tag[i]) ssqrt(i);
//3.右散块
for(int i=(id[r]-1)*block+1;i<=r;i++)
sum[id[i]]-=a[i],a[i]=(ll)floor(sqrt(a[i])),sum[id[i]]+=a[i];
}
ll query(int l,int r){
ll res=0;
//1.左散块
for(int i=l;i<=min(r,id[l]*block);i++)
res+=a[i];
if(id[l]==id[r]) return res;
//2.中间的整块
for(int i=id[l]+1;i<=id[r]-1;i++) res+=sum[i];
//3.右散块
for(int i=(id[r]-1)*block+1;i<=r;i++) res+=a[i];
return res;
}
int main(){
/*2023.4.29 hewanying P4145 上帝造题的七分钟 2 / 花神游历各国 分块*/
scanf("%d",&n);
block=(int)floor(sqrt(n));
for(int i=1;i<=n;i++){
id[i]=(i-1)/block+1;
scanf("%lld",&a[i]);
sum[id[i]]+=a[i];
}
scanf("%d",&m);
for(int i=1;i<=m;i++){
scanf("%d%d%d",&op,&l,&r);
if(l>r) swap(l,r);
if(op==0) change(l,r);
else printf("%lld\n",query(l,r));
}
return 0;
}
总结
1.对于那些看似没有公式或方法进行区间处理的，我们可以考虑计算每个值被有效操作的次数，一般情况这样的次数会很小，从而直接可以暴力枚举
2.区间数据结构对于每一个整块的操作一定是\(O(1)\)的，可以从这一点下手