[Libre 6281] 数列分块入门 5 (分块)

水一道入门分块qwq

题面：传送门

开方基本暴力。。

如果某一个区间全部都开成1或0就打上标记全部跳过就行了

因为一个数开上个四五六次就是1了所以复杂度能过233~

code:

//By Menteur_Hxy

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<cmath>

using namespace std;

int rd() {

    int x=0,fla=1; char c=' ';

    while(c>'9'|| c<'0') {if(c=='-') fla=-fla; c=getchar();}

    while(c<='9'&&c>='0') x=x*10+c-'0',c=getchar();

    return x*fla;

}

const int MAX=50010;

const int INF=0x3f3f3f3f;

int n,blo;

int v[MAX],fla[MAX],sum[MAX],bl[MAX];

void sqr(int x) {

    if(fla[x]) return ;

    fla[x]=1;sum[x]=0;

    for(int i=(x-1)*blo+1;i<=x*blo;i++) {

        v[i]=sqrt(v[i]),sum[x]+=v[i];

        if(v[i]>1) fla[x]=0;

    }

}

void add(int a,int b,int c) {

    for(int i=a;i<=min(bl[a]*blo,b);i++) {

        sum[bl[a]]-=v[i];

        v[i]=sqrt(v[i]);

        sum[bl[a]]+=v[i];

    }

    if(bl[a]!=bl[b])

        for(int i=(bl[b]-1)*blo+1;i<=b;i++) {

            sum[bl[b]]-=v[i];

            v[i]=sqrt(v[i]);

            sum[bl[b]]+=v[i];

        }

    for(int i=bl[a]+1;i<=bl[b]-1;i++) sqr(i);

}

int query(int a,int b) {

    int ans=0;

    for(int i=a;i<=min(bl[a]*blo,b);i++) ans+=v[i];

    if(bl[a]!=bl[b])

        for(int i=(bl[b]-1)*blo+1;i<=b;i++) ans+=v[i];

    for(int i=bl[a]+1;i<=bl[b]-1;i++) ans+=sum[i];

    return ans;

}

int main() {

    n=rd(); blo=sqrt(n);

    for(int i=1;i<=n;i++) scanf("%d",&v[i]);

    for(int i=1;i<=n;i++) {

        bl[i]=(i-1)/blo+1;

        sum[bl[i]]+=v[i];

    }

    for(int i=1;i<=n;i++) {

        int opt=rd(),a=rd(),b=rd(),c=rd();

        if(opt) printf("%d\n",query(a,b));

        else add(a,b,c);

    }

    return 0;

}

巴特西

[Libre 6281] 数列分块入门 5 (分块)

最新文章

热门文章