首页 > 其他 > 详细

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

时间:2019-02-14 12:32:54      阅读:181      评论:0      收藏:0      [点我收藏+]

传送门:洛谷 P4145 上帝造题的七分钟2 / 花神游历各国
题目描述:

将区间内的每个数开平方,并区间求和

算法分析:\(\sqrt{x}\) 向下取整,那么\(\forall x \in R\),在经过有限次开平方运算后,其结果一定为\(1\)。故只需将大于\(1\)的区间的数开平方即可,就能大大降低时间复杂度


#include<iostream>
#include<cstdio>
#include<cmath>
#define ls k<<1
#define rs k<<1 | 1
#define mid ((l+r)>>1)
#define G ch=getchar()
#define in(x) x=read()
#define S(x) x=(int)sqrt(x)
using namespace std;
const int maxN=100000;
typedef long long rd;
typedef long long ll;
inline rd read();
int n,m,l,r,op;
ll sum[4*maxN+1],maxi[4*maxN+1];
void update(int,int,int,int,int);
ll query(int,int,int,int,int);
void build(int,int,int),pushup(int);
int main()
{
    in(n); build(1,1,n); in(m);
    for(register int i=1;i<=m;i++)
    {
        in(op); in(l); in(r);
        if(l>r) swap(l,r);
        if(op==0) update(1,1,n,l,r);
        else printf("%lld\n",query(1,1,n,l,r));
    }
    return 0;
}
void pushup(int k)
{
    sum[k]=sum[ls]+sum[rs];
    maxi[k]=max(maxi[ls],maxi[rs]);
}
void update(int k,int l,int r,int ql,int qr)
{
    if(l==r) {S(sum[k]); S(maxi[k]); return;}
    if(ql<=mid && maxi[ls]>1) update(ls,l,mid,ql,qr);
    if(qr>mid && maxi[rs]>1) update(rs,mid+1,r,ql,qr);
    pushup(k);
}
ll query(int k,int l,int r,int ql,int qr)
{
    if(ql<=l && r<=qr) return sum[k];
    ll ans=0;
    if(ql<=mid) ans+=query(ls,l,mid,ql,qr);
    if(qr>mid) ans+=query(rs,mid+1,r,ql,qr);
    return ans;
}
void build(int k,int l,int r)
{
    if(l==r) {in(sum[k]); maxi[k]=sum[k]; return;}
    build(ls,l,mid); build(rs,mid+1,r);
    pushup(k);
}
inline rd read()
{
    char ch=getchar();
    rd num=0,f=1;
    while((ch<'0' || ch>'9') && ch!='-') G;
    if(ch=='-') {f=-1; G;}
    while(ch>='0' && ch<='9') {num=num*10+ch-'0'; G;}
    return num*f;
}

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

原文:https://www.cnblogs.com/ezsyshx/p/10373873.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!