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

原题传送门

这道题实际和GSS4是一样的，只是输入方式有点区别

GSS4传送门

这道题暴力就能过qaq（这里暴力指线段树）

数据比较水

开方修改在线段树中枚举叶节点sqrt

查询区间和线段树基本操作

这就可以ac

下面有两个优化，没在代码中体现

1.加开方的懒标记

2.最大的数很小，只要开方6次就可以变成1

所以线段树中再记录区间最大值

当最大值是1时，就可以不用开方

暴力的代码

#include <bits/stdc++.h>

using namespace std;

const int MAXN=100005;

long long a[MAXN];

long long f[MAXN<<2];

long long read(long long &x)

{

    long long f=1;char ch=getchar();

    x=0;

    while(ch<'0' || ch>'9')

    {

        if(ch=='-')

        f=-1;

        ch=getchar();

    }

    while(ch>='0' && ch<='9')

    {

        x=x*10+ch-'0';

        ch=getchar();

    }

    return x*f;

}

int readline(int &x)

{

    int f=1;char ch=getchar();

    x=0;

    while(ch<'0' || ch>'9')

    {

        if(ch=='-')

        f=-1;

        ch=getchar();

    }

    while(ch>='0' && ch<='9')

    {

        x=x*10+ch-'0';

        ch=getchar();

    }

    return x*f;

}

void build(int root,int left,int right)

{

    if(left==right)

    {

        f[root]=a[left];

        return;

    }

    int mid=(left+right)/2;

    build(2*root,left,mid);

    build(2*root+1,mid+1,right);

    f[root]=f[2*root]+f[2*root+1];

}

void update(int root,int left,int right,int qleft,int qright)

{

    int mid,ans,i;

    if(right-left+1==f[root])

        return;

    if(left==right)

    {

        f[root]=sqrt(f[root]);

        return;

    }

    mid=(left+right)/2;

    if(qleft<=mid)

        update(2*root,left,mid,qleft,qright);

    if(mid<qright)

        update(2*root+1,mid+1,right,qleft,qright);

    f[root]=f[root*2]+f[root*2+1];

}

long long query(int root,int left,int right,int qleft,int qright)

{

    long long ans=0;

    if(qleft<=left&&right<=qright)

        return f[root];

    int mid=(left+right)/2;

    if(qleft<=mid)

        ans=query(2*root,left,mid,qleft,qright);

    if(mid<qright)

        ans+=query(2*root+1,mid+1,right,qleft,qright);

    return ans;

}

int main()

{

    int n,i,x,y,j,way,k=0,m;

    scanf("%d",&n);

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

        read(a[i]);

    build(1,1,n);

    readline(m);

    for(i=1;i<=m;i++)

    {

        readline(way);readline(x);readline(y);

        if(x>y)

        	swap(x,y);

        if(way==1)

            printf("%lld\n",query(1,1,n,x,y));

        else

            update(1,1,n,x,y);

    }

    return 0;

}