题解 P4145 【上帝造题的七分钟2】

· · 题解

分块让人快乐。

当a[i]=1时，开方便不再有意义。

加上每个数不大于le12，所以每个数至多被开方6次。

直接分块暴力，维护区间和和一个标记表示是否每个元素都为1。

如果每次区间开方只不涉及完整的块，不超过2√n个元素，直接暴力即可。

如果涉及了一些完整的块，这些块经过几次操作以后就会都变成 1，区间修改时跳过那些全为 1 的块即可。

体感一下复杂度和每个元素被开方次数有关，所以是可行的。

#define ll long long
#include<iostream>
#include<cstdio>
#define N 100005
#include<cmath>
#define B 400
using namespace std;
int bg[N],l[N],r[N],fl[N],n,m;
ll a[N],sum[N];
void Turn()
{
    int u,v;scanf("%d%d",&u,&v);if(u>v) swap(u,v);
    if(bg[u]==bg[v])
    {
        if(fl[bg[u]]) return;
        for(int i=u;i<=v;++i) sum[bg[u]]-=a[i],a[i]=sqrt(a[i]),sum[bg[u]]+=a[i];
        if(sum[bg[u]]==r[bg[u]]-l[bg[u]]+1) fl[bg[u]]=1;
    }
    else
    {
        for(int i=bg[u]+1;i<bg[v];++i)
        {
            if(fl[i]) continue;
            for(int j=l[i];j<=r[i];++j) sum[i]-=a[j],a[j]=sqrt(a[j]),sum[i]+=a[j];
            if(sum[i]==r[i]-l[i]+1) fl[i]=1;
        }
        for(int i=u;i<=r[bg[u]];++i) sum[bg[u]]-=a[i],a[i]=sqrt(a[i]),sum[bg[u]]+=a[i];
        for(int i=l[bg[v]];i<=v;++i) sum[bg[v]]-=a[i],a[i]=sqrt(a[i]),sum[bg[v]]+=a[i];
        if(sum[bg[u]]==r[bg[u]]-l[bg[u]]+1) fl[bg[u]]=1;
        if(sum[bg[v]]==r[bg[v]]-l[bg[v]]+1) fl[bg[v]]=1;
    }
}
void Ask()
{
    int u,v;ll ans=0;scanf("%d%d",&u,&v);if(u>v) swap(u,v);
    if(bg[u]==bg[v])
    {
        for(int i=u;i<=v;++i) ans+=a[i];
    }
    else
    {
        for(int i=bg[u]+1;i<bg[v];++i) ans+=sum[i];
        for(int i=u;i<=r[bg[u]];++i) ans+=a[i];
        for(int i=l[bg[v]];i<=v;++i) ans+=a[i];
    }
    printf("%lld\n",ans);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        scanf("%lld",&a[i]);
        bg[i]=i/B;
        l[bg[i]]=!l[bg[i]]?i:l[bg[i]];
        r[bg[i]]=i;sum[bg[i]]+=a[i];
    }scanf("%d",&m);
    for(int i=1;i<=m;++i)
    {
        int fl;scanf("%d",&fl);
        if(fl) Ask();
        else Turn();
    }
    return 0;
}