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

vocaloid · 2019-04-01 19:00:49 · 题解

线段树 / 分块。

和隔壁的 GSS 重到了呢……

这道题还是非常简单的，考虑怎么处理开方操作，注意到最大的数 10^{12} 最多被开方 log_210^{12}=39 次，所以最多每个位置处理 39 次，即 \text{O}(39\times 100000)，显然是可以接受的，所以我们记录一下区间最大值，可以用线段树，也可以用分块。

线段树：

#include<bits/stdc++.h>
#define ll long long
#define MAXN 100005
using namespace std;
int n,m;
ll a[MAXN],t[MAXN<<2],maxn[MAXN<<2];
void PushUp(int rt)
{
    t[rt]=t[rt<<1]+t[rt<<1|1];
    maxn[rt]=max(maxn[rt<<1],maxn[rt<<1|1]);
}
void BuildSegmentTree(int rt,int l,int r)
{
    if(l==r)
    {
        t[rt]=maxn[rt]=a[l];
        return;
    }
    int mid=l+r>>1;
    BuildSegmentTree(rt<<1,l,mid);
    BuildSegmentTree(rt<<1|1,mid+1,r);
    PushUp(rt);
}
void Modify(int rt,int l,int r,int tl,int tr)
{
    if(l==r)
    {
        t[rt]=sqrt(t[rt]);
        maxn[rt]=t[rt];
        return;
    }
    int mid=l+r>>1;
    if(tl<=mid && maxn[rt<<1]>1) Modify(rt<<1,l,mid,tl,tr);
    if(tr>mid && maxn[rt<<1|1]>1) Modify(rt<<1|1,mid+1,r,tl,tr);
    PushUp(rt);
}
ll Query(int rt,int l,int r,int tl,int tr)
{
    if(tl<=l && r<=tr) return t[rt];
    int mid=l+r>>1;
    ll res=0;
    if(tl<=mid) res+=Query(rt<<1,l,mid,tl,tr);
    if(tr>mid) res+=Query(rt<<1|1,mid+1,r,tl,tr);
    return res;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    BuildSegmentTree(1,1,n);
    scanf("%d",&m);
    while(m--)
    {
        int opt,x,y;
        scanf("%d %d %d",&opt,&x,&y);
        if(x>y) swap(x,y);
        if(!opt) Modify(1,1,n,x,y);
        else printf("%lld\n",Query(1,1,n,x,y));
    }
    return 0;
}

分块：

#include<bits/stdc++.h>
#define ll long long
#define MAXN 200005
using namespace std;
int n,m,unt,pos[MAXN];
ll sum[MAXN],val[MAXN];
bool fg[MAXN];
template <typename T> void Read(T &x)
{
    int fu=1;
    x=0;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') fu=-1;
    for(;isdigit(ch);ch=getchar()) x=(x<<3)+(x<<1)+(ch-48);
    x*=fu;
}
void ModifyBlock(int x)
{
    if(fg[x]) return;
    fg[x]=1;
    sum[x]=0;
    for(int i=(x-1)*unt+1;i<=x*unt;i++)
    {
        val[i]=sqrt(val[i]);
        sum[x]+=val[i];
        if(val[i]>1) fg[x]=0;
    }
}
void Modify(int l,int r)
{
    for(int i=l;i<=min(pos[l]*unt,r);i++)
    {
        sum[pos[l]]-=val[i];
        val[i]=sqrt(val[i]);
        sum[pos[l]]+=val[i];
    }
    if(pos[l]!=pos[r])
    {
        for(int i=(pos[r]-1)*unt+1;i<=r;i++)
        {
            sum[pos[r]]-=val[i];
            val[i]=sqrt(val[i]);
            sum[pos[r]]+=val[i];
        }
    }
    for(int i=pos[l]+1;i<=pos[r]-1;i++) ModifyBlock(i);
}
ll Query(int l,int r)
{
    ll res=0;
    for(int i=l;i<=min(pos[l]*unt,r);i++) res+=val[i];
    if(pos[l]!=pos[r]) for(int i=(pos[r]-1)*unt+1;i<=r;i++) res+=val[i];
    for(int i=pos[l]+1;i<=pos[r]-1;i++) res+=sum[i];
    return res;
}
int main()
{
    scanf("%d",&n);
    unt=sqrt(n);
    for(int i=1;i<=n;i++) Read(val[i]);
    for(int i=1;i<=n;i++)
    {
        pos[i]=(i-1)/unt+1;
        sum[pos[i]]+=val[i];
    }
    Read(m);
    while(m--)
    {
        int opt,x,y;
        Read(opt);
        Read(x);
        Read(y);
        if(x>y) swap(x,y);
        if(!opt) Modify(x,y);
        else printf("%lld\n",Query(x,y));
    }
    return 0;
}