自从学了分块,我开始了疯狂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;
}
分类: 文章

B_Z_B_Y

虽然也包含些许残酷 , 时间毕竟对任何人都很温柔-。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *