【题解】上帝造题的七分钟 2 / 花神游历各国 分块 LUOGU 4145 — B_Z_B_Y

自从学了分块，我开始了疯狂 A 水题。不得说分块虽然慢，但是写的快，当暴力对拍还是行的（如果你真的很闲的话）。

让我们愉悦的学习 QVQ

对分块的讲解，洛谷日报有具体的文章。这里就讲讲本题方法。

很明显，本题对区间的开方比较蛮烦，所以只好直接采用暴力修改。而且众所周知，sqrt（1）= 1 所以当区间都为 1 时则不需要操作（所以 tag[] 标记一下即可），每次修改的时候下传一下标记就行了，剩下的就是普通的分块区间查询

//以下为卡常操作
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>
using namespace std;
#define fors(i,a,b) for(int i=(a);i<=(b);++i)
typedef long long ll;
const int Size=1<<28;
inline char getch(){
    static char buf[Size],*p1=buf,*p2=buf;
    return p1==p2 && (p2=(p1=buf)+fread(buf,1,Size,stdin),p1==p2) ? EOF : *p1++;
}
#define int ll//精度需要
int read(){
    int s=0,f=1;
    char c=getch();
    while(c>'9' || c<'0'){if(c=='-') f=-1;c=getch();}
    while(c<='9' && c>='0'){s=(s<<1)+(s<<3)+c-'0';c=getch();}
    return s*f;
}//基于 fread 的读入优化
void write(int x){
    if(x<0){putchar('-');x=-x;}
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
#define max(x,y) ((x) > (y) ? (x) : (y))
#define min(x,y) ((x) < (y) ? (x) : (y))
//以上为卡常操作
const int maxn=1e5+7;
int n,tot,val[maxn],m,belong[maxn],block,tag[maxn],sum[maxn];
void slove(int x){  
    if(tag[x]) return ;
    tag[x]=1;//标记，sum 清零
    sum[x]=0;
    int len=x*block;
    fors(i,(x-1)*block+1,len){//对这个块暴力修改
        val[i]=sqrt(val[i]);
        sum[x]+=val[i];
        if(val[i] > 1) tag[x]=0; //如果存在一个不为 1 则标记为 0
    }
}
void qrt(int x,int y){
    int len=min(belong[x]*block,y);
    fors(i,x,len){
        sum[belong[x]]-=val[i];
        val[i]=sqrt(val[i]);//修改这个边角块 sum
        sum[belong[x]]+=val[i];
    }
    if(belong[x]!=belong[y]){
        fors(i,(belong[y]-1)*block+1,y){
            sum[belong[y]]-=val[i];
            val[i]=sqrt(val[i]);
            sum[belong[y]]+=val[i];
        }
    }
    fors(i,belong[x]+1,belong[y]-1)
        slove(i);//暴力修改
}
int query(int x,int y){//正常的区间查询
    int ans=0,len=min(belong[x]*block,y);
    fors(i,x,len)//边角块查询
        ans+=val[i];
    if(belong[x]!=belong[y])
        fors(i,(belong[y]-1)*block+1,y)//边角块查询
            ans+=val[i];
    fors(i,belong[x]+1,belong[y]-1)//整块查询
        ans+=sum[i];
    return ans;
}

signed main()
{
    n=read();
    block=sqrt(n);
    fors(i,1,n){
        val[i]=read();
        belong[i]=(i-1)/block+1;
        sum[belong[i]]+=val[i];
    }
    m=read();
    while(m--){
        int op=read(),l=read(),r=read();
        if(l>r) swap(l,r);//坑点，注意交换
        if(op==0){
            qrt(l,r);
        }   
        else if(op==1){
            write(query(l,r)),putchar(10);
        }
    }
    return 0;
}