Loading...

洛谷P4145 上帝造题的七分钟2 / 花神游历各国 题解

check评论:0 条 remove_red_eye浏览量:455 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-09-18

我又来刷两倍经验题了

这其实和$loj$数列分块入门$5$一样的

听说开根和分块更配哦

这道题一看就是分块裸题啊$\text{qwq}$

$\text{orz}$线段树$\text{dalao}$们

我们对于每个块,统计出它的总和,以及他现在是不是$1$

因为发现基本上$\sqrt{\sqrt{\sqrt{\sqrt{\sqrt{\sqrt n}}}}}$都等于$1$了,所以我们对每个块,最多开$6$次方,打个标记关于其是否全为$1$即可

然后边块角块暴力开根,记得要先用总和减去当前值,开根后再加上,就可以算出答案了

每次边块角块修改后也统计一下是否全为$1$,说不定用几次$O(\sqrt n)$时间复杂度的操作就可以大大减小常数对于非洲人来说很有必要的

还有就是关于分块块大小的问题,我这里是按照理论最优$\sqrt{\frac{n+2}{3}}$处理的,具体证明可以看我的博客

上代码qwq

#include <bits/stdc++.h>
#define int long long
using namespace std;
int belong[100010],isone[4000],sum[4000];
int a[100010],n,m,block;
void update(int blockn)
{
    for(int i=(blockn-1)*block+1;i<=blockn*block;i++)
    {
        if(a[i]!=1)
        {
            isone[blockn]=0;
            return ;
        }
    }
    isone[blockn]=1;
}
void getsqrt(int l,int r)
{
    int flag=0;
    for(int i=l;i<=min(r,belong[l]*block);i++)
    {
        if(isone[belong[l]])
        {
            flag=1;
            break;
        }
        sum[belong[i]]-=a[i];
        a[i]=sqrt(a[i]);
        sum[belong[i]]+=a[i];
    }
    if(!flag)
    {
        update(belong[l]);
    }
    flag=0;
    if(belong[l]!=belong[r])
    {
        for(int i=(belong[r]-1)*block+1;i<=r;i++)
        {
            if(isone[belong[r]])
            {
                flag=1;
                break;
            }
            sum[belong[i]]-=a[i];
            a[i]=sqrt(a[i]);
            sum[belong[i]]+=a[i];
        }
        if(!flag)
        {
            update(belong[r]);
        }
    }
    for(int i=belong[l]+1;i<belong[r];i++)
    {
        if(isone[i])
        {
            continue;
        }
        for(int j=(i-1)*block+1;j<=i*block;j++)
        {
            sum[i]-=a[j];
            a[j]=sqrt(a[j]);
            sum[i]+=a[j];
        }
        update(i);
    }
}
int query(int l,int r)
{
    int ans=0;
    for(int i=l;i<=min(r,belong[l]*block);i++)
    {
        ans+=a[i];
    }
    if(belong[l]!=belong[r])
    {
        for(int i=(belong[r]-1)*block+1;i<=r;i++)
        {
            ans+=a[i];
        }
    }
    for(int i=belong[l]+1;i<belong[r];i++)
    {
        ans+=sum[i];
    }
    return ans;
}
main()
{
    cin>>n;
    block=sqrt((n+2)/3);
    for(int i=1;i<=n;i++)
    {
        belong[i]=(i-1)/block+1;
        scanf("%lld",&a[i]);
        sum[belong[i]]+=a[i];
    }
    cin>>m;
    for(int i=1;i<=m;i++)
    {
        int opt,l,r;
        scanf("%lld%lld%lld",&opt,&l,&r);
        if(l>r)
        {
            swap(l,r);
        }
        if(opt==0)
        {
            getsqrt(l,r);
        }
        else
        {
            printf("%lld\n",query(l,r));
        }
    }
} 

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名