BZOJ3211: 花神游历各国【线段树】

3211: 花神游历各国

【题目描述】

传送门

【题解】

我们知道一个整数开根号取整最后会一直是1或0,而且10^9开五六次根号就变成了1,所以完全可以暴力开根号,如果区间最大值<=1时就可以不用做了。

代码如下

#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int MAXN=1e6+5;
int n,m,a[MAXN],Max[MAXN<<2];LL Tre[MAXN<<2];
void PushUp(int x){Tre[x]=Tre[x<<1]+Tre[x<<1|1],Max[x]=max(Max[x<<1],Max[x<<1|1]);}
void Build(int rt,int L,int R){
    if(L==R) return (void)(Tre[rt]=a[L],Max[rt]=a[L]);
    int mid=(R+L)>>1;
    Build(rt<<1,L,mid);Build(rt<<1|1,mid+1,R);
    PushUp(rt);
}
void Insert(int rt,int L,int R,int l,int r){
    if(L==R){Max[rt]=Tre[rt]=sqrt(Tre[rt]);return;}
    int mid=(R+L)>>1;
    if(l<=mid&&Max[rt<<1  ]>1) Insert(rt<<1  ,L,mid,l,r);
    if(mid<r &&Max[rt<<1|1]>1) Insert(rt<<1|1,mid+1,R,l,r);
    PushUp(rt);
}
LL Query(int rt,int L,int R,int l,int r){
    if(l<=L&&R<=r) return Tre[rt];
    int mid=(R+L)>>1;LL Sum=0;
    if(l<=mid) Sum+=Query(rt<<1,L,mid,l,r);
    if(mid<r) Sum+=Query(rt<<1|1,mid+1,R,l,r);
    return Sum;
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("prob.in","r",stdin);
    freopen("prob.out","w",stdout);
    #endif
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    Build(1,1,n);scanf("%d",&m);
    for(int i=1,opt,l,r,x;i<=m;i++){
        scanf("%d%d%d",&opt,&l,&r);
        if(opt==2) Insert(1,1,n,l,r);
        else printf("%lld\n",Query(1,1,n,l,r));
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部